Envy-Free Division of Land
From MaRDI portal
Publication:3387907
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.
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
Cites work
- scientific article; zbMATH DE number 1234106 (Why is no real title available?)
- scientific article; zbMATH DE number 1015852 (Why is no real title available?)
- 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects
- A combinatorial algorithm to establish a fair border
- A foundation of location theory: Consumer preferences and demand
- A foundation of location theory: existence of equilibrium, the welfare theorems, and core
- A moving-knife solution to the four-person envy-free cake-division problem
- A theory of a heterogeneous divisible commodity exchange economy
- Algorithmic solutions for envy-free cake cutting
- Allocation rules for land division
- An Envy-Free Cake Division Protocol
- Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
- Children crying at birthday parties. Why?
- Computing depth orders for fat objects and related problems
- Constructing a Fair Border
- Cutting a Cake for Five People
- Cutting a pie is not a piece of cake
- Determining a Fair Border
- Disputed lands
- Economies with land -- A game theoretical approach
- Efficient egalitarian equivalent allocations over a single good
- Envy-free cake divisions cannot be found by finite protocols
- Equitable allocation of divisible goods
- Existence of efficient envy-free allocations of a heterogeneous divisible commodity with nonadditive utilities
- Fair and square: cake-cutting in two dimensions
- Fair division of a measurable space
- How to Cut A Cake Fairly
- How to Cut a Cake Fairly
- How to cut a pizza fairly: fair division with decreasing marginal evaluations
- Meta-Envy-Free Cake-Cutting Protocols
- Monotonicity and competitive equilibrium in cake-cutting
- On finding an envy-free Pareto-optimal division
- On the fair division of a heterogeneous commodity
- Proportional pie-cutting
- Rental Harmony: Sperner's Lemma in Fair Division
- Rental harmony with roommates
- Representation of preference relations on \(\sigma \)-algebras of nonatomic measure spaces: convexity and continuity
- Strategic divide and choose
- Truth, justice, and cake cutting
- Waste makes haste: bounded time algorithms for envy-free cake cutting with free disposal
Cited in
(6)
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)
