Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

The Surprisingly Complex Art of Cake Cutting

Mathematicians have discovered how to divide a cake fairly among three people.

  • July 23, 2009

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

The latest Insider Conversation is live! Listen to the story behind the story.

Subscribe today
Already a Premium subscriber? Log in.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

Want more award-winning journalism? Subscribe to Insider Basic.
  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly magazine delivery and unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

/
You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.