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. 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 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 ${\displaystyle C}$. 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 ${\displaystyle \mathbb {R} ^{d}}$.

There are ${\displaystyle n}$ partners. Each partner ${\displaystyle i}$ has a personal value function ${\displaystyle V_{i}}$ which maps subsets of ${\displaystyle C}$ ("pieces") to numbers.

${\displaystyle C}$ has to be divided to ${\displaystyle n}$ disjoint pieces, one piece per partner. The piece allocated to partner ${\displaystyle i}$ is called ${\displaystyle X_{i}}$, and ${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$.

A division ${\displaystyle X}$ is called utilitarian or utilitarian-maximal or maxsum if it maximizes the following expression:

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i})}}$

The concept is often generalized by assigning a different weight to each partner. A division ${\displaystyle X}$ is called weighted-utilitarian-maximal (WUM) if it maximizes the following expression:

${\displaystyle \sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i}}}}$

where the ${\displaystyle w_{i}}$ are given positive constants.

Maxsum and Pareto-efficiency

Every WUM division with positive weights is obviously Pareto-efficient. This is because, if a division ${\displaystyle Y}$ Pareto-dominates a division ${\displaystyle X}$, then the weighted sum-of-utilities in ${\displaystyle Y}$ is strictly larger than in ${\displaystyle X}$, so ${\displaystyle X}$ cannot be a WUM division.

What's more surprising is that every Pareto-efficient division is WUM for some selection of weights.^[1]

Characterization of the utilitarian rule

Christopher P. Chambers suggests a characterization to the WUM rule.^[2] 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 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 ${\displaystyle w_{1},\dots ,w_{n}}$ 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 ${\displaystyle w_{1},\dots ,w_{n}}$ 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

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.

Another approach to combining efficiency and fairness is to find, among all possible fair divisions, a fair division with a highest sum-of-utilities:

Monotonicity properties of utilitarian cake-cutting

When the pieces may be disconnected, the absolute-utilitarian rule (maximizing the sum of non-normalized utilities) is resource-monotonic and population-monotonic. The relative-utilitarian rule (maximizing the sum of normalized utilities) is population-monotonic but not resource-monotonic.^[8]

This no longer holds when the pieces are connected.^[9]

See also

• Efficient cake-cutting
• Fair cake-cutting
• Weller's theorem
• Pareto-efficient envy-free division
• Rank-maximal allocation
• Utilitarian voting - the utilitarian principle in a different context.

References