Last December I compared strategies for playing white elephant, a game in which people take turns either unwrapping a gift or stealing a previously unwrapped gift. It turned out that players’ best strategy was to be “greedy” by stealing the most subjectively valuable unwrapped gift. Intuitively, this strategy helps players obtain the gift they want most, provided no other players also want that gift and steal it later in the game.

White elephant exchanges are a fun, but not necessarily optimal, way to match people with gifts. Another way is to use the top trading cycle (TTC) algorithm:

1. Give everyone a random unwrapped gift.
2. Ask everyone to point at the most subjectively valuable gift (which may be their own).
3. If there is a closed cycle of people pointing at each others’ gifts, give everyone in that cycle the gift at which they’re pointing, and remove those people and gifts from consideration.

The allocation delivered by this algorithm has several desirable properties. First, it is Pareto efficient: every cycle identifies a mutually beneficial exchange, and the algorithm stops when no such exchanges remain. Second, it is strategy-proof: people cannot get better gifts by lying about their preferences (see Roth, 1982). Third, it is core-stable: no group of people can cooperate to improve their allocations, for otherwise they would have formed a cycle before the algorithm stopped.

However, the TTC algorithm may not deliver the allocation that maximizes the sum of gifts’ subjective values. This allocation corresponds to a maximum-weight matching in the bipartite graph connecting people to gifts, with each edge’s weight equal to the incident player’s subjective value of the incident gift.1

The chart below compares the mean subjective value of the gifts allocated using a game of white elephant, using the TTC algorithm, and by finding a maximum-weight matching. I compute these allocations as follows. First, I define person $$i$$'s subjective value of gift $$j$$ as $$V_{ij}=\rho X_j+(1-\rho)Y_{ij},$$ where $$X_i$$ and $$Y_{ij}$$ are iid uniformly distributed on the unit interval. The parameter $$\rho$$ determines the correlation of gifts’ subjective values across people: if $$\rho=0$$ then everyone’s valuations are independent, whereas if $$\rho=1$$ then everyone has the same valuation of each gift. For a range of $$\rho$$ values, I simulate 100 valuation sets $$\{V_{ij}:i,j\in\{1,2,\ldots,30\}\}$$, and apply each gift exchange mechanism to each set. In the white elephant games, I assume all players adopt the greedy strategy described above unless the best unwrapped gift has subjective value less than $$\mathrm{E}[V_{ij}]=0.5$$, in which case players unwrap a new gift.

All three gift exchange mechanisms get worse as gifts’ subjective values become more correlated. Intuitively, as the correlation increases, there are fewer Pareto-improving trades and so people get stuck with their random endowments.2 The allocations delivered via white elephant games and the TTC algorithm have similar allocative efficiencies, even though white elephant players can’t assign subjective values to gifts until they are unwrapped.

Yet white elephant games are much more popular at Christmas parties than the TTC algorithm. One explanation could be that the algorithm tends to reveal a lot of information about peoples’ preferences and, in particular, may make people more upset about contributing a gift no-one wants. I justify this claim in the following chart, which plots the number of times someone rejects each gift for another in my simulated exchanges. For example, I add one to gift A’s rejection count if