The concept of egalitarian cake-cutting was first described by Dubins and Spanier, who called it "optimal partition".
Dubins and Spanier proved that, with a continuous heterogeneous resource ("cake"), the set of allocations is compact.
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.
However, they differ in other properties:[3] Both variants of the leximin rule may yield allocations that are not envy-free.
[3] Dubins and Spanier[1] proved that, when all value-measures are strictly positive, every relative-leximin allocation is envy-free.
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.
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
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).