A brief personal survey of "fair cake division" mathematics

Warren D. Smith, Oct. 2016

A compromise is the art of dividing a cake in such a way that everyone believes he has the biggest piece. – Ludwig Erhard (1897-1977; Erhard was Chancellor of the Federal Republic of Germany 1963-1966).

2-player problem: Suppose you have a cake and two obnoxious children who want to eat it.

1-cut solution: A well known way to cut a cake into two pieces that assures that each person gets at least half of the value of the cake (where the two players may value different cake-parts differently, e.g. one likes chocolate and another likes cherries) is the "cut and choose" protocol where player A cuts the cake and then player B chooses his piece.

3-player problem: Can we devise a similar protocol for three cake-eating players assuring each will regard his/her piece as containing at least as much value as either one of the others?

5-cut solution (John L. Selfridge & John H. Conway in about 1960):

1. Amy cuts the cake into what she regards as equal thirds. (2 cuts.)
2. Bob trims (what he regards as) the biggest piece, to create (what he regards as) a two-way tie for largest. (1 cut.) The trimming is set aside.
3. Cal picks a piece, then Bob, then Amy, with the asterisk that Bob must take the trimmed piece if Cal didn't. Call the person who took the trimmed piece T, and the other (of Bob and Cal) N.
4. At this point, no player envies any other – but the trimming still has not been divided.
5. To deal with the trimming, N cuts it into what he thinks are thirds. (2 cuts)
6. The players pick pieces in this order: T, Amy, N. (In all, 5=2+1+2 cuts.)

N-player problem: Can we devise a similar protocol for N cake-eating players assuring each will regard his/her piece as containing at least as much value as anybody else's?

To learn more about such fair cake-cutting protocols, read the enjoyable book

Here and in their earlier [S.J.Brams & A.D.Taylor: Amer. Math'l. Monthly 102,1 (Jan. 1995) 9-18] they show that a finite number of steps suffice for any number N of players, but if N>3 then the number of steps required by their methods may not be a function of N alone – it may also depend on the structure of the cake (but it will always be finite for any particular N and any particular cake).

Another book on this is

Robertson and Webb invented procedures whereby each player would actually get a piece strictly better (in his own estimation) than anybody else's, provided that such a division exists (which happens if and only if the players' cake-valuing measures are linearly independent).

A standard 1-dimensional setting for the problem: Robertson and Webb also pointed out (more or less) that the cake, without loss of generality, can be regarded as the standard unit length line-segment [0,1] – since we can bijectively map this to any higher-dimensional compact set using a space-filling curve – and then we may demand each "cut" be the removal of a single point from (disconnecting) that line segment. In this standard 1-dimensional setting we can enquire what the minimum number of needed cuts are, for N-player envy-free cake division.

If the "envy-free" requirement is dropped, i.e. we merely want to devise a "proportional" protocol assuring that every player feels he has at least 1/N of the cake (measured by his own measure, where there are N players), then the problem is easy to solve for any N:

"Last-diminisher" protocol of Banach & Knaster (≈1940): Have player 1 cut the cake into two, player 2 chooses a piece, players 3,...,N successively then diminish that piece (or not), and the "last diminisher" is forced to take the piece he last diminished. Then that player is eliminated and the rest of the cake is re-assembled, at which point we solve the problem again, but now with only N-1 players. (When we reach N=2, the usual cut-and-choose protocol is employed.) That process uses at most (N-1)N/2   cuts.

Even-Paz optimal protocol: [Shimon Even & Azaria Paz: A note on cake-cutting, Discrete Applied Mathematics 7 (1984) 285-296] showed how to speed that up to ≤2(N+1)(L-2.125)+7.08233 cuts, where L=log₂(N), for all N≥4:

1. If N is odd, then apply the above "last diminisher" procedure to eliminate one of the players and thus decrement N. (That took at most N-1 cuts.) We now may assume N is even.
2. Each player is asked to cut the cake into two pieces that he considers of equal value. (1 cut per player, hence N in all.)
3. The algorithm sorts the N cuts into increasing order and cuts the cake at anyplace between the two bimedians, if N is even). E.g, if there are N=4 players who cut at x=0.1, x=0.2, x=0.4 and x=0.5, then the algorithm cuts the cake at x=0.3. (This is 1 additional cut, which strictly speaking is not needed since it is permissible to use one of the two bimedians itself.)
4. The algorithm assigns to each of the two halves the N/2 players – those whose cut lies inside that half. E.g, the players who cut at x=0.1 and x=0.2 are assigned to the western half and the other two to the eastern half.
5. Each half is divided recursively among the N/2 players assigned to it.

If the Even-Paz protocol requires F(N) cuts, then evidently F(1)=0, F(2)=1, and special methods are known [William A. Webb: How to cut a cake fairly using a minimal number of cuts, Discrete Applied Maths 74,2 (April 1997) 183-190] showing F(3)≤3, F(4)≤4, F(5)≤6, and F(6)≤8 (Webb shows these are best possible for each N≤5); and from then onward we may apply the recurrences that if N≥3 is odd then F(N)≤N-1+F(N-1), while if N≥3 is even then F(N)≤N+2F(N/2). I find the resulting upper bound on F(N) is upper bounded by 2(N+1)(L-2.125)+7.08233 where L=log₂(N) for all N≥4.

[Gerhard J. Woeginger & Jiri Sgall: On the complexity of cake cutting, Discrete Optimization 4,2 (2007) 213-220] then showed the Even-Paz protocol's O(NlogN) bound was (up to the constant factor in the "O") best-possible for any protocol guaranteeing proportionality and whose cake pieces (in the standard 1D model) always were connected. Even & Paz's protocol obeys this connectedness demand. But see also Sgall & Woeginger: An approximation scheme for cake division with a linear number of cuts, Combinatorica, 27,2 (2007) 205-211. And then [Jeff Edmonds & Kirk Pruhs: Cake cutting really is not a piece of cake, ACM Transactions on Algorithms 7,4 (Sept. 2011) 1-12] showed the Woeginger-Sgall Ω(NlogN) lower bound worked even (i) for protocols merely guaranteeing "approximate fairness" and (ii) not anymore demanding the cake-pieces be connected sets. Thus the proportional cake-cutting problem is quite well solved, in the sense that known upper and lower bounds on the number of cuts needed, match to within a small constant factor.

As of 2014, the following question remained open: For which N is there a cut-and-choose N-player envy-free cake cutting protocol that runs in at most some function of N steps regardless of the structure of the cake? (Indeed, nobody knew any 4-player envy-free cake-cutting protocol that ends after at most a fixed number of steps.)

Allegedly solved (2015-2016)! In an impressive theoretical breakthrough, Haris Aziz & Simon Mackenzie: A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents (2016) claimed to find such a protocol for every N. However it remains totally impractical at least as far as their worst-case guarantee is concerned, since they found the astonishingly huge bound

on the number of "cake cuts" made during their protocol. It's really amazing if this really is approximately the best answer. Even with N=2 this bound on F(2) has over 6×10¹⁹⁷²⁷ decimal digits. (That is far too many digits even to write down this number fitting it within the observable universe!)

There is a rumor that Aziz & Mackenzie think they know how to reduce their upper bound to F(N)≤N^NN. Even if that rumor is true, though, this improved bound remains insanely impractical, e.g. it would show F(4)≤2⁵¹² and F(5)≤5³¹²⁵ which both are far more cuts than the number of atoms in any cake (even if the "cake" were the entire observable universe).

But for the special case N=4, Aziz & Mackenzie in 2015 found a special protocol requiring at most 203 cuts.

Lower bounds for envy-free N-player cake cutting: [Ariel D. Procaccia: Thou Shalt Covet Thy Neighbor's Cake, Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009) 239-244; Cake-cutting, not just child's play, Commun. of the ACM 56,7 (2013) 78-87] showed an Ω(N²) lower bound for envy-free N-player cake-cutting, which note is greater than the Woeginger-Sgall-Edmonds Ω(NlogN) lower and Even-Paz O(NlogN) upper bounds for merely-proportional cake-cutting but still is vastly below the Aziz-Mackenzie alleged upper bound.

I point out, however, that there is good reason to believe, at least under the Woeginger-Sgall "all pieces must be connected" demand, that at least about (2N)^N-2 cuts are needed to achieve even approximate envy-freeness. My "reason" consists of two ingredients:

1. The Simmons-Su connection was the observation by Forest Simmons in 1980 that the N-player 1-dimensional cake-cutting problem (with connected-pieces constraint) could trivially be rewritten as a problem of finding a fixpoint of a selfmap of an (N-1)-dimensional simplex.

   "Brouwer's fixpoint theorem" says that such a point always exists, which was Simmons's proof that an envy-free cake cutting meeting the connected-pieces demand always exists for every N and every cake, provided each of the N players values the cake with their own nonsingular positive measure. (More precisely, any cake-subset valued positively by any player, is valued positively by every other.) And to read a beautiful proof of Brouwer's fixpoint theorem, see chapter 21 of Martin Aigner & Günter M. Ziegler: Proofs from the book, Springer, which also shows (basically) that an ε-approximately-envy-free cake cutting may be found, arising from an ε-approximate fixpoint, in ε^2-N steps if N≥3.

2. The fact that finding a Brouwer fixpoint (for any N players' given polynomial-time cake-valuing functions) is a PPAD-complete problem, which therefore conjecturally is impossible to solve faster than about ε^2-N steps to ε approximation, and exactly-envy-free cake-cutting presumably is as least as hard as the ε-approximate problem with ε=(2N)^-1 with possibly-harder-than-polynomial-time cake-valuing functions.

I doubt that relaxing the all-pieces-connected demand makes it any easier (and it seems likely this can be proven by an extension of the PPAD-completeness proof). Proving any superpolynomial lower bound won't be possible until fundamental barriers in computational complexity are overcome.

Later note: my same observations about the Simmons-Su connection and PPAD-completeness were already made by [Xiaotie Deng, Qi Qi, Amin Saberi: Algorithmic Solutions for Envy-Free Cake Cutting, Operations Research 60,6 (2012) 1461-1476].

N-player exactly-envy-free cake-cutting status as of 2016:

F(1)=0,
F(2)=1 ["cut and choose"],
F(3)≤5 [Selfridge & Conway, probably best possible],
F(4)≤203 [Aziz & Mackenzie 2015],
and F(N) is bounded by the "tower of six N's" function for every N≥1 [Aziz & Mackenzie 2016]. According to a rumor, that upper bound might improve to a mere N^NN or so. I conjecture a lower bound behaving something like (2N)^N-2.

Approximately envy-free cake cutting: Aziz & Mackenzie also showed "that an envy-free partial allocation can be computed in N^N+1 steps such that each agent gets a connected piece that gives the agent at least 1/(3N) of the value of the whole cake (by her own value-measure)."

If we do that L times (each time allocating the unallocated part of the cake left over from previous iterations), then the unallocated part of the cake will have value≤[1-1/(3N)]^L of the value of the whole cake (by any player's reckoning). This is exponentially small, e.g. if L≥3Nk then the unallocated cake's value will be ≤exp(-k) of the value of the whole cake. Hence, for example, even if the cake were the entire Earth, using L≥357N would assure that the unallocated part (if somebody's measure were "mass") would be well below the mass of 1 atom. Even if the cake were the entire observable universe, using L≥646N would assure that the unallocated part (if somebody's measure were "mass") would be below the mass of each presently-known elementary particle. Further, keep in mind that real-life obnoxious children are incapable of cutting a cake exactly in half. They probably cannot even achieve 1% accuracy. In view of that, for all practical purposes exactly envy-free protocols are pointless. Any protocol capable of achieving accuracy ε with work proportional to |log(ε)| is good enough. The method we just described assures all envies≤ε in ≤3N^N+2|lnε| steps. This is of the same order – up to factors of form polynomial(N)×SimpleExponential(N) – as the putative lower bound (from the Simmons-Su connection and PPAD-completeness) on N-player envy≤ε cake division, i.e. likely is approaching best possible efficiency.

Even this is, however, highly impractical. For example, suppose the number of players is N=47, and we want ε=0.001 accuracy about the envy-freeness. Well, that would require >10⁸⁰ steps, which happens to approximate the number of protons in the observable universe.

But there is reason to believe it is impossible to do much better.

The "societally best" envy-free cake-cutting? S.J.Brams in correspondence was unhappy with the above. First of all, the cake is going to be cut into an absurdly enormous number of pieces. But aside from that, the cake-division it produces is likely to be "improvable" in the sense that some rival division would also be envy-free, but would be regarded by every player as just as good for them, or better (with at least one considering it better). A societally best envy-free cake division will mean one maximizing the sum of the personal values, to each player, of their cake-pieces.

Fact: societally-best envy-free cake divisions are unimprovable.

Fact: If the number of players is 2, then the societally-best envy-free cake division is essentially unique. Here by "essentially" I mean that there may be some subset S of the cake, not wholy owned by any one player, such that both players regard S as having constant value-density (albeit the two player's constants might differ). Hence as far as the two players are concerned, any way to divide S into two parts giving fraction F to the first and fraction 1-F to the second player is equivalent to any other. The cake division will, however, uniquely divide the rest (non-S) of the cake.

Societally-best envy-free cake divisions always exist for any number N≥1 of players. The question is how to find them (or approximate them) – or as an easier problem, how to find or approximate unimprovable envy-free cake divisions.

Impossibility Theorem (W.D.Smith 2016): No protocol in the "cut, value, and choose" model is capable of guaranteeing an unimprovable envy-free cake division, nor even one the players agree is not improvable by more than ε, not even if the number of players is N=2 and ε=0.166.

Proof: Let the "cake" be the unit square 0≤X≤1, 0≤Y≤1 in the XY plane. Let the two players have utility-density functions 2X and 2Y. The unique optimum (societally best) cake-division is to cut the cake along the diagonal line X=Y. This causes each player to get 2/3 of the cake (in her own reckoning). However, suppose every time the protocol asks the players to cut anything the players always cut along a perpendicular line (of form X+Y=C for some C the player chooses for that occasion). The players certainly are allowed to behave this way in our model. If they do, then the cake division that results, although it can be (and with a valid protocol will be) envy-free, will always be improvable, and indeed because of mirror symmetry (about the mirror-line X=Y) each player will necessarily regard themselves as getting exactly 1/2 of the cake. Q.E.D.

In view of this impossibility theorem, we can only hope to achieve societally-best or unimprovable envy-free cake-cuttings (even ε-approximately) in some extension of the "cut, value, and choose" model. Here is a suggested possible extended model:

Extension: The protocol can specify two players A and B, and a cake-piece, and demand that they divide that piece in what would be the societally-optimal manner if all other players besides A and B were ignored.

Further Extension: The protocol can specify two players A and B, and positive integers X, Y, and a cake-piece, and demand that A & B divide that piece in what would be the societally-optimal manner if all other players besides A and B were ignored and if player A got X copies of her piece while B got Y copies of his.

Question: In these extended models, do protocols exist which assure delivering N-player cake divisions in which all envies are ≤ε and all improvabilities are ≤ε?

I conjecture the answer is "yes" and have a protocol that I believe works. Essentially, it divides up the cake into (what all players agree are) small pieces, and then has all players value all pieces, and then uses "integer programming" to deal out the pieces to the players in the manner minimizing the maximum ε. It looks fairly clear this can be made to work if all the measures are smooth enough; the difficulty for anybody trying to prove or disprove this will be to make their argument work in a wholy-abstract setting involving arbitrary nonsingular measures which might be based on, e.g, nowhere-differentiable functions or value-densities which can go infinite.

Return to puzzle page

Return to main page