It says that a heterogeneous resource ("cake") can be divided among n partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF).
Thus, it is possible to divide a cake fairly without compromising on economic efficiency.
Thus, it connects two research fields which were previously unrelated: fair cake-cutting and general equilibrium.
A corollary of the Dubins–Spanier convexity theorem (1961) is that there always exists a "consensus partition" – a partition of the cake to n pieces such that every agent values every piece as exactly
Envy-freeness, as a criterion for fair allocation, were introduced into economics in the 1960s and studied intensively during the 1970s.
Varian's theorems study it in the context of dividing homogeneous goods.
Under mild restrictions on the agents' utility functions, there exist allocations which are both PE and EF.
The proof uses a previous result on the existence of a competitive equilibrium from equal incomes (CEEI).
David Gale proved a similar existence result for agents with linear utilities.
Cake-cutting is more challenging than homogeneous good allocation, since a cake is heterogeneous.
The presentation below is based on Weller's paper and partly on [2]: 341–351 .
Weller's proof relies on weighted-utilitarian-maximal (WUM) cake divisions.
If there are two or more people for whom this value is the same, then every arbitrary division of that piece between them results in a WUM division (WUM allocations can also be defined using the Radon–Nikodym set.
Weller proves that there exists a vector of weights for which the WUM division is also EF.
is a set-valued function from the unit-simplex-interior into the space of sets of PE cake-partitions.
satisfy the conditions of competitive equilibrium with equal incomes (CEEI).
, is exactly 1, since As an illustration, consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations: Since there are two agents, the vector
can be represented by a single number – the ratio of the weight of Alice to the weight of George: Berliant, Thomson and Dunz[3] introduced the criterion of group envy-freeness, which generalizes both Pareto-efficiency and envy-freeness.
They proved the existence of group-envy-free allocations with additive utilities.
Later, Berliant and Dunz[4] studied some natural non-additive utility functions, motivated by the problem of land division.
Some later works studied the algorithmic aspects of finding a CEEI partition.
These works usually assume that the value measures are piecewise-constant, i.e, the cake can divided to homogeneous regions in which the value-density of each agent is uniform.
The first algorithm for finding a CEEI partition in this case was developed by Reijnierse and Potters.
[6] In fact, every CEEI cake-partition maximizes the product of utilities, and vice versa – every partition that maximizes the product of utilities is a CEEI.
[7] Therefore, a CEEI can be found by solving a convex program maximizing the sum of the logarithms of utilities.
For two agents, the adjusted winner procedure can be used to find a PEEF allocation that is also equitable (but not necessarily a CEEI).
[5] In the CEEI partition guaranteed by Weller, the piece allocated to each partner may be disconnected.
Instead of a single contiguous piece, each partner may receive a pile of "crumbs".
The EI condition again implies that, in any connected CEEI division, the cake is cut in the middle.
In the above example, if we consider the cake to be a "pie" (i.e, if a piece is allowed to go around the cake boundary to the other boundary), then a PEEF allocation exists; however, Stromquist [9] showed a more sophisticated example where a PEEF allocation does not exist even in a pie.