The three-way cake division problem

Gideon asked:

This is a puzzle. I dont know if you could describe it as philosophical.

Here’s a fair way to cut a cake into two portions, one for A and one for B. A makes the cut and B chooses. So A has a reason to make the two halves the same size, otherwise B will take the bigger slice.

The question is, can you describe a similarly fair way to cut a cake into three portions, for A, B and C ?. If A cuts and chooses, then A can deliberately cut the cake so that B gets a bigger slice. Someone gets to make a cut, or possibly the first cut. Someone gets to choose the first slice, for him or herself or for someone else, and similarly with the second slice.

You’re not allowed to spin a coin or throw dice, or do any action that involves chance.

Can this be done, without either A, B or C having possible grounds for complaint?

Answer by Craig Skinner

Yes it can.

This is an example of a Fair Division Problem. Division is fair if it is proportional (each of n sharers gets 1/nth) and envy-free (no sharer feels that another gets a bigger share than she did).

I wouldn’t describe it as a specifically philosophical problem, but fair division is crucial, for instance, to (amicable) divorce settlements or territorial divisions/treaties, and so is of interest to lawyers, politicians, and negotiators, as well as to mathematicians/logicians who think up solutions.

Sometimes we are dealing with continuous goods (divisible into arbitrarily small pieces, as with cakes); sometimes with discrete goods (indivisible, as with cats or cars) where we have to come up with a metric for comparison.

You describe a fair 2-person division for continuous goods (one divider, one chooser).

The 3-. 4-, 5,- … n-person procedure is an extension of this in which we have one divider/several choosers (Lone Divider method), or one chooser/several dividers (Lone Chooser method), as well as a more complicated Last-Diminisher method.

Here is the simplest, Lone-Divider method:

A divides cake into three pieces, X, Y and Z.

B and C each states her choice:

  Case 1. B chooses X, C chooses Y (or vice-versa).

So, B and C get their chosen slice, A gets Z

  Case 2. B and C both choose X (or Y).

So, X (or Y) is merged with say Y (or X) and B/C do a 2-person divide-and-choose on XY.

A gets Z.

 

Answer by Ira Allen

This is simple, as long as nobody minds odd-shaped slices.

A, B, and C are sharing a piece of cake. A makes the first cut, which cannot entirely bisect the cake; B then makes as many cuts as are necessary to produce three pieces. C chooses her piece first, A second, and B third. Because B will choose last, she is incentivized to take whatever opening cut A has made and turn it into the most equitable arrangement. If she privileges C at A’s expense, she can expect that A will get her back by leaving her with the worst piece. Because A can only make a partial cut, not entirely bisecting the cake, and because B can make as many incisions as necessary to produce a total of three pieces, there is no way for A to privilege C at B’s expense.

The one possibility that this leaves open is that B will want, for whatever reason, to put A at a disadvantage – and will not mind being similarly disadvantaged herself. Shortsighted viciousness is hard to account for in any model, though it’s arguably one of the defining features of the human.

Most puzzles of this sort rely on a principle of incomplete lines, i.e., on lines (cuts, here) that do not entirely cross from side to side of the figure (here, the cake) to be divided.

 

2 thoughts on “The three-way cake division problem

  1. Ok, now I read Ira’s solution. I see this problem as a game theory problem. The game is a classic zero-sum game, and the goal is to design a protocol such that each player has a strategy ensuring she gets at least 1/3.

    In that sense, in Ira’s solution, A’s partial cut is completely irrelevant and has no impact whatsoever. A cannot guarantee himself anything more than 0. However, B’s best strategy is to cut the cake equally, so if she relies on B being rational A still gets 1/3. In the game theory sense, this is not solution that meets the criteria.

  2. Craig’s answer doesn’t explain how to choose the second piece to merge with in case 2.

    Ira’s answer depends on some joint cutting by A and B which not really well defined. I didn’t read it fully, though.

    Here’s a different suggestion:
    – Player A cuts a piece X (supposedly of size 1/3) and asks players B and C if they want it.
    – If both don’t want X, A gets X and B and C divide the rest between them the usual 2-way.
    – If B wants X and C doesn’t, then B gets X, and A and C divide the rest among them. (When C wants X it’s symmetrical)
    – If both B and C want X, they divide it among themselves, and now we need to divide the rest so that A gets 1/2, and B and C get 1/4:
    – – A cuts the rest into 2 pieces Y, and Z, and asks B and C if they want Y.
    – – If both of them want Y, they divide it between them and A gets Z. (If both want Z it’s symmetrical).
    – – If B wants Y and C want Z, B and A divide Y between them, and C and A divide Z between them. (If C want Y and B want Z it’s symmetrical).

    This solution generalizes to any number of players and many allocations of shares. The one who is allocated the largest share cuts his own slice and asks the other players if he can have it. If some of them want it, they share it among themselves (I won’t describe the share allocation here), otherwise the cutter gets it. The rest of the cake is then divided according to the updated shares, recursively.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s