Egalitarian cake-cutting
Fair division problem
- 3 min read
- 5 chapters
Explore on Lably
ToursExplore Lably’s 3D toursThe concept of egalitarian cake-cutting was first described by Dubins and Spanier, who called it "optimal partition".
Existence
Leximin-optimal allocations exist whenever the set of allocations is a compact space. This is always the case when allocating discrete objects, and easy to prove when allocating a finite number of continuous homogeneous resources. Dubins and Spanier proved that, with a continuous heterogeneous resource ("cake"), the set of allocations is compact. Therefore, leximin-optimal cake allocations always exist. For this reason, the leximin cake-allocation rule is sometimes called the Dubins–Spanier rule.
Sign in to keep reading
4 more chapters are free with a Lably account.
Variants
When the agents' valuations are not normalized (i.e., different agents may assign a different value to the entire cake), there is a difference between the absolute utility profile of an allocation (where element i is just the utility of agent i), and its relative utility profile (where element i is the utility of agent i divided by the total value for agent i). The absolute leximin rule chooses an allocation in which the absolute utility profile is leximin-maximal, and the relative leximin rule chooses an allocation in which the relative utility profile is leximin-maximal.
Properties
Both variants of the leximin rule are Pareto-optimal and population monotonic. However, they differ in other properties:
- The absolute-leximin rule is resource monotonic but not proportional;
- The relative-leximin rule is proportional but not resource-monotonic.
Relation to envy-freeness
Both variants of the leximin rule may yield allocations that are not envy-free. For example, suppose there are 5 agents, the cake is piecewise-homogeneous with 3 regions, and the agents' valuations are (missing values are zeros):
All agents value the entire cake at 15, so absolute-leximin and relative-leximin are equivalent. The largest possible minimum value is 5, so a leximin allocation must give all agents at least 5. This means that the Right must be divided equally among agents C, D, E, and the Middle must be given entirely to agent B. But then A envies B.
Dubins and Spanier proved that, when all value-measures are strictly positive, every relative-leximin allocation is envy-free.
Weller showed an envy-free and efficient cake allocation that is not relative-leximin. The cake is [0,1], there are three agents, and their value measures are trianglular distributions centered at 1/4, 1/2 and 3/4 respectively. The allocation ([0,3/8],[3/8,5/8],[5/8,1]) has utility profile (3/8,7/16,7/16). It is envy-free and utilitarian-optimal, hence Pareto-efficient. However, there is another allocation ([0,5/16],[5/16,11/16],[11/16,1]) with a leximin-better utility profile.
Computation
Dall'aglio presents an algorithm for computing a leximin-optimal resource allocation.
Aumann, Dombb and Hassidim present an algorithm that, for every e>0, computes an allocation with egalitarian welfare at least (1-e) of the optimum using queries. This is exponential in n, but polynomial in the number of accuracy digits.
On the other hand, they prove that, unless P=NP, it is impossible to approximate the optimal egalitarian value to a factor better than 2, in time polynomial in n. The proof is by reduction from 3-dimensional matching (3DM). For every instance of 3DM matching with m hyperedges, they construct a cake-cutting instance with n agents, where 4m ≤ n ≤ 5m. They prove that, if the 3DM instance admits a perfect matching, then there exists a cake allocation with egalitarian value at least 1/m; otherwise, there is no cake-allocation with egalitarian value larger than 1/(2m).