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.
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 formula_1. A consensus partition is of course EF, but it is not PE. Moreover, another corollary of the Dubins–Spanier convexity theorem is that, when at least two agents have different value measures, there exists a division that gives each agent strictly more than formula_1. This means that the consensus partition is not even weakly PE.
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 formula_3. The number of partners is denoted by formula_4.
A "cake partition", denoted by formula_5, is an "n"-tuple formula_6 of subsets of formula_3; formula_8 is the piece given to partner formula_9.
A partition is called "PEEF" if it satisfies the following two conditions:
A partition formula_5 and a price-measure formula_11 on formula_3 are called "CEEI" if they satisfy the following two conditions (where formula_13 is agent formula_9's value measure and formula_11 is the price measure):
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.
Weller's proof relies on "weighted-utilitarian-maximal (WUM)" cake divisions. A WUM division is a division maximizing a function of the following form:
formula_20
where formula_9 is an index of an agent, formula_13 is agent formula_9's value measure, formula_8 is the piece given to formula_9, and formula_26 is a positive weight.
A corollary of the Dubins–Spanier compactness theorem is that, for every weight-vector formula_27, WUM allocations exist. Intuitively, each tiny piece of cake formula_28 should be given to the person formula_9 for whom formula_30 is largest. 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 .
Every WUM division is obviously PE. However, a WUM division can be very unfair; for example, if formula_26 is very large, then agent formula_9 might get only a small fraction of the cake . In contrast, if formula_26 is very small, then agent formula_9 might get the entire cake.
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 formula_35: for every positive weight vector formula_36, formula_37 is the set of WUM partitions with weights formula_27. The function formula_35 is a set-valued function from the unit-simplex-interior into the space of sets of PE cake-partitions.
2. The function formula_40: for every partition formula_41, formula_42 is a vector proportional to the values of the partners: formula_43. The function formula_40 maps the space of cake-partitions into the unit-simplex.
3. The function formula_45: for every positive weight-vector formula_27, formula_47 is a set of new weight-vectors. This is a set-valued function from the interior of the unit-simplex into the set of subsets of the unit-simplex. The vectors in formula_47 are, in a sense, opposite to formula_27: if formula_26 is small, then the partitions in formula_37 give agent formula_9 a large value and its weight in formula_47 is large. In contrast, if formula_26 is large then the partitions in formula_37 give agent formula_9 a small value and its weight in formula_47 is large. This hints that, if formula_58 has a fixed-point, then this fixed-point corresponds to the PEEF partition that we look for.
To prove that the function formula_58 has a fixed-point, we would like to use the Kakutani fixed-point theorem. However, there is a technical issue that should be handled: the function formula_58 is defined only on the interior of the unit-simplex, while its range is the entire unit-simplex. Fortunately, it is possible to extend formula_58 to the boundary of the unit-simplex, in a way that will guarantee that any fixed-point will NOT be on the boundary. The extended function, formula_62, is indeed a function from the unit-simplex to subsets of the unit-simplex. formula_62 satisfies the requirements of Kakutani' fixed-point theorem, since:
Therefore, formula_62 has a fixed-point – a vector formula_67 in the unit-simplex such that formula_68. By the construction of formula_62, it is possible to show that the fixed-point formula_67 must be in the unit-simplex-interior, where formula_71. Hence:
formula_72
By definition of formula_58, formula_74, so there exists a partition formula_5 such that:
formula_5 is clearly PE since it is WUM (with weight-vector W). It is also EF, since:
formula_82
formula_85
Combining the last two inequalities gives, for every two agents formula_81:
formula_87
which is exactly the definition of envy-freeness.
Calculating the price measure.
Once we have a PEEF allocation formula_5, a price measure formula_11 can be calculated as follows:
It is possible to prove that the pair formula_93 satisfy the conditions of competitive equilibrium with equal incomes (CEEI). Specifically, the income of every agent, under the price measure formula_11, is exactly 1, since
formula_95
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 formula_27 can be represented by a single number – the ratio of the weight of Alice to the weight of George:
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 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. 
A more computationally-efficient algorithm was developed by Aziz and Ye.
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. 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).
All the above algorithms can be generalized to value-measures that are Lipschitz continuous. Since such functions can be approximated as piecewise-constant functions "as close as we like", the above algorithms can also approximate a PEEF allocation "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 formula_97. The EI condition again implies that, in any connected CEEI division, the cake is cut in the middle. Both Alice and George receive two peripheral slices and one central slice. The CE condition for Alice implies that formula_98 but the CE condition on George implies that formula_99, which is a contradiction.
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. Consider the following piecewise-constant valuations:
EF implies that Bob receives at least some of his 7-valued slice (PE then implies that he receives all of it).
By connectivity, there are three options:
Hence, no allocation is PEEF. 
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 showed a more sophisticated example where a PEEF allocation does not exist even in a pie.
References.
 ;templatestyles src="Reflist/styles.css" / ;