Cut your cake and eat it (eventually)

Two computer scientists have made a breakthrough in the theory of cake cutting. They have found a new method to divide a cake between any number of people so that nobody is left envious of someone else. The result isn't only relevant to birthday parties: the cake can represent any continuous object, be it a piece of land, broadcasting time, or oil. Cake cutting theory is inspired by problems that come up in all sorts of contexts, from divorce proceedings to political conflicts.

Which piece do you want?

The problem of dividing the cake is quite simple when there are only two people involved. Get the first person to cut the cake and the second to choose the piece they want. The first person will make sure they cut the cake so that he or she is content with either of the two pieces. Depending on preference, and what's on the cake, he or she might cut it into two equal halves, or into a smaller piece that comes with a particular bonus (a strawberry, say) and a larger one. Whatever piece the second person chooses, the first won't be left envious. The second person might not like the way the cake was cut, but, since he or she got to pick first, also won't be envious of the other person's piece. Generally, a division method is called envy-free if no person would prefer another person's allocation to their own.

The method for two people has been known for a long time, but it wasn't until the 1960s that the mathematician John L. Selfridge devised an elegant and efficient method (later independently discovered by John H. Conway) that works for three people (see below). In 1995 Steven J. Brams (who has written several Plus articles) and Alan D. Taylor came up with a breakthrough method that works for any number of people, but has a drawback. Even when only four cake eaters are involved, the number of cuts required to make the fair division could be arbitrarily large. The number of questions you need to ask cake eaters in order to find the division — which relates to the time it takes the method to complete — could also be arbitrarily large. Just how large these numbers will be depends on the preferences of the players (if you're lucky, they could be small), but the point is that you can't from the outset put a limit on how long the algorithm would run and how many cuts would need to be made. This is particularly frustrating because mathematicians know for sure that for $n$ cake eaters there is an envy-free division that requires only $n-1$ cuts. It's finding that division which is the problem.

One variation is to allow a moving knife: this involves a referee moving the knife (or several knives) across the cake and players shouting "stop" when they think a cut should be made. For four cake eaters at least, this brings the number of cuts needed down to five. But it involves cake eaters making an infinite number of decisions. For each point of the axis along which the knife moves they need to decide whether to shout stop or not. And since what we would really like is a discrete step-by-step algorithm that could be run on a computer, such moving knife methods aren't entirely satisfactory.

The new method, devised by Haris Aziz and Simon MacKenzie, is discrete and comes with a bound on the number of cuts needed and the number of questions you need to ask of the cake eaters to find the division. Brams, co-inventor of the unbounded method, is pleased with the result. "I believe that the Aziz-MacKenzie algorithm is an important theoretical result and certainly improves on my earlier result with Taylor — by bounding the number of steps (or cuts) that the algorithm requires — which we showed was finite but for which we could not fix an upper bound."

Does this mean that conflicts over cake-like goods can now be solved in a flash? Not quite — Aziz and MacKenzie's result is of purely theoretical interest. The bound on the number of questions you need to ask when there are $n$ cake eaters involved is $$n^{n^{n^{n^{n^n}}}}.$$ No matter what the cake eaters' preferences are, you never need to ask more than that number of questions. But this still leads to unimaginably large numbers: even for $n=2$ standard calculators will give up. "It remains a challenge to reduce this bound, with or without the use of a moving knife," says Brams. "However, I don't think this number will ever be such that any of these algorithms will have any practical value."

There are many ways to eat a cake.

There is another problem too. Aziz and MacKenzie's method guarantees that nobody is left envious of another person's piece of cake. But this doesn't guarantee that everybody is as satisfied as possible. There may be another division of the cake that leaves one or more of the cake eaters better off without making anyone worse off — in maths jargon, envy-free divisions are not generally pareto-optimal. This may leave cake eaters grumbling: they may not be jealous of another person's piece, but they may well be unhappy knowing they could have done better with a different division. It is often impossible to satisfy both envy-freeness and pareto-optimality at the same time. So while theorists are hard at work reducing the bound on their algorithms, practitioners on the ground need to think hard about what sort of division is best in a particular conflict: envy-free, pareto-optimal, or perhaps some other criterion.

Further reading

There is a lovely article about the new result in Quanta Magazine.

How to divide a cake between three people so that nobody is envious

Let's suppose our three people are called A, B and C, and since we're gender neutral, we refer to all of them as "it". The procedure starts by C cutting the cake into three pieces it considers equally valuable. A and B then take their pick. If they choose two different pieces we are done.

Suppose A and B want the same piece. In that case B trims a bit off the piece it considers most valuable so that it matches B's second most-valuable piece. Put the trimming to one side and let A take its pick. Next, B chooses its piece, with the limitation that if A didn't choose the piece that had something trimmed off, then B must choose it. Lastly, C takes its pick. Now A is not envious because it got the first choice. B is not envious, because its two first choices are equally valuable: whatever A picks, there's an equally-valuable piece left for B. C isn't envious because the three initial pieces were equally valuable to it. The only piece that has reduced in value, from C's point of view, is the one that had something trimmed off it, but that will have been taken by either A or B.

This leaves the trimming to be divided up. Suppose the piece that had something trimmed off it was chosen by A in the previous round. Let B divide the trimming into three pieces it considers equally valuable. Let the A take the first pick, C the second pick, and B the last pick. Now A isn't envious because it got to pick first. If C were envious, it would have to be envious of A. That's because it wasn't envious in the first round, and in the second it's not envious of B because it got to pick ahead of B. Could C be envious of A? Well, in the first round A chose the piece that had something trimmed off it, that is, A picked the piece in the first round that was less valuable to C than the other two. Let's write V for the value, to C, of the three pieces it initially cut the cake into. Let's write W for the value, to C, of the trimming. Now the total value, to C, of C's allocation is V plus some fraction of W. The total value, to C, of A's allocation is V-W plus some fraction of W. Clearly, V-W plus some fraction of W is always going to be less than V. That is, the value of A's allocation, to C, is less than its own allocation, hence C is not envious of A.

What if it was B who chose the piece that had something trimmed off it in the first round? In that case, simply swap the roles of A and B in the previous paragraph.