Google Research

Analysis of the gift exchange problem

The Electronic Journal of Combinatorics, vol. 24 (2017), P3.9

Abstract

In the gift exchange game there are n players and n wrapped gifts. When a player’s number is called, that person can either choose one of the remaining wrapped gifts, or can “steal” a gift from someone who has already unwrapped it, subject to the restriction that no gift can be stolen more than a total of σ times. The problem is to determine the number of ways that the game can be played out, for given values of σ and n. Formulas and asymptotic expansions are given for these numbers. This work was inspired in part by a 2005 remark by Robert A. Proctor in the On-Line Encyclopedia of Integer Sequences.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work