Fair cake-cutting

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogenous resource, such as a cake with different toppings, that is assumed to be divisible – it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The division should be subjectively fair, i.e., each person should receive a piece that he/she believes to be a fair share.

The "cake" is only a metaphor; Procedures for fair cake-cutting can be used to divide various kinds of resources, such as land estates, advertisement space or broadcast time.

The cake-cutting problem has been introduced by Hugo Steinhaus after World War II[1] and is still the subject of intense research in mathematics, computer science, economics and political science.

Assumptions

There is a cake C, which is usually assumed to be either a finite 1-dimensional segment, a 2-dimensional polygon or a finite subset of the multidimensional Euclidean plane Rd.

There are n people with equal rights to C.[2]

C has to be divided to n disjoint subsets, such that each person receives a disjoint subset. The piece allocated to person i is called Pi, and C = P_1 \sqcup \cdots \sqcup P_n.

Each person should get a piece with a "fair" value. Fairness is defined based on subjective value functions. Each person i has a subjective value function Vi which maps subsets of C to numbers.

All value functions are assumed to be absolutely continuous with respect to the length, area or (in general) Lebesgue measure.[3] This means that there are no "atoms" – there are no singular points to which one or more agents assign a positive value, so all parts of the cake are divisible.

Additionally, in some cases the value functions are assumed to be sigma additive (the value of a whole is equal to the sum of the values of its parts).

Example cake

In the following lines we will use the following cake as an illustration.

Justice criteria

The original and most common criterion for justice is proportionality (PR). In a proportional division, each person receives a piece that he values as at least 1/n of the total value. In the example cake, a proportional division can be achieved by giving all the vanilla and 4/9 of the chocolate to George (for a value of 6.66), and the other 5/9 of the chocolate to Alice (for a value of 5). In symbols:

\forall{i}:\ V_i(P_i)\geq 1/n

The proportionality criterion can be generalized to situations in which the rights of the people are not equal. For example, the cake belongs to shareholders such that one of them holds 20% and the other holds 80% of the cake. This leads to the criterion of Weighted proportionality (WPR):

\forall i:\ V_i(P_i)\geq w_i

Where the wi are weights that sum up to 1.

Another common criterion is envy-freeness (EF). In an envy-free division, each person receives a piece that he values at least as much as every other piece. In symbols:

\forall i,j:\ V_i(P_i)\geq V_i(P_j)

In some cases, there are implication relations between proportionality and envy-freeness, as summarized in the following table:

Agents Valuations EF implies PR? PR implies EF?
2 additive yes yes
2 general no yes
3+ additive yes no
3+ general no no

A third, less common criterion is equitability (EQ). In an equitable division, each person enjoys exactly the same value. In the example cake, an equitable division can be achieved by giving each person half the chocolate and half the vanilla, such that each person enjoys a value of 5. In symbols:

\forall i,j:\ V_i(P_i) = V_j(P_j)

A fourth criterion is exactness. If the entitlement of each partner i is wi, then an exact division is a division in which:

\forall{i,j}:\ V_i(P_j) = w_j

If the weights are all equal (to 1/n) then the division is called perfect and:

\forall i,j:\ V_i(P_j) = 1/n

Additional criteria

In addition to justice, it is also common to consider the economic efficiency of the division; see Efficient cake-cutting.

In some cases, the pieces allocated to the partners must satisfy some geometric constraints, in addition to being fair.

In addition to the desired properties of the final partitions, there are also desired properties of the division process. One of these properties is truthfulness (aka incentive compatibility), which comes in two levels.

Results

2 people – proportional and envy-free division

For n = 2 people, an EF division always exists and can be found by the Divide and choose protocol. If the value functions are additive then this division is also PR; otherwise, proportionality is not guaranteed.

Proportional division

Main article: Proportional division

For n people with additive valuations, a PR division always exists. Moreover, a weighted proportional division is also guaranteed to exist for every set of weights (Corollary 1.1 of [5]).

The most common protocols for unweighted PR division are:

None of the protocols described above guarantees that the division is envy-free.

Envy-free division

An EF division for n people exists even when the valuations are not additive, as long as they can be represented as consistent preference sets. EF division has been studied separately for the case in which the pieces must be connected, and for the easier case in which the pieces may be disconnected.

For connected pieces the major results are:

Both these algorithms are infinite: the first is continuous and the second might take an infinite time to converge. In fact, envy-free divisions of connected intervals to 3 or more people cannot be found by any finite protocol.[8]

For possibly-disconnected pieces the major results are:

The negative result in the general case is much weaker than in the connected case. All we know is that every algorithm for envy-free division must use at least Ω(n2) queries.[9] There is a large gap between this result and the fact that all known algorithms are unbounded.

Efficient division

When the value functions are additive, UM divisions exist. Intuitively, to create a UM division, we should give each piece of cake to the person that values it the most. In the example cake, a UM division would give the entire chocolate to Alice and the entire vanilla to George, achieveing a utilitarian value of 9 + 4 = 13.

This process is easy to carry out when the value functions are piecewise-constant, i.e. the cake can be divided to pieces such that the value density of each piece is constant for all people. When the value functions are not piecewise-constant, the existence of UM divisions is based on a generalization of this procedure using the Radon–Nikodym derivatives of the value functions; see Theorem 2 of.[5]

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. 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.[10]

For every set of positive weights, a WUM division can be found in a similar way. Hence, PE divisions always exist.

Efficient fair division

For n people with additive value functions, a PEEF division always exists.[11]

If the cake is a 1-dimensional interval and each person must receive a connected interval, the following general result holds: if the value functions are strictly monotonic (i.e. each person strictly prefers a piece over all its proper subsets) then every EF division is also PE.[12] Hence, Simmons' protocol produces a PEEF division in this case.

If the cake is a 1-dimensional circle (i.e. an interval whose two endpoints are topologically identified) and each person must receive a connected arc, then the previous result does not hold: an EF division is not necessarily PE. Additionally, there are pairs of (non-additive) value functions for which no PEEF division exists. However, if there are 2 agents and at least one of them has an additive value function, then a PEEF division exists.[13]

If the cake is 1-dimensional but each person may receive a disconnected subset of it, then an EF division is not necessarily PE. In this case, more complicated algorithms are required for finding a PEEF division.

If the value functions are additive and piecewise-constant, then there is an algorithm that finds a PEEF division.[14] If the value density functions are additive and Lipschitz continuous, then they can be approximated as piecewise-constant functions "as close as we like", therefore that algorithm approximates a PEEF division "as close as we like".[14]

An EF division is not necessarily UM.[15][16] One approach to handle this difficulty is to find, among all possible EF divisions, the EF division with the highest utilitarian value. This problem has been studied for a cake which is a 1-dimensional interval, each person may receive disconnected pieces, and the value functions are additive.[17]

See also

References

  1. 1.0 1.1 Steinhaus, Hugo (1948). "The problem of fair division". Econometrica.
  2. I.e. there is no dispute over the rights of the people – the only problem is how to divide the cake such that each person receives a fair share.
  3. Hill, T. P.; Morrison, K. E. (2010). "Cutting Cakes Carefully". The College Mathematics Journal 41 (4): 281. doi:10.4169/074683410x510272.
  4. Chen, Yiling; Lai, John K.; Parkes, David C.; Procaccia, Ariel D. (2013). "Truth, justice, and cake cutting". Games and Economic Behavior 77 (1): 284–297. doi:10.1016/j.geb.2012.10.009.
  5. 5.0 5.1 5.2 Dubins, Lester Eli; Spanier, Edwin Henry (1961). "How to Cut a Cake Fairly". The American Mathematical Monthly 68: 1. doi:10.2307/2311357. JSTOR 2311357.
  6. "The Fair Division Calculator".
  7. Ivars Peterson (March 13, 2000). "A Fair Deal for Housemates". MathTrek.
  8. Stromquist, Walter (2008). "Envy-Free Cake Divisions Cannot be Found by Finite Protocols". The electronic journal of combinatorics.
  9. Procaccia, Ariel (2009). "Thou Shalt Covet Thy Neighbor’s Cake". IJCAI.
  10. Aumann, Yonatan; Dombb, Yair; Hassidim, Avinatan (2013). Computing Socially-Efficient Cake Divisions. AAMAS.
  11. Weller, D. (1985). "Fair division of a measurable space". Journal of Mathematical Economics 14: 5. doi:10.1016/0304-4068(85)90023-0.
  12. Berliant, M.; Thomson, W.; Dunz, K. (1992). "On the fair division of a heterogeneous commodity". Journal of Mathematical Economics 21 (3): 201. doi:10.1016/0304-4068(92)90001-n.
  13. Thomson, W. (2006). "Children Crying at Birthday Parties. Why?". Economic Theory 31 (3): 501. doi:10.1007/s00199-006-0109-3.
  14. 14.0 14.1 Reijnierse, J. H.; Potters, J. A. M. (1998). "On finding an envy-free Pareto-optimal division". Mathematical Programming 83: 291. doi:10.1007/bf02680564.
  15. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "The Efficiency of Fair Division". Theory of Computing Systems 50 (4): 589. doi:10.1007/s00224-011-9359-y.
  16. Aumann, Y.; Dombb, Y. (2010). "The Efficiency of Fair Division with Connected Pieces". Internet and Network Economics. Lecture Notes in Computer Science 6484. p. 26. doi:10.1007/978-3-642-17572-5_3. ISBN 978-3-642-17571-8.
  17. Cohler, Yuga Julian; Lai, John Kwang; Parkes, David C; Procaccia, Ariel (2011). Optimal Envy-Free Cake Cutting. AAAI.