Utilitarian cake-cutting (also calledmaxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with differentcardinal utility functions, such that thesum of the utilities of the partners is as large as possible. It is a special case of theutilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict withfair cake-cutting.

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 notproportional since George receives less than half the total cake value, and it is notenvy-free since George envies Alice.

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\bigsqcup ...\bigsqcup X_n}$.

A division${\displaystyle X}$ is calledutilitarian orutilitarian-maximal ormaxsum 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 calledweighted-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.

Every WUM division with positive weights is obviouslyPareto-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 thatevery Pareto-efficient division is WUM for some selection of weights.^[1]

Christopher P. Chambers suggests acharacterization to the WUM rule.^[2] The characterization is based on the following properties of a division ruleR:

• Pareto-efficiency (PE): the ruleR 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 ruleR, the result is the same as if the original cake were partitioned according toR.
• Independence of infeasible land (IIL): whenever a sub-cake is divided according toR, 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 byR do not change.
• Continuity (CO): for a fixed piece of cake, the set of utility profiles which map to a specific allocation is aclosed set underpointwise convergence.

The following is proved for partners that assign positive utility to every piece of cake with positive size:

• IfR is PE DI and IIL, then there exists a sequence of weights${\displaystyle w_1,\dots ,w_n}$ such that all divisions recommended byR are WUM with these weights (it is known that every PE division is WUM withsome weights; the news are that all divisions recommended byR are WUM withthe same weights. This follows from the DI property).
• IfR is PE DI IIL and PTE, then all divisions recommended byR are utilitarian-maximal (in other words, all divisions must be WUM and all agents must have equal weights. This follows from the PTE property).
• IfR is PE DI IIL and SI, thenR is a dictatorial rule - it gives the entire cake to a single partner.
• IfR is PE DI IIL and CO, then there exists a sequence of weights${\displaystyle w_1,\dots ,w_n}$ such thatR is a WUM rule with these weights (i.e.R recommends all and only WUM divisions with these weights).

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 theexample above. Similarly, WUM divisions can be found by giving each fraction of the cake to the partner for whom the ratio${\displaystyle V_i/w_i}$ is largest.

This process is easy to carry out when cake ispiecewise-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 theDubins–Spanier compactness theorem and it can also be proved using theRadon–Nikodym set.

However, no finite algorithm can find a maxsum division.Proof:^{[3][4]: Cor.2} 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${\displaystyle k}$ subsets. Now, it may be the case that all partners answered all the queries as if they have thesame 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${\displaystyle k}$ pieces, there is a subset which two partners value differently. In this case, there exists asuper-proportional division, in which each partner receives a value of more than${\displaystyle 1/n}$, so the sum of utilities is strictly more than 1. Hence, the division returned by the finite algorithm is not maxsum.

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 withpiecewise-constant valuations. In this case, the problem of finding a UM division isNP-hard, and furthermore noFPTAS is possible unless P=NP.

There is an 8-factor approximation algorithm, and afixed-parameter tractable algorithm which is exponential in the number of players.^[5]

For every set of positive weights, a WUM division exists and can be found in a similar way.

A maxsum division is not always fair; see theexample 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, seeprice 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:

The following algorithms can be used to find anenvy-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:^[6]

1. For${\displaystyle n}$ partners withpiecewise-constant valuations: divide the cake intom totally-constant regions. Solve alinear program withnm 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.
2. For${\displaystyle 2}$ partners withpiecewise-linear valuations: for each point in the cake, calculate the ratio between the utilities:${\displaystyle r=u_1/u_2}$. Give partner 1 the points with${\displaystyle r\ge r^{\ast }}$ and partner 2 the points with, where${\displaystyle r^{\ast }}$ is a threshold calculated so that the division is envy-free. In general${\displaystyle r^{\ast }}$ cannot be calculated because it might be irrational, but in practice, when the valuations are piecewise-linear,${\displaystyle r^{\ast }}$ can be approximated by an "irrational search" approximation algorithm. For any${\displaystyle ϵ>0}$, The algorithm find an allocation that is${\displaystyle ϵ}$-EF (the value of each agent is at least the value of each other agentminus${\displaystyle ϵ}$), and attains a sum that is at least the maximum sum of an EF allocation. Its run-time is polynomial in the input and in${\displaystyle \log (1/ϵ)}$.
3. For${\displaystyle n}$ partners with general valuations: additive approximation to envy and efficiency, based on the piecewise-constant-valuations algorithm.

Brams, Feldman, Lai,Morgenstern and Procaccia^[7] study both envy-free (EF) andequitable (EQ) cake divisions, and relate them to maxsum and Pareto-optimality (PO). As explained above, maxsum allocations are always PO. However, when maxsum is constrained by fairness, this is not necessarily true. They prove the following:

• When there are two agents, maxsum-EF, maximum-EQ and maximum-EF-EQ allocations are always PO.
• When there are three or more agents withpiecewise-uniform valuations, maxsum-EF allocations are always PO (since EF is equivalent toproportionality, which is preserved under Pareto improvements). However, there may beno maxsum-EQ and maxsum-EQ-EF allocations that are PO.
• When there are three or more agents withpiecewise-constant valuations, there may be even no maxsum-EF allocations that are PO. For example, consider a cake with three regions and three agents with values:

Alice	51/101	50/101	0
Bob	50/101	51/101	0
Carl	51/111	10/111	50/111

The maxsum rule gives region i to agent i, but it is not EF since Carl envies Alice. Using a linear program, it is possible to find the unique maxsum-EF allocation, and show that it must share both region 1 and region 2 between Alice and Bob. However, such allocation cannot be PO since Alice and Bob could both gain by swapping their shares in these regions.

• When all agents havepiecewise-linear valuations, the utility-sum of a maxsum-EF allocation is at least as large as a maxsum-EQ allocation. This result extends to general valuations up to an additive approximation (i.e.,ε-EF allocations have a utility-sum of at least EQ allocations −ε).

When the pieces may bedisconnected, the absolute-utilitarian rule (maximizing the sum of non-normalized utilities) isresource-monotonic andpopulation-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 areconnected.^[9]

• 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.

• Cake-cutting
• Utilitarianism