Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

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

Become an MIT Technology Review Insider for in-depth analysis and unparalleled perspective.

Subscribe today
Want more award-winning journalism? Subscribe to Insider Plus.
  • Insider Plus {! insider.prices.plus !}*

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    Print + Digital Magazine (6 bi-monthly issues)

    Unlimited online access including all articles, multimedia, and more

    The Download newsletter with top tech stories delivered daily to your inbox

    Technology Review PDF magazine archive, including articles, images, and covers dating back to 1899

    10% Discount to MIT Technology Review events and MIT Press

    Ad-free website experience

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