The Surprisingly Complex Art of Cake Cutting
Mathematicians love a good cake, so it is hardly a surprise that the problem of how to cut and apportion a Victoria sponge, say, has severely exercised them. Today, cake lovers will be excited to hear of a significant breakthrough.

The problem is this: how do you cut a cake and divide it fairly among n people when each person may have a different opinion of the value of each piece?
In 1980, Walter Stromquist at Swarthmore College near Philadelphia proved that there was an envy-free solution to the problem. In other words, it is possible to cut a cake into n pieces using n−1 cuts and to allocate one piece to each person so that everyone values his or her piece no less than any other piece.
But although a solution may be possible, finding it is hard. The open question today is whether there is an efficient algorithm that finds such a cut of the cake, say Xiaotie Deng at the City University of Hong Kong and a couple of pals.
Their contribution to the problem is to find such an algorithm, albeit with a couple of minor caveats. Impressively, their algorithm works in polynomial time, which means that a solution can always be found reasonably quickly.
The caveats? The algorithm works when dividing a cake only among three people and then only for the special case involving mathematical objects called measurable utility functions, and the result is only approximately envy-free.
Nevertheless, that should still be handy when a dispute arises at the next junior common room tea party.
Ref: arxiv.org/abs/0907.1334: On the Complexity of Envy-Free Cake Cutting
Keep Reading
Most Popular
DeepMind’s cofounder: Generative AI is just a phase. What’s next is interactive AI.
“This is a profound moment in the history of technology,” says Mustafa Suleyman.
What to know about this autumn’s covid vaccines
New variants will pose a challenge, but early signs suggest the shots will still boost antibody responses.
Human-plus-AI solutions mitigate security threats
With the right human oversight, emerging technologies like artificial intelligence can help keep business and customer data secure
Next slide, please: A brief history of the corporate presentation
From million-dollar slide shows to Steve Jobs’s introduction of the iPhone, a bit of show business never hurt plain old business.
Stay connected
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.