Abstract
We study the recently introduced cake-cutting setting in which the cake is represented by an undirected graph. This generalizes the canonical interval cake and allows for modeling the division of road networks. We show that when the graph is a forest, an allocation satisfying the well-known criterion of maximin share fairness always exists. Our result holds even when separation constraints are imposed; however, in the latter case no multiplicative approximation of proportionality can be guaranteed. Furthermore, while maximin share fairness is not always achievable for general graphs, we prove that ordinal relaxations can be attained.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 30th International Joint Conference on Artificial Intelligence, IJCAI 2021 |
| Editors | Zhi-Hua Zhou |
| Publisher | International Joint Conferences on Artificial Intelligence |
| Pages | 161-167 |
| Number of pages | 7 |
| ISBN (Electronic) | 9780999241196 |
| DOIs | |
| State | Published - 2021 |
| Event | 30th International Joint Conference on Artificial Intelligence, IJCAI 2021 - Virtual, Online, Canada Duration: Aug 19 2021 → Aug 27 2021 |
Publication series
| Name | IJCAI International Joint Conference on Artificial Intelligence |
|---|---|
| ISSN (Print) | 1045-0823 |
Conference
| Conference | 30th International Joint Conference on Artificial Intelligence, IJCAI 2021 |
|---|---|
| Country/Territory | Canada |
| City | Virtual, Online |
| Period | 8/19/21 → 8/27/21 |
Funding
This work was partially supported by the Israel Science Foundation under grant number 712/20 and by an NUS Start-up Grant. We would like to thank the anonymous reviewers for their valuable comments.
ASJC Scopus subject areas
- Artificial Intelligence
