Graphical Cake Cutting via Maximin Share

Elkind, Edith; Segal-Halevi, Erel; Suksompong, Warut

doi:10.24963/ijcai.2021/23

Graphical Cake Cutting via Maximin Share

Edith Elkind, Erel Segal-Halevi, Warut Suksompong

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 161-167.

https://doi.org/10.24963/ijcai.2021/23

Keywords

Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Resource Allocation

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.

Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. 2021. Graphical Cake Cutting via Maximin Share. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 161–167. https://doi.org/10.24963/ijcai.2021/23

@inproceedings{ijcai2021p23,
  title     = {Graphical Cake Cutting via Maximin Share},
  author    = {Elkind, Edith and Segal-Halevi, Erel and Suksompong, Warut},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {161--167},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/23},
  url       = {https://doi.org/10.24963/ijcai.2021/23},
}

TY  - CPAPER
TI  - Graphical Cake Cutting via Maximin Share
AU  - Elkind, Edith
AU  - Segal-Halevi, Erel
AU  - Suksompong, Warut
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 161
EP  - 167
DO  - 10.24963/ijcai.2021/23
UR  - https://doi.org/10.24963/ijcai.2021/23
ER  -