Content area
Full Text
Theory Comput Syst (2012) 50:319 DOI 10.1007/s00224-011-9342-7
Published online: 15 June 2011 Springer Science+Business Media, LLC 2011
Abstract 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 participants 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 sub-game perfect equilibrium of the game. We compute the expected utility of players as a function of the position in the random ordering; the rst players utility is vanishingly small relative to every other player. We then analyze a different version of the game, also played in practice, where the rst player is allowed an extra turn after all presents have been openedwe 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.
Keywords Game theory
1 Introduction
The practice of giving gifts to friends and relatives at Christmas is a centuries-old tradition. Contrary to popular belief, gifts are not conjured up by Santa at the North
A. Ghosh M. Mahdian ( )
Yahoo! Research, Santa Clara, CA, USA e-mail: [email protected]
A. Ghoshe-mail: mailto:[email protected]
Web End [email protected]
Christmas Gift Exchange Games
Arpita Ghosh Mohammad Mahdian
4 Theory Comput Syst (2012) 50:319
Pole, and the actual buying of gifts unfortunately must be done by real people in real local marketplaces with no aid from Santa whatsoever. As a result, the Christmas gift industry is now a huge multibillion dollar industry much larger than online advertising, and is therefore clearly a subject deserving of serious study.
The problem of Christmas gifting admits many interesting...