Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A duality principle for selection games

Authors: Lionel Levine, Scott Sheffield and Katherine E. Stange
Journal: Proc. Amer. Math. Soc. 141 (2013), 4349-4356
MSC (2010): Primary 91A10, 91A18, 91A06, 91A50
Published electronically: August 23, 2013
MathSciNet review: 3105877
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A dinner table seats $ k$ guests and holds $ n$ discrete morsels of food. Guests select morsels in turn until all are consumed. Each guest has a ranking of the morsels according to how much he would enjoy eating them; these rankings are commonly known.

A gallant knight always prefers one food division over another if it provides strictly more enjoyable collections of food to one or more other players (without giving a less enjoyable collection to any other player), even if it makes his own collection less enjoyable. A boorish lout always selects the morsel that gives him the most enjoyment on the current turn regardless of future consumption by himself and others.

We show that the way the food is divided when all guests are gallant knights is the same as when all guests are boorish louts, but turn order is reversed. This implies and generalizes a classical result of Kohler and Chandrasekaran (1971) about two players strategically maximizing their own enjoyments. We also treat the case where the table contains a mixture of boorish louts and gallant knights.

Our main result can also be formulated in terms of games in which selections are made by groups. In this formulation, the surprising fact is that a group can always find a selection that is simultaneously optimal for each member of the group.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 91A10, 91A18, 91A06, 91A50

Retrieve articles in all journals with MSC (2010): 91A10, 91A18, 91A06, 91A50

Additional Information

Lionel Levine
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

Scott Sheffield
Affiliation: Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139

Katherine E. Stange
Affiliation: Department of Mathematics, Stanford University, 450 Serra Mall, Building 380, Stanford, California 94305
Address at time of publication: Department of Mathematics, University of Colorado Boulder, Campus Box 395, Boulder, Colorado 80309

Keywords: Agreement, cake cutting, fair division, sequential selection, subgame perfect equilibrium
Received by editor(s): October 21, 2011
Received by editor(s) in revised form: February 14, 2012
Published electronically: August 23, 2013
Additional Notes: The first author was supported by NSF MSPRF 0803064.
The second author was partially supported by NSF grant DMS 0645585.
The third author was supported by NSF MSPRF 0802915.
Communicated by: Jim Haglund
Article copyright: © Copyright 2013 American Mathematical Society

American Mathematical Society