How to make the most of a shared meal: plan the last bite first

Lionel Levine, Katherine E. StangearXiv 2011 · arXiv

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.

Crossout boards D and D-m illustrating the visual representation of morsel utilities and the effect of removing a single item.

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.

Scatter plot of Alice's vs. Bob's scores across simulated trials, highlighting the Pareto efficiency of the crossout strategy.

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

Abstract

If you are sharing a meal with a companion, how best to make sure you get your favourite mouthfuls? Ethiopian Dinner is a game in which two players take turns eating morsels from a common plate. Each morsel comes with a pair of utility values measuring its tastiness to the two players. Kohler and Chandrasekaharan discovered a good strategy -- a subgame perfect equilibrium, to be exact -- for this game. We give a new visual proof of their result. The players arrive at the equilibrium by figuring out their last move first and working backward. We conclude that it's never too early to start thinking about dessert.
BibTeX
@misc{levine2011how,
  author = {Lionel Levine and Katherine E. Stange},
  title = {{How to make the most of a shared meal: plan the last bite first}},
  year = {2011},
  eprint = {1104.0961},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1104.0961},
}
Figure