Introduction
In game theory, "selection games" involve players choosing items from a common pool to maximize their individual utility. A classic example is the "Ethiopian Dinner" game: Alice and Bob share a platter of morsels, where each morsel $m_i$ has a specific value to Alice ($a_i$) and a different value to Bob ($b_i$). Because Alice’s gain is not necessarily Bob’s loss, this is a non-zero-sum game. However, competition remains high, and a simple greedy approach—eating one's favorite item first—often leads to sub-optimal outcomes by leaving high-value items for the opponent. This paper presents a visual proof for an elegant solution: the "crossout strategy."
The Crossout Strategy and Board Lemma
The core strategy, first identified by Kohler and Chandrasekaran in 1971, follows a counter-intuitive mantra: “Eat your opponent’s least favorite morsel on your own last move.” To prove that this backward-induction approach constitutes a subgame perfect equilibrium, the authors introduce Crossout Boards.
Morsels are plotted on a 2D Cartesian plane where the x-axis represents Alice’s utility and the y-axis represents Bob’s. The "crossout sequence" is defined by iteratively removing the current player's least favorite remaining morsel. The Crossout Board Lemma uses these plots to demonstrate that removing any single morsel does not "help" a player reach their preferred items earlier in the sequence. This visual, inductive approach simplifies the original 1971 proof and provides an intuitive understanding of the equilibrium's stability.
Key Insights
- Backward Induction: Optimal play requires determining the final move first and working backward. This "plan the last bite first" approach ensures a subgame perfect equilibrium.
- Computational Efficiency: Unlike many Nash equilibria problems which are PPAD-complete, the crossout strategy is $O(n \log n)$, requiring only basic sorting of utility lists.
- First-Mover Advantage: In an optimal game, the first player eventually secures their favorite morsel, though not necessarily on the opening turn.
- Combinatorial Connections: The game's structure relates to the Thue-Morse sequence for fair turn-taking, and the number of optimal outcomes for Alice is linked to Catalan numbers.
Results and Pareto Efficiency
The authors validated the strategy using Sage Mathematics Software to simulate 10,000 random permutation dinners of size 16.
The results confirm that the crossout strategy $(c, c)$ is a subgame perfect equilibrium. Furthermore, the strategy resulted in a Pareto efficient outcome—where no player can be made better off without hurting the other—in 93.28% of cases, and was weakly Pareto efficient in 97.59% of cases. Envy is also strictly bounded: the first player is never envious of the second, and the second player's envy never exceeds the utility of their single favorite morsel.
Limitations and Future Directions
While robust, the crossout strategy faces challenges in more complex scenarios:
- Utility Decay: If flavors "fade" over time (exponential decay), the symmetry of the proof is broken.
- Physical Constraints: In real meals, some items may be "hidden" (e.g., under bread), creating a partial ordering of availability.
- Information Asymmetry: The strategy assumes perfect knowledge of the partner's preferences; "deceit" might be viable if preferences are hidden.
- Scalability: The strategy does not easily extend to three or more players, where moving later can sometimes be advantageous.
Summary updated