Computer Scientists Can Divide A Cake Fairly, And That's A Surprisingly Big Deal
File this under "Wait, seriously?": until two computer scientists published a paper in 2016, there was no computer algorithm that could divide a cake fairly among any number of people. Because cutting a cake is a parallel to a wide range of real-world problems—dividing land, for example, or splitting wealth—this new advancement in computer science has wide-reaching implications.
The First Cut Is The Fairest
First things first: by dividing a cake "fairly," we mean in a way that won't make any one person envious of anyone else. If you like fondant flowers and the one other person doesn't, for example, a fair cake cutting ends up with two equal-sized pieces where one has all the fondant flowers and the other is flower-free. There was an algorithm for this kind of so-called "envy-free" cake division among three people circa 1960, but until 2016, the only algorithm that could divide a cake for more people than that was "unbounded." That means that it might need to run for millions of steps, depending on the people's cake preferences. In Quanta Magazine, Erica Klarreich explains, "Over the past 50 years, many mathematicians and computer scientists [...] had convinced themselves that there was probably no bounded, envy-free algorithm for dividing cake among n players." That algorithm doesn't sound so obvious now, does it?
The Algorithm, Explained
The algorithm is a little complicated, but it can be laid out in plain language. Say Alice, Bob, and Charlie are cutting a cake. Charlie cuts the cake into three pieces that he considers equally valuable. Alice and Bob each point to their first-choice piece. If those pieces are different, it ends there—they both get their first choice, and Charlie gets a piece he considers equal to the other two.
But if Alice and Bob choose the same piece, there's some work to do. Bob identifies his second choice, then trims his first-choice piece to match his second choice, placing the trimmed part aside for later. Then Alice gets to choose the piece she wants, followed by Bob, then Charlie. (If Alice doesn't go for the trimmed piece, Bob has to take it). That makes things fair, because Alice got to choose first, Bob considered his second choice equally valuable, and Charlie thought all of the slices were equally valuable in the first place.
What about the leftover trimmed part? Bob gets to cut that piece into three slices he considers equally valuable. Then Alice chooses her preferred piece first, followed by Charlie, then Bob. That also makes things fair, because Alice got to choose first and Bob thought all of the pieces were equal in the first place. But what about Charlie? Well, back at the beginning, Charlie thought all of the slices were equally valuable, and he got one of those equal pieces. Adding on the trim is just a cherry on top of an already good situation for Charlie, so he doesn't really care which part of the trim he gets. The authors of the algorithm would say that Charlie "dominates" whoever got the trimmed slice. That's important, because if Charlie did care, the algorithm could end in more trimming of the trimmed slice in an endless loop.
Still, even a simplified version of this algorithm might not be practical for things like land and wealth, since it requires tiny bits from other parts of the thing being divided. But it's a stepping stone. It proves to computer scientists that a better algorithm may be out there—they just have to keep looking.