| 3. Everything / Deep Thought / Philosophy 3. Everything / Maths, Science & Technology / Mathematics Envy-Free Cake Division
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 obliged 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:
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:
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 Each of the above methods has 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:
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:
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? People have been talking about this Guide Entry. Here are the most recent Conversations: |
Most of the content on this site is created by h2g2's Researchers, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the BBC. The BBC is not responsible for the content of any external sites referenced. In the event that you consider anything on this page to be in breach of the site's House Rules, please click here to alert our Moderation Team. For any other comments, please start a Conversation below. | ||||||||||||||||||