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:
- 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.
- 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.
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.
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