Farm Fresh!

How to Divide the Cake Most Fairly

Cake Cutter Finally... mathematicians have come up with a supremely practical algorithm solving a common problem: how to slice up a cake fairly between two people.

Mathematician Julius Barbanel of Union College, and political scientist Steven Brams of New York University, published an algorithm in Springer's The Mathematical Intelligencer in which they demonstrate how to optimally share cake between two people, in equal pieces and in such a way that neither feels robbed

The "cut and choose" method of sharing divisible goods has been used since
Biblical times, when Abraham and his nephew Lot divided up Canaan.

Since the land could not support the herds of both tribes, they had to split up. Abraham let Lot choose the land he wanted and he choose the plain of Jordan, considered the best. Abraham graciously accepted what was left.

Being free of envy is not the only consideration when sharing something. What happens when more than two cuts can be made, or when people prefer different, specific sections of whatever is to be divided? Barbanel and Brams believe that with a giveback procedure it is possible to make a perfect division between two people that is efficient, equitable and void of jealousy.





An objective referee (such as a Mom or a computer) is essential to the plan. The potential cake eaters first tell the referee which parts of the delicacy they value most. In mathematical terms these are called someone's "probability density functions (PDFs)." The referee then marks out the cake at all points where the PDFs of the disgruntled would-be cake eaters cross, and assigns portions. If at this point the two parties receive the same size of cake, the task is over. If not, the giveback process starts.

The party who received the larger part of the cake during the first round must give a part of it back to the other person, starting with those parts in which the ratio of their
PDFs is the smallest. This goes on until the parties value their portions equally, and have the same volume of cake to eat. This method only works with a finite number of cuts if the players'  PDFs are straight-lined, or are so-called piecewise linear sections.

The researchers believe the method can be used to share cake and other divisible goods such as land. In the case of beachfront property being co-owned by two developers, for example, it can help to determine who gets what strips of land to build on based on the pieces of land they value most.

"This allocation is not only equitable but also envy-free and efficient – that is, perfect," says Barbanel.

Source: Two-Person Cake Cutting: The Optimal Number of Cuts by Barbanel, J.B. & Brams, S.J..The Mathematical Intelligencer.
 
Abraham and Lot separating
Abraham and Lot separating



Mathematical Conversations
Mathematical Conversations
Selections from The Mathematical Intelligencer

Cake-Cutting Algorithms
Cake-Cutting Algorithms






 

Contests
See the Movie
Market Entrance
Visit the Booths
Gamesmanship
Guides
Holiday
How to Lease a Booth
Buy Direct Directory
Pinterest

Copyright © 2014 Outrider. All rights reserved.