Keep your distance: Land division with separation

Edith Elkind; Erel Segal-Halevi; Warut Suksompong

doi:10.1016/j.comgeo.2023.102006

Keep your distance: Land division with separation

Edith Elkind, Erel Segal-Halevi, Warut Suksompong^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

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 axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions.

Original language	English (US)
Article number	102006
Journal	Computational Geometry: Theory and Applications
Volume	113
DOIs	https://doi.org/10.1016/j.comgeo.2023.102006
State	Published - Aug 2023

Funding

This work was partially supported by the European Research Council (ERC) under grant number 639945 (ACCORD), by the Israel Science Foundation under grant number 712/20, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and by an NUS Start-up Grant. We would like to thank Kshitij Gajjar for his insights and references regarding guillotine partitions, Alex Ravsky for his insights regarding rainbow independent sets, Qiaochu Yuan for mathematical help, and the anonymous reviewers of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021) and Computational Geometry: Theory and Applications for their valuable comments and suggestions.

Keywords

Fair division
Guillotine partition
Land division
Maximin share
Separation

ASJC Scopus subject areas

Computer Science Applications
Geometry and Topology
Control and Optimization
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/j.comgeo.2023.102006

Cite this

@article{1fdbbeaf4f8147cdaa3bb0859cc4ef6f,

title = "Keep your distance: Land division with separation",

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 axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions.",

keywords = "Fair division, Guillotine partition, Land division, Maximin share, Separation",

author = "Edith Elkind and Erel Segal-Halevi and Warut Suksompong",

note = "Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = aug,

doi = "10.1016/j.comgeo.2023.102006",

language = "English (US)",

volume = "113",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Keep your distance

T2 - Land division with separation

AU - Elkind, Edith

AU - Segal-Halevi, Erel

AU - Suksompong, Warut

PY - 2023/8

Y1 - 2023/8

N2 - 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 axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions.

AB - 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 axis-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting. Our work makes use of tools and concepts from computational geometry such as independent sets of rectangles and guillotine partitions.

KW - Fair division

KW - Guillotine partition

KW - Land division

KW - Maximin share

KW - Separation

UR - http://www.scopus.com/inward/record.url?scp=85150484631&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85150484631&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2023.102006

DO - 10.1016/j.comgeo.2023.102006

M3 - Article

AN - SCOPUS:85150484631

SN - 0925-7721

VL - 113

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

M1 - 102006

ER -

Keep your distance: Land division with separation

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this