Difference between revisions of "The perfect way to cut a cake"

Revision as of 02:39, 7 November 2006

Solved: the perfect way to cut a cake

The art of cake-cutting requires great care and skill to ensure no party is left
feeling cheated or envious. Now, however, parents and party hosts can approach
the task with a little more confidence –
mathematicians claim to have found the perfect way to cut a cake and keep everyone happy.

“The problem of fair division is one of the oldest existing problems. The cake
is a metaphor for any divisible object where people value different parts
differently,” explains Christian Klamler, at the University of Graz, Austria,
who solved the problem with fellow mathematicians Steven Brams and Michael Jones.

According to Klamler, for any division to be acceptable, it must ideally be
equal among all parties, envy-free so that no one prefers another’s share and
equitable, where each places the same subjective value on their share.

Traditional methods, such as the "you cut, I choose" method, where one person
halves the cake and the other chooses a piece, are flawed because though both
get equal shares and neither is envious, the division is not equitable
- one piece may have more icing or fruit on it than another, for example.
Impartial cutter

Enter the “Surplus Procedure” (SP) for cake-sharing between two people, and the
"Equitability Procedure" (EP) for sharing between three or more.
Both involve asking guests to tell the cake-cutter how they value different parts
of the cake. For example, one guest may prefer chocolate, another may prefer marzipan.

Under SP, the two parties first receive just half of the cake portion that they
subjectively valued the most. Then the "surplus" left over is divided
proportionally according to the value they gave it. EP works in a similar way:
the guests first get an equal proportion of the part of the cake they
each value the highest – a third each if they are three; a quarter each if
they are four, etc – and then the remainder is again divided along the lines of
subjective value.

The result is everyone is left feeling happy, Klamler says. Two people, for
example, may feel they are each getting 65% of what they want rather than just
half.

“These procedures are new and have never been tried out in real-world
applications,” says Brams. “But where there is a divisible good like land or
water, which players value differently, the procedure could be used to allocate more-than-proportional shares, making everybody as happy as possible.”

Intriguingly, the procedures are "tamper-proof" – people cannot manipulate the
process and must be truthful with the referee, or else they could end up
with less than makes them happy.

Journal reference: Notices of the American Mathematical Society (Vol 53, p1014)