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?
Advertisement
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.
This story is only available to subscribers.
Don’t settle for half the story.
Get paywall-free access to technology news for the here and now.
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.
