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
Investing in people is key to successful transformation
People-related factors like talent attraction and retention and clear top-down communication will determine whether your transformation progresses or stalls.
The way forward: Merging IT and operations
Digital transformation in any industry begins with bridging the gap between two traditionally separate teams.
Work reinvented: Tech will drive the office evolution
As organizations navigate a new world of hybrid work, tech innovation will be crucial for employee connection and collaboration.
Be a good example
"It was in the newspaper, but the towers fell the next day, and what I’d done was quickly lost."
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.