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.
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.
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.
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.
What's more surprising is that every Pareto-efficient division is WUM for some selection of weights.
[1] Christopher P. Chambers suggests a characterization to the WUM rule.
[2] The characterization is based on the following properties of a division rule R: The following is proved for partners that assign positive utility to every piece of cake with positive size: 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
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.
I.e. there is only a finite number of subsets of the cake, for which the algorithm knows the valuations of the partners.
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.
In this case, there exists a super-proportional division, in which each partner receives a value of more than
In this case, the problem of finding a UM division is NP-hard, and furthermore no FPTAS is possible unless P=NP.
[5] For every set of positive weights, a WUM division exists and can be found in a similar way.
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.
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 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:[6] Brams, Feldman, Lai, Morgenstern and Procaccia[7] study both envy-free (EF) and equitable (EQ) cake divisions, and relate them to maxsum and Pareto-optimality (PO).
They prove the following: The maxsum rule gives region i to agent i, but it is not EF since Carl envies Alice.
However, such allocation cannot be PO since Alice and Bob could both gain by swapping their shares in these regions.
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.