תקציר
We consider the classical cake cutting problem where we wish to fairly divide a heterogeneous resource among interested agents. Work on this subject typically assumes that the cake is represented by an interval. We introduce a generalized setting where the cake is represented by an arbitrary undirected graph, which allows us to model the division of road networks. Unlike in the interval setting, common fairness criteria such as proportionality cannot always be satisfied in graphical cake cutting if each agent must receive a connected subgraph. We determine the optimal approximation of proportionality that can be obtained for any number of agents with additive valuations, and exhibit a tight guarantee for each graph in the case of two agents. We also study several variants and extensions, including when more than one connected piece per agent is allowed as well as when the item to be divided is undesirable.
| שפה מקורית | אנגלית |
|---|---|
| עמודים (מ-עד) | 19-54 |
| מספר עמודים | 36 |
| כתב עת | SIAM Journal on Discrete Mathematics |
| כרך | 39 |
| מספר גיליון | 1 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 2025 |
טביעת אצבע
להלן מוצגים תחומי המחקר של הפרסום 'DIVIDING A GRAPHICAL CAKE'. יחד הם יוצרים טביעת אצבע ייחודית.פורמט ציטוט ביבליוגרפי
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver