Envy-Free Division of Land
From MaRDI portal
Publication:3387907
DOI10.1287/MOOR.2019.1016zbMATH Open1451.90092arXiv1609.03938OpenAlexW2921789274MaRDI QIDQ3387907FDOQ3387907
Authors: Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, Yonatan Aumann 
Publication date: 8 January 2021
Published in: Mathematics of Operations Research (Search for Journal in Brave)
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 multi-dimensional 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 multi-dimensional resource wherein the allocated piece must have a pre-specified geometric shape. We present constructive division algorithms that satisfy the two most prominent fairness criteria, namely envy-freeness and proportionality. In settings where proportionality cannot be achieved due to 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.
Full work available at URL: https://arxiv.org/abs/1609.03938
Recommendations
- Envy-free divisions
- Competitive envy-free division
- Envy freeness in experimental fair division problems
- Allocation rules for land division
- Envy-free division in the presence of a dragon
- How to decrease the degree of envy in allocations of indivisible goods
- Fair allocation of disputed properties
- Fair allocation of indivisible goods with minimum inequality or minimum envy
- On finding an envy-free Pareto-optimal division
Discrete location and assignment (90B80) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)
Cites Work
- Rental Harmony: Sperner's Lemma in Fair Division
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- Title not available (Why is that?)
- Strategic divide and choose
- Truth, justice, and cake cutting
- How to Cut A Cake Fairly
- Title not available (Why is that?)
- How to cut a pizza fairly: fair division with decreasing marginal evaluations
- Equitable allocation of divisible goods
- How to Cut a Cake Fairly
- Rental harmony with roommates
- Fair division of a measurable space
- A moving-knife solution to the four-person envy-free cake-division problem
- An Envy-Free Cake Division Protocol
- Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
- Proportional pie-cutting
- Cutting a pie is not a piece of cake
- Envy-free cake divisions cannot be found by finite protocols
- On the fair division of a heterogeneous commodity
- A foundation of location theory: existence of equilibrium, the welfare theorems, and core
- Allocation rules for land division
- A theory of a heterogeneous divisible commodity exchange economy
- Representation of preference relations on \(\sigma \)-algebras of nonatomic measure spaces: convexity and continuity
- Efficient egalitarian equivalent allocations over a single good
- Cutting a Cake for Five People
- Algorithmic solutions for envy-free cake cutting
- A foundation of location theory: Consumer preferences and demand
- Economies with land -- A game theoretical approach
- Children crying at birthday parties. Why?
- Determining a Fair Border
- Computing depth orders for fat objects and related problems
- Constructing a Fair Border
- A combinatorial algorithm to establish a fair border
- On finding an envy-free Pareto-optimal division
- Disputed lands
- Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal
- Existence of efficient envy-free allocations of a heterogeneous divisible commodity with nonadditive utilities
- Monotonicity and competitive equilibrium in cake-cutting
- Fair and square: cake-cutting in two dimensions
- Meta-Envy-Free Cake-Cutting Protocols
Cited In (5)
This page was built for publication: Envy-Free Division of Land
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387907)
