Egalitarian cake-cutting is a kind of fair cake-cutting in which the fairness criterion is the egalitarian rule. The cake represents a continuous resource (such as land or time), that has to be allocated among people with different valuations over parts of the resource. The goal in egalitarian cake-cutting is to maximize the smallest value of an agent; subject to this, maximize the next-smallest value; and so on. It is also called leximin cake-cutting, since the optimization is done using the leximin order on the vectors of utilities.
The concept of egalitarian cake-cutting was first described by Dubins and Spanier, who called it "optimal partition".[1]
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.[2]
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.
Both variants of the leximin rule are Pareto-optimal and population monotonic. However, they differ in other properties:[3]
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):
| Agent | Left | Middle | Right | |
|---|---|---|---|---|
| A | 6 | 9 | ||
| B | 5 | 10 | ||
| C | 15 | |||
| D | 15 | |||
| E | 15 |
Dubins and Spanier proved that, when all value-measures are strictly positive, every relative-leximin allocation is envy-free.[4]
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.
Dall'aglio presents an algorithm for computing a leximin-optimal resource allocation.
Aumann, Dombb and Hassidim[5] present an algorithm that, for every e>0, computes an allocation with egalitarian welfare at least (1-e) of the optimum using
2n ⋅ n ⋅ log2(n/\epsilon)
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).