Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 19-54 |
| Number of pages | 36 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 39 |
| Issue number | 1 |
| DOIs | |
| State | Published - 2025 |
Funding
This work was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 1 (RG23/20) and grant MOE-T2EP20221-0001, by the European Research Council (ERC) under grant 639945 (ACCORD), by the Israel Science Foundation under grant 712/20, by the AI Programme of the Alan Turing Institute, and by an NUS Start-up Grant. We would like to thank the anonymous reviewer for detailed comments which significantly improved the presentation of this paper, and in particular for suggesting Corollary 4.15 and Theorem 4.23.
Keywords
- cake cutting
- fair division
- graph theory
ASJC Scopus subject areas
- General Mathematics