All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Game Theory on dividing cakes (Posted on 2004-12-27)
A well-known method of dividing a cake between two people is to have the first person to cut the cake and have the second person to have the first pick. This will guarantee that the first person will cut the cake in half so that the second person cannot leave him with a smaller piece.

Now we want to divide the cake among n people. Let's make the following assumptions:
(a) Each person cannot cut the cake more than once
(b) Everyone is logical
(c) Everyone wishes to get the largest possible piece
(d) Everyone wishes to narrow the gap with those who have a bigger piece than he does
(e) No one cares about anyone who has a smaller piece than themselves.

Can you generalize the strategy to n people? Give your logical steps/proof that this strategy will yield a fair result.

 See The Solution Submitted by Bon Rating: 1.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Fair cuts... | Comment 7 of 8 |

This works equally well for 1 designated cutter or for multiple cutters.

For simplicity of explaining the process, assume the cake is long and narrow:

The cutter (single designated or rotationally determined) holds the knife at one end of the cake and starts moving it towards the other end in a way that the cut will be perpendicular to the length of the cake (it does not need to be perfectly perpendicular).  At any point that one of the people without a piece thinks that the piece betwen the end of the cake and the current knife position is 'fiar' or larger than 'fair' they call out and the cake is cut at that position and the person who called out gets that piece.  The next cutter takes the knife and starts from the previous cut and moves the knife slowly towards the other end of the cake.  anyone without a piece can call out when they like the size of the piece about to be cut.  This process continues until only two people remain then the process resorts to the 'you cut, I choose' method.

Incidentally, this process works equally well for cakes which may not be uniformly designed, such as cakes which are decorated with extra icing, flowers, candies, etc.

For round cakes you could make an initial cut and move the knife rotationally, or you could resort to cutting parallel slices.  The method also lends itself well to odd shaped cakes.

 Posted by Erik O. on 2004-12-28 18:04:53

 Search: Search body:
Forums (0)