Content area
Abstract
Issue Title: Special Issue: Fun with Algorithms
The Christmas gift exchange is a popular party game played around Christmas. Each participant brings a Christmas present to the party, and a random ordering of the participants, according to which they will choose gifts, is announced. When a participant's turn comes, she can either open a new gift with unknown value, or steal an already opened gift with known value from someone before her in the ordering; in the second case, the person whose gift was stolen gets to make the same choice. A gift cannot be stolen more than once.
We model the gift exchange as a sequential game of perfect information and characterize its equilibria, showing that each player plays a threshold strategy in the subgame perfect equilibrium of the game. We compute the expected utility of players as a function of the position in the random ordering; the first player's utility is vanishingly small relative to every other player. We then analyze a different version of the game, also played in practice, where the first player is allowed an extra turn after all presents have been opened--we show that all players have equal utility in the equilibrium of this game. Finally, we analyze the equilibria of two variants of this game, one where a gift can be stolen more than once, and another where players have complete information about the value of the gift.[PUBLICATION ABSTRACT]