Weller's theorem is a theorem in economics. 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.
Contents
- Background
- Notation
- Proof sketch
- Calculating the price measure
- Example
- Generalizations and extensions
- Algorithms
- Limitations
- References
Moreover, Weller's theorem says that there exists a price such that the allocation and the price are a competitive equilibrium (CE) with equal incomes (EI). Thus, it connects two research fields which were previously unrelated: fair cake-cutting and general equilibrium.
Background
Fair cake-cutting has been studied since the 1940s. There is a heterogeneous divisible resource, such as a cake or a land-estate. There are n partners, each of whom has a personal value-density function over the cake. The value of a piece to a partner is the integral of his value-density over that piece (this means that the value is a nonatomic measure over the cake). The envy-free cake-cutting problem is to partition the cake to n disjoint pieces, one piece per agent, such for each agent, the value of his piece is weakly larger than the values of all other pieces (so no agent envies another agent's share).
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. In a sense, a cake is a continuum of goods: each point in the cake is a different good. This is the topic of Weller's theorem.
Notation
The cake is denoted by
A cake partition, denoted by
A partition is called PEEF if it satisfies the following two conditions:
A partition
CEEI is much stronger than PEEF: every CEEI allocation is PEEF, but there are many PEEF allocations which are not CEEI.
Weller's theorem proves the existence of a CEEI allocation, which implies the existence of a PEEF allocation.
Proof sketch
The presentation below is based on Weller's paper and partly on .
Weller's proof relies on weighted-utilitarian-maximal (WUM) cake divisions. A WUM division is a division maximizing a function of the following form:
where
A corollary of the Dubins–Spanier compactness theorem is that, for every weight-vector
Every WUM division is obviously PE. However, a WUM division can be very unfair; for example, if
Weller proves that there exists a vector of weights for which the WUM division is also EF. This is done by defining several functions:
1. The function
2. The function
3. The function
To prove that the function
Therefore,
By definition of
Combining the last two inequalities gives, for every two agents
which is exactly the definition of envy-freeness.
Calculating the price measure
Once we have a PEEF allocation
It is possible to prove that the pair
Example
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
Generalizations and extensions
Berliant, Thomson and Dunz 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 studied some natural non-additive utility functions, motivated by the problem of land division. When utilities are not additive, a CEEI allocation is no longer guaranteed to exist, but it does exist under certain restrictions.
More related results can be found in Efficient cake-cutting and Utilitarian cake-cutting.
Algorithms
Weller's theorem is purely existential. Some later authors studied the algorithmic aspects of finding a CEEI partition:
If the value measures are piecewise-constant, then there is an algorithm that finds a CEEI partition.
If the value measures are Lipschitz continuous, then they can be approximated as piecewise-constant functions "as close as we like", therefore that algorithm approximates a CEEI partition "as close as we like".
Limitations
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". Indeed, when the pieces must be connected, CEEI partitions might not exist. Consider the following piecewise-constant valuations:
The CE condition implies that all peripheral slices must have the same price (say, p) and both central slices must have the same price (say q). The EI condition implies that the total cake-price should be 2, so
While the CEEI condition may be unattainable with connected pieces, the weaker PEEF condition is always attainable when there are two partners. This is because with two partners, envy-freeness is equivalent to proportionality, and proportionality is preserved under Pareto-improvements. However, when there are three or more partners, even the weaker PEEF condition may be unattainable.