Cake Cutting

Everyone loves cake and wants to get as much of it as they can. Alice and Bob are trying to decide how to fairly share a cake, but they don't have any measuring equipment. How can they divide it so that both people are happy with what they end up with?

This two person case is well known and is solved with the strategy of “you cut, I'll choose”. Alice starts by cutting the cake into two pieces which she thinks are equal and then Bob chooses which piece he would like. Crucially if either player gets what they think is less than half then they only have themselves to blame. Either Alice didn't manage to cut the cake into what she thought of as equal pieces, or Bob purposefully picked the wrong piece. They key is that both players (er… party goers) are happy with their cut even though there is no guarantee that they actually half exactly half of the cake.

Things get more complicated when you start adding in more people. At the next party Alice and Bob decided that they should really start inviting more people and so they call Carol. There is a new cake and again they are trying to get as much cake as possible.

Let's just look at an obvious, but failed attempt. Alice cuts what she thinks are thirds, so she will be happy with any result. But now if Bob picks, he may take what Carol thinks is by far the biggest piece and so she may be left with a choice of only two, both of which she thinks are smaller than her fair share.

We need to bodge this slightly by allowing the later players to shave off pieces of cake to cut them down to size. So this time Alice cuts what she thinks is a third. Bob assesses the piece and if he thinks it is bigger than a third he shaves a bit off and adds the shavings back to the main cake. He then passes the slice to Carol who may also shave some off cake. The idea is that the last person to cut any off the slice gets to keep it. If no one shaves any then the originally cutter, Alice gets it. Once one person is sorted you can have the remaining two do the I cut you choose method.

But all of that is quite complicated and although you can scale it for when the group extends to Daniel and Eve and … etc. you end up with lots of shavings. Clearly we need a more generalised system. Here is the simplest and that is the beauty of it. It's called the travelling knife solution. Start by making a radial cut in the cake (you can adapt this method for non-circular cakes). Then you hold the knife above the cake and slowly more the knife around, tracing out a larger and larger slice. Whoever shouts “CUT!” first gets the piece. Then the process is started again. For n people the optimum strategy for logical people is to shout out as soon as you think the slice is 1/n of the cake. You may do better than that if you disagree with the other players’ evaluations. What this algorithm lacks is that it isn’t free from envy.

Let's say there are 10 people and you give the command first getting what you think is a fair piece. Then most of the other people play, but do so suboptimally in your opinion, leaving the last player with a bigger piece than yours. The algorithm has delivered everyone a piece of cake that they think is at least 1/10th of the cake and yet some players may not feel that they got the best piece. There are algorithms that can achieve this, but they pay for it by being more complicated.