Keep Your Distance: Land Division With Separation
arXiv:2105.06669 · doi:10.1016/j.comgeo.2023.102006
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 \emph{proportionality} is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the \emph{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.
arXiv commentAppears in the 30th International Joint Conference on Artificial Intelligence (IJCAI), 2021
References in corpus (10)
- Weighted Envy-Freeness in Indivisible Item Allocation
- Fair and Square: Cake-Cutting in Two Dimensions
- Fair and Square: Cake-cutting in Two Dimensions
- Picking Sequences and Monotonicity in Weighted Fair Division
- On Maximum Weighted Nash Welfare for Binary Valuations
- 'Fair' Partitions of Polygons - an Introduction
- Cake-Cutting with Different Entitlements: How Many Cuts are Needed?
- The Price of Connectivity in Fair Division
- Envy-Free Division of Land
- Mind the Gap: Cake Cutting With Separation