Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different
cardinal utility functions, such that the ''sum'' of the utilities of the partners is as large as possible. It is a special case of the
utilitarian social choice rule
In social choice and operations research, the utilitarian rule (also called the max-sum rule) is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the ''sum of the utilities'' of all individual ...
. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with
fair cake-cutting.
Example
Consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations:
The utilitarian rule gives each part to the partner with the highest utility. In this case, the utilitarian rule gives the entire chocolate to Alice and the entire Vanilla to George. The maxsum is 13.
The utilitarian division is not fair: it is not
proportional
Proportionality, proportion or proportional may refer to:
Mathematics
* Proportionality (mathematics), the property of two variables being in a multiplicative relation to a constant
* Ratio, of one quantity to another, especially of a part compare ...
since George receives less than half the total cake value, and it is not
envy-free since George envies Alice.
Notation
The cake is called
. It is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane
.
There are
partners. Each partner
has a personal value function
which maps subsets of
("pieces") to numbers.
has to be divided to
disjoint pieces, one piece per partner. The piece allocated to partner
is called
, and
.
A division
is called ''utilitarian'' or ''utilitarian-maximal'' or ''maxsum'' if it maximizes the following expression:
:
The concept is often generalized by assigning a different weight to each partner. A division
is called ''weighted-utilitarian-maximal'' (WUM) if it maximizes the following expression:
:
where the
are given positive constants.
Maxsum and Pareto-efficiency
Every WUM division with positive weights is obviously
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 ...
. This is because, if a division
Pareto-dominates a division
, then the weighted sum-of-utilities in
is strictly larger than in
, so
cannot be a WUM division.
What's more surprising is that ''every'' Pareto-efficient division is WUM for some selection of weights.
Characterization of the utilitarian rule
Christopher P. Chambers suggests a
characterization to the WUM rule.
The characterization is based on the following properties of a division rule ''R'':
* Pareto-efficiency (PE): the rule ''R'' returns only divisions which are Pareto-efficient.
* Division independence (DI): whenever a cake is partitioned to several sub-cakes and each cake is divided according to rule ''R'', the result is the same as if the original cake were partitioned according to ''R''.
* Independence of infeasible land (IIL): whenever a sub-cake is divided according to ''R'', the result does not depend on the utilities of the partners in the other sub-cakes.
* Positive treatment of equals (PTE): whenever all partners have the same utility function, ''R'' recommends at least one division that gives a positive utility to each partner.
* Scale-invariance (SI): whenever the utility functions of the partners are multiplied by constants (a possibly different constant to each partner), the recommendations given by ''R'' do not change.
* Continuity (CO): for a fixed piece of cake, the set of utility profiles which map to a specific allocation is a
closed set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a cl ...
under
pointwise convergence.
The following is proved for partners that assign positive utility to every piece of cake with positive size:
* If ''R'' is PE DI and IIL, then there exists a sequence of weights
such that all divisions recommended by ''R'' are WUM with these weights (it is known that every PE division is WUM with ''some'' weights; the news are that all divisions recommended by ''R'' are WUM with ''the same'' weights. This follows from the DI property).
* If ''R'' is PE DI IIL and PTE, then all divisions recommended by ''R'' are utilitarian-maximal (in other words, all divisions must be WUM and all agents must have equal weights. This follows from the PTE property).
* If ''R'' is PE DI IIL and SI, then ''R'' is a dictatorial rule - it gives the entire cake to a single partner.
* If ''R'' is PE DI IIL and CO, then there exists a sequence of weights
such that ''R'' is a WUM rule with these weights (i.e. ''R'' recommends all and only WUM divisions with these weights).
Finding utilitarian divisions
Disconnected pieces
When the value functions are additive, maxsum divisions always exist. Intuitively, we can give each fraction of the cake to the partner that values it the most, as in the
example above. Similarly, WUM divisions can be found by giving each fraction of the cake to the partner for whom the ratio
is largest.
This process is easy to carry out when cake is ''piecewise-homogeneous'', i.e., the cake can be divided to a finite number of pieces such that the value-density of each piece is constant for all partners.
When the cake is not piecewise-homogeneous, the above algorithm does not work since there is an infinite number of different "pieces" to consider.
Maxsum divisions still exist. This is a corollary of the
Dubins–Spanier compactness theorem and it can also be proved using the
Radon–Nikodym set
In the theory of fair cake-cutting, the Radon–Nikodym set (RNS) is a geometric object that represents a cake, based on how different people evaluate the different parts of the cake.
Example
Suppose we have a cake made of four parts. There are ...
.
However, no finite algorithm can find a maxsum division. Proof:
A finite algorithm has value-data only about a finite number of pieces. I.e. there is only a finite number of subsets of the cake, for which the algorithm knows the valuations of the partners. Suppose the algorithm has stopped after having value-data about
subsets. Now, it may be the case that all partners answered all the queries as if they have the ''same'' value measure. In this case, the largest possible utilitarian value that the algorithm can achieve is 1. However, it is possible that deep inside one of the
pieces, there is a subset which two partners value differently. In this case, there exists a
super-proportional division A strongly-proportional division (sometimes called super-proportional division) is a kind of a fair division. It is a division of resources among ''n'' partners, in which the value received by each partner is strictly more than his/her due share of ...
, in which each partner receives a value of more than
, so the sum of utilities is strictly more than 1. Hence, the division returned by the finite algorithm is not maxsum.
Connected pieces
When the cake is 1-dimensional and the pieces must be connected, the simple algorithm of assigning each piece to the agent that values it the most no longer works, even with
piecewise-constant valuations. In this case, the problem of finding a UM division is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
, and furthermore no
FPTAS is possible unless P=NP.
There is an 8-factor approximation algorithm, and a
fixed-parameter tractable algorithm which is exponential in the number of players.
For every set of positive weights, a WUM division exists and can be found in a similar way.
Maxsum and fairness
A maxsum division is not always fair; see the
example above. Similarly, a fair division is not always maxsum.
One approach to this conflict is to bound the "price of fairness" - calculate upper and lower bounds on the amount of decrease in the sum of utilities, that is required for fairness. For more details, see
price of fairness In the theory of fair division, the price of fairness (POF) is the ratio of the largest economic welfare attainable by a division to the economic welfare attained by a ''fair'' division. The POF is a quantitative measure of the loss of welfare that ...
.
Another approach to combining efficiency and fairness is to find, among all possible fair divisions, a fair division with a highest sum-of-utilities:
Finding utilitarian-fair allocations
The following algorithms can be used to find an
envy-free cake-cutting with maximum sum-of-utilities, for a cake which is a 1-dimensional interval, when each person may receive disconnected pieces and the value functions are additive:
# For
partners with
''piecewise-constant'' valuations: divide the cake into ''m'' totally-constant regions. Solve a
linear program with ''nm'' variables: each (agent, region) pair has a variable that determines the fraction of the region given to the agent. For each region, there is a constraint saying that the sum of all fractions from this region is 1; for each (agent, agent) pair, there is a constraint saying that the first agent does not envy the second one. Note that the allocation produced by this procedure might be highly fractioned.
# For
partners with
''piecewise-linear'' valuations: for each point in the cake, calculate the ratio between the utilities:
. Give partner 1 the points with
and partner 2 the points with