Keep Your Distance: Land Division With Separation
Keep Your Distance: Land Division With Separation
复制标题
保持距离：土地分割与分离
DOI：
10.1016/j.comgeo.2023.102006
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Warut Suksompong
中科院分区：
文献类型：
--
作者：
Edith Elkind;Erel Segal;Warut Suksompong
本文是正在进行的努力的一部分，目的是通过处理现实生活中的应用程序的要求，使公平分工理论更接近实践。我们着重于土地地产分割的两个要求：(1)每个代理人应该得到一个可用的几何形状的地块，(2)不同代理人的地块必须在物理上分开。有了这些要求，比例的经典公平概念是不切实际的，因为它可能不可能达到任何乘法近似。相比之下，Budish在2011年推出的有序最大份额近似提供了有意义的公平保证。当可用形状为正方形、胖矩形或任意轴对齐矩形时，我们证明了可达到的最大共享保证的上下界，并探索了在这种情况下寻找公平分区的算法和查询复杂性。我们的工作利用了计算几何中的工具和概念，例如独立的矩形集和断头图划分。
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 ofproportionalityis impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, theordinal 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.
DOI：
10.1109/focs52979.2021.00042
发表时间：
2022
期刊：
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Mitchell, Joseph S.
通讯作者：
Mitchell, Joseph S.