An Algorithm For Super Envy-Free Cake Division

✍ Scribed by William A. Webb

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 720 KB
• Volume: 239
• Category: Article
• ISSN: 0022-247X
• DOI: 10.1006/jmaa.1999.6581

✦ Synopsis

The standard mathematical setting for fair division problems begins with a cake X which is a compact subset of some Euclidean space and n players P,, . . . ,el each with an additive nonatomic probability measure p,,. . . , p,, on a a-algebra of measureable subsets of X , and asks for a partition { X ,,..., X,} of X such that P, is satisfied to receive X , under some definition of fairness. The original problem introduced by Steinhaus in 1946 asked for a simple fair assignment where p i ( X j ) 2 l/n whenever 1 I i I n [23]. Other common criteria for fairness include strongly fair assignment where p j ( X i ) > l / n whenever 1 I i I n , envy-free where p i ( X , ) 2 p i ( X j ) whenever 1 I i, j I n and strongly envy-free where p,(X,) > p , ( X j ) whenever 1 I i, j I n and i # j . Recently, Barbanel introduced the condition of super envy-free where p i ( X , ) > l/n and p , ( X j ) < l/n whenever 1 5 i, j 5 n and i f j 131.

Barbanel proved that a super envy-free partition exists if and only if the measures are linearly independent, that is c1 p1 + ...