Envy-Free Cake Division [Peer Review version]
Created | Updated Oct 31, 2007
It's a beautiful early summer's day, and you've been invited to take tea on the vicarage lawn. While you're busy sipping Earl Grey and discussing the Reverend's plant specimens, his wife offers you a plate containing a ready-sliced home-made chocolate sponge cake. It looks gorgeous, and, as a guest, you may choose the first slice! Unfortunately, you notice that it has not been divided equally. Maybe one slice is a little fatter, or contains an extra-large dollop of filling. Which do you go for?
In this particular social situation you may feel incumbent to take the least desirable slice; maybe the vicar will be thinking the same thing when it comes to his turn. To save the cringing embarrassment which the wrong choice could convey, you decide that it would be a better world if all slices were equally desirable to all parties, but that's not so easy to achieve.
On the other hand, maybe you are in a cake-choosing situation where selfishness and greed are the rules of the game. In this case, there's only one slice that will do, and that's the biggest. If you choose last, you get the smallest - it's unfair. Again, we need a way to divide our cake so that everyone is satisfied, but can it be done?
The Problem
It's easy if there are only two of us: I cut and you choose. When I cut, I carefully control the position of the knife so that either half of the cake is equally desirable to me. You can choose whichever piece you like; we are both satisfied. Alternatively, you could cut and then I choose - it makes no difference.
However, things get more complicated if there are three of us. Who cuts the cake, and who chooses first? What about the third person - do they have a say in things? In practice, there could be any number of cake eaters, so our method must reflect this.
Now, we could, of course, appoint an impartial referee to supervise the cutting and distribution, according to a previously-agreed set of rules. Maybe they would cut as geometrically accurate a set of slices as they can, or maybe they would weigh the cake, and then trim or augment each slice according to the calculated weight of an even portion. Either way, you get what you're given. You agreed the rules, so you can't complain, but there's always the nagging feeling that the decision has been taken out of your hands, isn't there? And did you ever meet a referee that didn't like cake? Can you really trust them? We need a method which will work without external influences and rules. One cake, one knife and a set number of eaters.
Cake and Mathematics
You may be surprised to hear that it's a problem which has engaged mathematicians for many years. There we were, thinking that they were beavering away in their institutes, developing the complex algebraic formulae which underpin new technological advances and engineering marvels. All the time they were sitting in the coffee lounge, eating cake.
They write papers about it, and publish them in highly-respected journals. For example, Walter Stromquist's 1980 article 'How to Cut a Cake Fairly' occupies pages 640-644 of The American Mathematical Monthly, Vol 87, No 8. To put it into context, it precedes Leon Gerber's 'Napoleon's Theorem and the Parallelogram Inequality for Affine-Regular Polygons'. We'll discuss Stromquists's method later.
The first published discussion of the topic was H Steinhaus's 'The Problem of Fair Division', which appeared in Econometrica in 1948. The methods have been refined and improved steadily over the years, and now there are hundreds of research papers and a fair few books on the subject, too. Perhaps we shouldn't be so surprised at this obsession; mathematicians did after all name one of their favourite curves after the blancmange.
All is Fair in Love, War and Cake
So, what do we actually mean by a fair division? Maybe it's fair if you can cut a cake so that each of five people, say, get what they believe to be one fifth of it. The aforementioned H Steinhaus's method relies on this definition, and works as follows:
One person starts by holding the knife above one edge of the cake. They slowly move the knife across the cake, such that the slice to be cut increases in size. At any time, a person can shout 'Cut!' when they believe it is large enough to be a fair portion. The knife stops, the cake is cut, and they get their slice. If two or more people shout 'Cut!' simultaneously then the slice is given to either of them. The process is repeated until all slices have been vocally claimed.
There are a couple of drawbacks with this method. First, there's a reliance on the hand holding the knife to instantaneously stop on the command 'Cut!', and then to cut the cake without wobbling or straying from that point. It might be a task better entrusted to an impartial referee, which brings with it all the associated issues of regulation and governance. Second, the method is not recommended for those taking a tea-break behind the scenes on a film set.
Peer Review
Another method, described by Martin Gardener in Scientific American, allows all the cake eaters to inspect each cut slice, to make sure it isn't too large:
Let's say there are five people - we'll call them Alice, Bob, Chris, Derek and Erica1.
First, Alice cuts herself a portion which she'd be happy to eat, and passes it to Bob for approval. If Bob thinks it's fair, it passes around to Chris, Derek and Erica for their approvals, too. If all approve, Alice can eat it.
If any reviewer thinks that it's too large, however, then they can pick up the knife and cut a piece off - reducing it to a fair portion. Any trimmings are added to the remaining cake. Having cut it, though, it now becomes that reviewer's slice. It passes to the remaining reviewers for approval or further trimming as they think fit. When the approval round has finished, the last owner of the slice may eat it.
The method is repeated for the next slice. When we get down to two remaining people, one cuts and the other chooses.
An obvious drawback with this method is the amount of offcuts generated by zealous trimming. If you prefer your portion in a single piece, then it may be better to accept a small slice early on in the process. The final choosers have little more than a pile of crumbs.
Envy
Both of the above methods have a further problem. If you accept an early slice out of five, say, you may agree it was one fifth as desirable as the whole cake, but you don't know how the rest of cake will be subsequently divided. One of the later slices may, by your judgement, be more desirable than the one you received. In short, you will remain envious. Mathematicians went back to the drawing board for this tricky problem, which they labelled 'Envy-Free Cake Division'.
What mathematicians wanted was a way to divide a cake such that everyone got their first choice. Stromquist's 1980 paper describes such a method for three persons. Stromquist issues each person with their own knife, and, crucially, also employs a referee with a large sword. It works something like this:
The referee starts with his sword hovering over one edge of the cake, then slowly moves it across, in preparation to cut a slice which is increasing in size. The three cake eaters also hover their knives over the larger portion of the cake, parallel to the sword, at the point where they believe their knife would cut the larger portion in two. In practice, as each cake eater's judgment differs, their knives will be in slightly different places. As the referee moves his sword, the eaters will also adjust the position of their knives.
At any point, one of the eaters can decide that the referee's slice is adequate for them, and they shout 'Cut!'. All knives and the sword stop at this point. The cake is then cut by the sword, and the crier of 'Cut!' receives that piece. The cake is also cut by the middle one of the three knives. Of the two people who didn't shout 'Cut!', the person whose knife is to the left receives the piece on the left, and the person whose knife is on the right receives the piece on the right.
This is a simple example of what mathematicians call a 'moving-knives' method. It has all sorts of problems if you wish to put it into practice - cutters must stop instantaneously on the command and cut fairly, for example.
Stromquist doesn't explain why the referee requires a sword rather than a cake knife. We can only assume that it adds an air of ceremony to the occasion.
Continuous Refinement
Most of the research since Stromquist has been to refine the method and to extend it to more than three recipients. In fact the mathematics gets seriously beyond the scope of this Entry for even four cake eaters, and they will receive somewhat fragmented slices, too. A universally-agreed envy-free procedure does not yet exist for five cake eaters, but the complexities it will undoubtedly involve will in all probability make it impractical to use.
One example of refinement is described in Julius Barbanel's 'Cake Division With Minimal Cuts...', published in Mathematical Social Sciences in 2004. His three-person envy-free method is as follows:
Starting on the left edge, the referee moves a knife across the cake until one person shouts 'Stop!'. The knife then marks the top of the cake without cutting through it. The person who shouted 'Stop!' - let's say it was Annie - then takes the knife and makes another parallel mark which bisects the larger piece, ie dividing the cake into three equal pieces, in her opinion. Let's call them pieces 1, 2 and 3, with piece 1 being Annie's.
The other two cake eaters, Bob and Chris then state which of pieces 2 and 3 they prefer. If they prefer different pieces, then we are all agreed. Each can take his piece believing it to be at least tied for biggest. If they prefer the same piece, however, this is where the fun starts.
If they both prefer piece 2, in the centre of the cake, then it needs to be reduced. The referee holds a knife over the left edge of piece 2, and Annie holds a second knife over the right edge. They then slowly move the knives towards each other, shrinking piece 2, but increasing pieces 1 and 3, until, let's say, Bob shouts 'Stop!'. Bob now thinks that piece 2 is tied for size with another piece, but Chris thinks it's still the largest. The cake can now be cut: Chris takes piece 2, Bob takes the piece he thinks it ties for size with, and Annie takes what's left.
If they both prefer piece 3, at the end of the cake, then the knives are placed at either edge of piece 2 as before, but they are now both moved to the right at the same rate, preserving the size of piece 2, but shrinking piece 3. Again, Bob shouts 'Stop!', thinking piece 3 now ties for size with either piece 1 or piece 2. The cake is cut: Chris takes piece 3, Bob takes the piece it tied with, in his opinion, and Annie takes the final piece.
This method sounds convoluted, but it has been proven to ensure that every cake eater receives a piece which they believe is at least tied for size with the largest. It just may not be the kind of thing you want to get into at a wedding reception.
Other Applications
Over 50 years after Steinhaus, research papers are still using cake as the subject, but mathematicians may try to justify their research grants by telling you that this analysis is applicable to other real life problems of fair division and dispute resolution. Barbanel states that his method extends beyond cake, such that it applies to any 'divisible heterogeneous good'. Land division is certainly a candidate for this analysis, although you would presumably need a very large knife, as well as deciding what to do with all the trimmings.
Perhaps the next phase of research is indicated by Stromquist, who acknowledges the work of Conway, Selfridge and Guy for their 'wine-sharing algorithm'. So, whose round is it?