# Is my cake split envy-free (and coalition-resistant)?

I once read that splitting a cake in 4 parts envy-free is notoriouse difficult. Not to mention splitting it with 5 or more people. Methods involve arbitrarily long recursions and cake split onto molecular scale.

I was thinking about the Selfridge–Conway discrete procedure and came up with a simpler solution: (N=3)

1. Player 1 cut the cake in 3 fair pieces.
2. Player 2 picks one of the 3 pieces (b).
3. Player 3 picks one of the 3 pieces (either b or another piece, c).
• a) If they both pick the same, player 2 cut off a part from b (namely b2) so that b1 and c are of equal size.
• b) Player 3 can then switch and player 2 keeps b1, or player 3 keeps b1 and player 2 takes another piece.
• c) Piece b2 gets divided by the N=2 algorithm: Player 3 cut it, and Player 2 takes the first piece.
4. Player 1 gets the remaining piece.

Now, we can also extend this into a 4 player game: (N=4)

1. Player 1 cut the cake in 4 fair pieces.
2. Player 2, 3 and 4 each pick a piece.
• a) If 2 players pick the same piece, repeat the sub-procedure from N=3. If a player switch to a piece already claimed, repeat but do not allow to switch to a piece he already has a claim on.
• b) If 3 players pick the same piece (b), player 2 cut off a part from it (namely b2) so that b1 and the largest remaining piece (a, c or d) is of equal size.
• c) Player 3 and 4 can then switch to one of the other pieces. If at least one of them does not switch, player 2 must switch.
• d) If again 2 players have a claim on the same piece, use sub-procedure from N=3 but disallow switching back to b.
• e) Piece b2 gets divided by the N=3 algorithm over player 2, 3 and 4.
3. Player 1 gets the remaining piece.

(It is probably a good idea to let another player cut every time, but not even required)

The advantage of this method is that it require a minimal number of cuts, as soon as the players agree two pieces are equal, those two will not be cut up again. Also the algorithm ends quickly, because each time a piece is re-cut, either the player that cut it is done, or the player that switch loses the claim on that piece.

We can extend this into 5 players as well, but lets focus on the 4 player game. Is this solution envy-free?

Already your $N=3$ procedure isn't envy-free. You seem to be solving the problem of making sure that each player gets at least $1/N$ of the cake (in their estimation). That's a weaker condition than "envy-free", which requires that the players also don't think that anyone else got more than them.
In your procedure, player $1$ makes $3$ equal pieces and in the end receives one of them, but the other two pieces are subdivided and shuffled between the other two players – since this part of the procedure doesn't involve player $1$, there's nothing to ensure that player $1$ will still regard the other two players' shares as equal.
• Oh right. Didn't think of is like that yet. Does this weaker condition have a name? For most cases the players will be more than happy with a guaranteed $1/N$ share, after all two cooperating players can always donate there share to the other after the algorithm completes. – Dorus Jul 24 '15 at 12:04