Two young computer scientists may have found a way to divide a cake among any number of people while satisfying everyone involved, a problem that scientists have trying to crack for most than half a century. The findings are like a breath of fresh air in the field where many scientists thought a fair-division protocol in this situation was impossible.
Can’t you just eat the damn cake?
‘How to cut a cake fairly?’ is a conundrum many of us had to face at least once in our lives. For instance, you and Jim might both like features from the same side like having some of that whole fruit or vanilla frosting. Things get even more complicated the more people are lined up for a piece. At the end of the day, we each make a compromise, but for mathematical purists there is no such thing. There has to be a way to divide a cake into equally fair pieces such that all involved satiate their envy.
This isn’t even a new problem. We can find the same fair cake-cutting metaphor even in antiquity. For instance, in the Bible we’re actually offered a solution. In the book of Genesis, Abraham and Lot squander about how to fairly divide a piece of land. The clever Abraham divided the land in two parts that he valued equally then asked Lot to choose his favorite. This way, no matter what Lot chose, Abraham was satisfied.
Things get messy when you slice the cake in three or four, though. One landmark algorithm that can slice a cake in three was proposed by mathematicians John Selfridge and John Conway, who both independently reached the same solution in the 1960s.
To ensure Tim, Jim and Kim each get a fair slice of a cake, the algorithm first assigns Tim to cut the cake in three slices that are equally valuable from his perspective. Jim and Kim then have to choose their favorite slices. In the favorable event that both Jim and Kim choose a different slice, the fair division is closed successfully because Tim gets what’s left which was already satisfying.
If Jim and Kim choose the same piece of cake, one of them is asked to trim the slice a bit until what’s left is equal in value to the second-favorite slice of cake. The trimmed piece is set aside for later. Say if Jim trimmed the slice, then Kim next chooses her favorite out of the three, followed by Tim. If Kim chose the un-trimmed slice, Jim has to take the trimmed one. Again, Tim gets the leftover — but that’s perfectly fine by him. At this stage, everyone is happy. There’s just the tiny matter of that small piece left after Jim cut the cake.
You might think the show starts again, with the small trimmed slice getting again divided by the same rule. This process however implies an infinite loop so it’s not really a solution. The quirk is that Tim is more than satisfied because even if one of the other players gets the trimmed slice and the rest of the cake waiting to be allocated, that still adds up to no more than a full slice of cake, which Tim already has. Tim is a sort of win-win situation which means he “dominates” the cake cutting game.
This sort of algorithm ensures an envy-free division but is unbounded, meaning it could run anywhere from a couple of iterations to more than we can count to solve the game. And despite all sorts of interesting proposals for improved cake-cutting algorithms, we still didn’t have a working solution — not until 27-year-old Simon Mackenzie, a postdoctoral researcher at Carnegie Mellon, and Haris Aziz, a 35-year-old computer scientist at the University of New South Wales, published their seminal work.
The pair’s algorithm is based on Selfridge’s and Conway’s method. Like other algorithms before it, the protocol asks individuals to cut the cake in n equally satisfying pieces, then asks the other players to make trims and choose their favorites. What’s different is that in the background, the protocol changes the dynamic of the game and increases the number of dominant relationships between the players.
A dominant player means he’ll be satisfied no matter what. If they get sent home with their pieces of cake, no one will mind so the problem’s complexity is greatly reduced.
That’s not to say that it gets any easier. Dividing a cake among n players can require as many as n^n^n^n^n^n steps and a roughly equivalent number of cuts. For a handful of players, this means more iterations are required than there are atoms in the universe — all to satisfy a perverse obsessive compulsive disorder for treating everyone fairly. Imagine having this sort of people at your birthday. That cake would rot.
The problem is at least bounded, now. Aziz and Mellon say, however, that they already have ideas to make their algorithm simpler and reduce the number of steps.
“Seeing, in retrospect, how complicated the algorithm is, it’s not surprising that it took a long time before somebody found one,” said Ariel Procaccia, a computer scientist at Carnegie Mellon University.
Aziz and Mellon will present their paper on Oct. 10 at the 57thannual IEEE Symposium on Foundations of Computer Science
