Weller's theorem
is a theorem in
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analy ...
. It says that a heterogeneous resource ("cake") can be divided among ''n'' partners with different valuations in a way that is both
Pareto-efficient
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engin ...
(PE) and
envy-free Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by a ...
(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
Competitive equilibrium (also called: Walrasian equilibrium) is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and s ...
(CE) with equal incomes (EI). Thus, it connects two research fields which were previously unrelated:
fair cake-cutting
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
and
general equilibrium
In economics, general equilibrium theory attempts to explain the behavior of supply, demand, and prices in a whole economy with several or many interacting markets, by seeking to prove that the interaction of demand and supply will result in an ov ...
.
Background
Fair cake-cutting
Fair cake-cutting is a kind of fair division problem. The problem involves a ''heterogeneous'' resource, such as a cake with different toppings, that is assumed to be ''divisible'' – it is possible to cut arbitrarily small pieces of it without ...
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 In mathematics, more precisely in measure theory, an atom is a measurable set which has positive measure and contains no set of smaller positive measure. A measure which has no atoms is called non-atomic or atomless.
Definition
Given a measurable ...
over the cake). The
envy-free cake-cutting
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other s ...
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
. 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
. 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 Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first ...
study it in the context of dividing homogeneous
goods
In economics, goods are items that satisfy human wants
and provide utility, for example, to a consumer making a purchase of a satisfying product. A common distinction is made between goods which are transferable, and services, which are not ...
. 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
Competitive equilibrium (also called: Walrasian equilibrium) is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and s ...
from equal incomes (CEEI). David Gale proved a similar existence result for agents with
linear utilities In economics and consumer theory, a linear utility function is a function of the form:
::u(x_1,x_2,\dots,x_m) = w_1 x_1 + w_2 x_2 + \dots w_m x_m
or, in vector form:
::u(\overrightarrow) = \overrightarrow \cdot \overrightarrow
where:
* m is the n ...
.
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
. The number of partners is denoted by
.
A ''cake partition'', denoted by
, is an ''n''-tuple
of subsets of
;
is the piece given to partner
.
A partition is called ''PEEF'' if it satisfies the following two conditions:
*
Pareto efficiency
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engin ...
: no other division is weakly better for all partners and strictly better for at least one partner.
*
Envy-freeness Envy-freeness, also known as no-envy, is a criterion for fair division. It says that, when resources are allocated among people with equal rights, each person should receive a share that is, in their eyes, at least as good as the share received by ...
: no partner strictly prefers a piece allocated to another agent.
A partition
and a price-measure
on
are called ''CEEI'' if they satisfy the following two conditions (where
is agent
's value measure and
is the price measure):
*
Competitive equilibrium
Competitive equilibrium (also called: Walrasian equilibrium) is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and s ...
: For every agent ''i'', every positive slice
, and every positive slice
:
.
* Equal incomes: For every agent i:
.
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
is an index of an agent,
is agent
's value measure,
is the piece given to
, and
is a positive weight.
A corollary of the
Dubins–Spanier compactness theorem is that, for every weight-vector
, WUM allocations exist. Intuitively, each tiny piece of cake
should be given to the person
for whom
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
(WUM allocations can also be defined using the Radon–Nikodym set. Each weight-vector , as a point on the -dimensional unit simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
, defines a partition of that simplex. This partition induces an allocation of the Radon–Nikodym set of the cake, which induces one or more allocations of the cake).
Every WUM division is obviously PE. However, a WUM division can be very unfair; for example, if
is very large, then agent
might get only a small fraction of the cake
(the weight-vector is very close to agent 's vertex of the unit-simplex, which means that will get only points of the Radon–Nikodym set that are very near its vertex). In contrast, if
is very small, then agent
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
: for every positive weight vector