1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dorus Jul 24 '15 at 12:04
  • 1
    $\begingroup$ @Dorus: Apparently this is called proportional division. See also fair cake-cutting for the problem that proportional and envy-free divisions are special cases of. Regarding your après-share solution, I wonder what the point is to design an envy-free division procedure among cooperating players :-) $\endgroup$ – joriki Jul 24 '15 at 12:18
  • $\begingroup$ Ah, that is a good link to look at. Thanks. My goal was to ensure two cooperating players can not claim more than 2/3th of the cake. That is still a stronger condition than just the requirement that the majority of the players is happy with the end result (player two and three both take half, and run away with the whole cake because they also have the majority of the votes together). $\endgroup$ – Dorus Jul 24 '15 at 13:15
  • $\begingroup$ @Dorus: I've never seen such a majority requirement -- it seems too easy to fulfill to make for an interesting problem. $\endgroup$ – joriki Jul 24 '15 at 13:21
  • $\begingroup$ It's more of a non-requirement. It shouldn't be possible to happen, yet some systems accidentally allow it. Proportional division is a much better property in that regard. $\endgroup$ – Dorus Jul 24 '15 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.