Egalitarian cake-cutting is a kind offair cake-cutting in which the fairness criterion is theegalitarian rule. Thecake 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 calledleximin cake-cutting, since the optimization is done using theleximin order on the vectors of utilities.
The concept of egalitarian cake-cutting was first described byDubins andSpanier, who called it "optimal partition".[1]
Leximin-optimal allocations exist whenever the set of allocations is acompact 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 continuousheterogeneous resource ("cake"), the set of allocations is compact.[1] Therefore, leximin-optimal cake allocations always exist. For this reason, the leximin cake-allocation rule is sometimes called theDubins–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 theabsolute utility profile of an allocation (where elementi is just the utility of agenti), and itsrelative utility profile (where elementi is the utility of agenti divided by the total value for agenti). Theabsolute leximin rule chooses an allocation in which the absolute utility profile is leximin-maximal, and therelative leximin rule chooses an allocation in which the relative utility profile is leximin-maximal.
Both variants of the leximin rule are Pareto-optimal andpopulation monotonic. However, they differ in other properties:[3]
Both variants of the leximin rule may yield allocations that are notenvy-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 |
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.[3]
Dubins and Spanier[1] proved that, when all value-measures are strictly positive, every relative-leximin allocation is envy-free.[4]: Sec.4
Weller[4]: Sec.4 showed anenvy-free andefficient cake allocation that is not relative-leximin. The cake is [0,1], there are three agents, and their value measures aretrianglular 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 andutilitarian-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[2] presents an algorithm for computing a leximin-optimalresource allocation.
Aumann, Dombb and Hassidim[5] present an algorithm that, for everye>0, computes an allocation with egalitarian welfare at least (1-e) of the optimum using queries. This is exponential inn, 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 inn. The proof is by reduction from3-dimensional matching (3DM). For every instance of 3DM matching withm hyperedges, they construct a cake-cutting instance withn agents, where 4m ≤n ≤ 5m. They prove that, if the 3DM instance admits aperfect 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).