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)
- Player 1 cut the cake in 3 fair pieces.
- Player 2 picks one of the 3 pieces (b).
- 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.
- Player 1 gets the remaining piece.
Now, we can also extend this into a 4 player game: (N=4)
- Player 1 cut the cake in 4 fair pieces.
- 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.
- 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?