Envy-Free Division of Land

Erel Segal-Halevi (), Shmuel Nitzan, Avinatan Hassidim () and Yonatan Aumann ()
Additional contact information
Erel Segal-Halevi: Ariel University, Ariel 40700, West Bank, Israel;
Avinatan Hassidim: Bar-Ilan University, Ramat Gan 5290002, Israel
Yonatan Aumann: Bar-Ilan University, Ramat Gan 5290002, Israel

Mathematics of Operations Research, 2020, vol. 45, issue 3, 896-922

Abstract: Classic cake-cutting algorithms enable people with different preferences to divide among them a heterogeneous resource (“cake”) such that the resulting division is fair according to each agent’s individual preferences. However, these algorithms either ignore the geometry of the resource altogether or assume it is one-dimensional. In practice, it is often required to divide multidimensional resources, such as land estates or advertisement spaces in print or electronic media. In such cases, the geometric shape of the allotted piece is of crucial importance. For example, when building houses or designing advertisements, in order to be useful, the allotments should be squares or rectangles with bounded aspect ratio. We, thus, introduce the problem of fair land division —fair division of a multidimensional resource wherein the allocated piece must have a prespecified geometric shape. We present constructive division algorithms that satisfy the two most prominent fairness criteria, namely envy-freeness and proportionality . In settings in which proportionality cannot be achieved because of the geometric constraints, our algorithms provide a partially proportional division, guaranteeing that the fraction allocated to each agent be at least a certain positive constant. We prove that, in many natural settings, the envy-freeness requirement is compatible with the best attainable partial-proportionality.

Keywords: fairness; land division; cake cutting; envy free; two-dimensional; cutting and packing (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.1016 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:3:p:896-922

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().