A duality principle for selection games

Lionel Levine, Scott Sheffield, Katherine E. StangearXiv 2011 · arXiv

Abstract

Sequential selection games, where players take turns choosing items from a set, are typically computationally complex to solve. This paper introduces a "Duality Principle" that reveals a fundamental symmetry between two behavioral extremes: the altruistic "Gallant Knight" and the greedy "Boorish Lout." By demonstrating that altruism and reversed greed lead to identical outcomes, the authors provide a framework to solve these games in linear time.

Introduction

In game theory, sequential selection games—such as kids picking teams or diners choosing sushi—are notoriously difficult to analyze. When players act strategically to maximize their own total enjoyment, finding the optimal play is often PSPACE-complete. This computational barrier makes it grueling to predict outcomes as the number of items grows. This research explores whether specific behavioral "stereotypes" can simplify this complexity, focusing on two extremes:

  1. The Gallant Knight: A player who prioritizes the enjoyment of others, choosing divisions that benefit their peers even at a personal cost, provided it doesn't harm anyone else.
  2. The Boorish Lout: A myopic, greedy player who grabs the best available item on their turn, ignoring future consequences.

Methodology

The authors utilize the framework of subgame perfect Nash equilibria on game trees. They define formal partial orderings for "knight order" and "lout order" based on how players compare sets of items (referred to as "plates"). The core of the proof relies on a "swapping" lemma: if a sequence of turns is transposed, a Knight's turn can be swapped with a Lout's turn without changing the final distribution of items under specific conditions. By repeatedly applying this logic, altruistic moves can be "pushed" to the end of the game and shown to be functionally equivalent to greedy moves made in reverse order.

Figure 1: A game tree illustrating sequential choices and payoffs for two players, highlighting the paths taken under different behavioral assumptions.

Key Insights and Ideas

The Duality Principle

The most striking insight is that altruism and reversed greed are two sides of the same coin. If a group of Knights plays in order $1, 2, \dots, m$, the resulting partition of items is exactly what would occur if a group of Louts played in order $m, m-1, \dots, 1$. This symmetry allows "knight" games to be solved in linear time ($O(nk)$) by simply simulating greedy behavior in reverse.

Conflict-Free Group Decisions

The paper extends this duality to group decision-making. When a group must agree on a selection (a Pareto efficient choice), there is always at least one choice that is simultaneously optimal for every member of the group, effectively avoiding internal conflict.

Figure 2: A complex game tree for three players where nodes represent collective decisions by player subsets, demonstrating conflict-free selection paths.

Weak Assumptions, Strong Results

The proofs do not require players to have a total ranking of every possible outcome. Even with "partial preferences"—where a player might find two sets of items incomparable—the duality holds, making the results robust across various preference structures.

Key Results

  • Theorem 1: Formally proves the duality between a sequence of Gallant Knights and a reversed sequence of Boorish Louts.
  • Theorem 4 (The Mixed Case): Generalizes the result to individuals of "mixed nature." If a player acts as a Knight on some turns and a Lout on others, the final division can still be found by pushing all knight turns to the end, reversing them, and treating them as lout turns.
  • Generalization of Kohler-Chandrasekaran: The paper provides a new context for a 1971 result regarding two-player strategic games, showing it is a specific case of this broader duality.

Limitations and Future Work

While the theory provides a powerful computational shortcut, the authors note several boundaries:

  • Deterministic Louts: The proof relies on a Lout having a clear favorite item. If a player is indifferent between items, the behavior becomes non-deterministic, potentially breaking the duality.
  • The Strategic Gap: While the Knight vs. Lout problem is solved, games where three or more players strategically maximize their own enjoyment (without being purely gallant or boorish) remain computationally difficult and full of "pathologies."
  • Multisets: While the proof holds for identical items, it requires careful handling of how louts choose between identical favorites.

Summary updated

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 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 that 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.
BibTeX
@misc{levine2011duality,
  author = {Lionel Levine and Scott Sheffield and Katherine E. Stange},
  title = {{A duality principle for selection games}},
  year = {2011},
  eprint = {1110.2712},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1110.2712},
}
Figure