N-Person Cake-Cutting: There May Be No Perfect Division

Abstract

A cake is a metaphor for a heterogeneous, divisible good, such as land. A perfect division of cake is efficient (also called Pareto-optimal), envy-free, and equitable. We give an example of a cake that is impossible to divide among three players, so that these three properties are satisfied, however many (finite) cuts are made. It turns out that two of the three properties can be satisfied by a 3-cut and a 4-cut division, which raises the question of whether the 3-cut division, which is not efficient, or the 4-cut division, which is not envy-free, is more desirable (a 2-cut division can at best satisfy either envy-freeness or equitability, but not both). We prove that no perfect division exists for more than 4 cuts and for an extension of this example to more than three players.

Additional information

Notes on contributors

Steven J. Brams

STEVEN J. BRAMS is Professor of Politics at New York University and the author, co-author, or co-editor of 18 books and more than 250 articles. His most recent book is Game Theory and the Humanities: Bridging Two Worlds (2011). He has applied game theory and social-choice theory to voting and elections, bargaining and fairness, international relations, and the Bible, theology, and literature. He is a former president of the Peace Science Society (1990–91) and of the Public Choice Society (2004–2006), a Fellow of the American Association for the Advancement of Science (1986), a Guggenheim Fellow (1986–87), and was a Visiting Scholar at the Russell Sage Foundation (1998– 99).

Michael A. Jones

MICHAEL A. JONES has been an Associate Editor at Mathematical Reviews in Ann Arbor, MI since 2008. After completing a Ph.D. in game theory under Donald G. Saari at Northwestern University in 1994, he held temporary positions at the U.S. Military Academy at West Point and Loyola University (Chicago) before spending 10 years at Montclair State University, where he became a tenured Associate Professor. His latest hobby is taking weekly beginning piano lessons with his two kids.

Christian Klamler

CHRISTIAN KLAMLER is Associate Professor of Economics at the University of Graz in Austria. His research interests lie in social choice theory and fairness, with a current focus on applications in operations research. In his spare time he has composed music for the Austrian pop band Rollkragen.