Utilitarian cake-cutting

Utilitarian 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. The rule says that the cake should be divided in a way which maximizes the sum of the utilities of the partners. It is called "utilitarian" because it is inspired by utilitarianism. An alternative term is maxsum cake-cutting.

Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is 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:

Header text	Chocolate	Vanilla
Alice	9	1
George	6	4

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

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

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

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

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

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

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

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

Utilitarianism and Pareto-efficiency

Every WUM division with positive weights is obviously Pareto-efficient. This is because, if a division $Y$ Pareto-dominates a division $X$ , then the weighted sum-of-utilities in $Y$ is strictly larger than in $X$ , so $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.
Indepencence 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 $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 $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-maximal divisions

Disconnected pieces

When the value functions are additive, utilitarian-maximal 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 $V_{i}/w_{i}$ is largest.

This process is easy to carry out when the value functions are piecewise-constant, 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 people.

What happens when the value functions are general (not piecewise-constant)? Then, the simple procedure of "give each piece to the one which wants it the most" does not work because there is an infinite number of different "pieces" to consider.

The good news is that UM divisions still exist. This is a corollary of the Dubins–Spanier compactness theorem and it can also be proved using the Radon–Nikodym set.

The bad news is that no finite algorithm can find a UM division. Proof:^[3] 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 $k$ 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 $k$ pieces, there is a subset which two partners value differently. In this case, there exists a super-proportional division, in which each partner receives a value of more than $1/n$ , 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 when the pieces are piecewise-constant. In this case, the problem of finding a UM division is NP-hard, and furthermore no FPTAS is possible unless P=NP.

There is a 8-factor approximation algorithm, and a fixed-parameter tractable algorithm which is exponential in the number of players.^[4]

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

Utilitiarianism vs. fairness

A utilitarian division is not always fair; see the #Example. Similarly, a fair division is not always utilitarian-maximal. Fairness comes with a price-tag: the price of fairness is the amount of welfare that society has to "pay" in order to maintain the ideal of fairness.

One approach to combining utilitarianism and fairness is to find, among all possible fair divisions, a fair division with a highest sum-of-utilities. In particular, the following algorithm is 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:^[5]

For $n$ partners with piecewise-constant valuations: create a set of totally constant pieces. solve a set of linear equations. Give each partner a fraction of each totally constant piece.
For $2$ partners with piecewise-linear valuations: for each point in the cake, calculate the ratio between the utilities: $r=u_{1}/u_{2}$ . Give partner 1 the points with $r\geq r^{*}$ and partner 2 the points with $r<r^{*}$ , where $r^{*}$ is a threshold calculated so that the division is envy-free. In general $r^{*}$ cannot be calculated because it might be irrational, but in practice, when the valuations are piecewise-linear, $r^{*}$ can be approximated by an "irrational search" approximation algorithm.
For $n$ partners with general valuations: additive approximation to envy and efficiency, based on the piecewise-constant-valuations algorithm.

See ^[6] for further discussion of these results relating them to equitable division.

References

↑ Barbanel, Julius B.; Zwicker, William S. (1997). "Two applications of a theorem of Dvoretsky, Wald, and Wolfovitz to cake division". Theory and Decision. 43 (2): 203. doi:10.1023/a:1004966624893. . See also Weller's theorem. For a similar result related to the problem of homogeneous resource allocation, see Varian's theorems.
↑ Chambers, Christopher P. (2005). "Allocation rules for land division". Journal of Economic Theory. 121 (2): 236. doi:10.1016/j.jet.2004.04.008.
↑ Brams, Steven J.; Taylor, Alan D. (1996). Fair Division [From cake-cutting to dispute resolution]. p. 48. ISBN 0521556449.
↑ Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Computing Socially-Efficient Cake Divisions. AAMAS.
↑ Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Optimal Envy-Free Cake Cutting. AAAI.
↑ Steven J. Brams; Michal Feldman; John K. Lai; Jamie Morgenstern; Ariel D. Procaccia (2012). On Maxsum Fair Cake Divisions. Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12). pp. 1285–1291. Retrieved 6 December 2015.

This article is issued from Wikipedia - version of the 6/6/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.