Institute for Logic, Language and Computation

28 March 2007, Computational Social Choice Seminar, Steven J. Brams

Speaker: Steven J. Brams (New York)
Title: Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Procedure
Date: Wednesday 28 March 2007
Time: 16:00
Location: Room 3.27, Euclides Building, Plantage Muidergracht 24, Amsterdam

Properties of discrete cake-cutting procedures that use a minimal number of cuts (n-1 if there are n players) are analyzed. None is always envy-free or efficient, but divide-and-conquer (D&C) minimizes the maximum number of players that any single player may envy. It works by asking n≥2 players successively to place marks on a cake that divide it into equal or approximately equal halves, then halves of these halves, and so on. Among other properties, D&C (i) ensures players of more than 1/n shares if their marks are different and (ii) is strategyproof for risk-averse players. However, D&C may not allow players to obtain proportional, connected pieces if they have unequal entitlements. Possible applications of D&C to land division are briefly discussed.

This is joint work with Michael A. Jones, and Christian Klamler.

For more information, see or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X