Keep Your Distance: Land Division With Separation

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

doi:10.24963/ijcai.2021/24

Keep Your Distance: Land Division With Separation

Edith Elkind, Erel Segal-Halevi, Warut Suksompong

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 168-174.

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

Keywords

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

Abstract

This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of proportionality is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the ordinal maximin share approximation, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axes-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting.

Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. 2021. Keep Your Distance: Land Division With Separation. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 168–174. https://doi.org/10.24963/ijcai.2021/24

@inproceedings{ijcai2021p24,
  title     = {Keep Your Distance: Land Division With Separation},
  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     = {168--174},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/24},
  url       = {https://doi.org/10.24963/ijcai.2021/24},
}

TY  - CPAPER
TI  - Keep Your Distance: Land Division With Separation
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  - 168
EP  - 174
DO  - 10.24963/ijcai.2021/24
UR  - https://doi.org/10.24963/ijcai.2021/24
ER  -