Update (December 2020)

I am trying to solve a two-body problem in the American West. Here's my CV. Also check out:

### on white elephant

5 May 2013

Come the holiday season, a fair proportion of Americans — myself possibly included — will engage in a cultural pastime known as White Elephant (Wikipedia). In this game as it usually occurs, people bring wrapped gifts to a holiday party; attendees, tipsy on eggnog, are then randomly ordered (often by drawing random cards from a deck) and proceed to select gifts in order.

Each person who selects a gift has a choice: they can either select an unwrapped gift from the central pile, or they can steal a gift from someone who has already chosen one. If someone's gift is stolen, they face the same choice: pick an unwrapped gift from the central pile, or steal a gift from someone else (excluding the person who just stole from them). This is repeated until all gifts have been picked from the central pile.

A standard modification — mostly to ensure that the game ends before the punch runs dry — is that a particular gift may only be stolen $$N$$ times. So once a highly-desirable item has been stolen for the $$N^\text{th}$$ time, the last thief is pretty happy with their situation.

It is worth emphasizing that in most instantiations, there is no gift that is even marginally desirable; as a pertinent example, the annual white elephant run by my parents' neighborhood has featured the same stuffed-dog-that-sings-Christmas-carols for five years now.

Since I am currently TAing a class in market design and allocation, white elephant came up as a [rather ridiculous] example of an allocation mechanism. I have decided to round out the literature and publish here that, as a mechanism, it is neither efficient nor strategy-proof for non-trivial cases (when $$N\geq2$$); it is not strategy-proof for any case except $$N=0$$. This should, of course, lead us to select a new holiday pastime.

### the setup

Consider a setting with individuals $$\{m_i\}_{i=1}^M$$ and gifts $$\{x_i\}_{i=1}^M$$; we will assume that there are the same number of individuals and gifts. Individual $$i$$ has a strict preference ordering $$\succ_i$$ over gifts.

To abstract from random ordering, we will for now assume that individual $$1$$ selects a gift, then individual $$2$$, etc. To further assist the analysis, we will assume that gifts are unwrapped: when an individual chooses a gift from the central gift pile, they know what they are picking and therefore where it sits in their preference ordering. Both of these assumptions can be weakened somewhat.

As mentioned above, in each round an individual can either select a gift from the central gift pile, or can steal a gift from another agent, provided that gift has not already been stolen $$N$$ times. If an individual's gift is stolen, they face the same choice, except that they cannot steal back immediately from the individual who stole from them.

The mechanism ends when all individuals have a gift.

As a mechanism, we will consider implementing this by having agents report their preferences over the unwrapped gifts; the game then proceeds by each agent selecting their most-preferred gift which is permissible according to the rules of the game.

### the degenerate case: N = 0

This bears little discussion. When $$N = 0$$, no gift may be stolen, and this mechanism is equivalent to serial dictatorship (PDF, page 6). It is already known — and relatively easy to show — that serial dictatorship is efficient and strategy-proof; I claim that this doesn't contradict the idea that white elephant satisfies neither property [in general] because, come on, what's the fun of a holiday game where you just pick things in order? Absolutely no drama!

### a little stealing: N = 1

Consider the following preference ranking:

$\begin{array}{ccc} m_1 & m_2 & m_3 \\ \hline x_3 & x_2 & x_3 \\ x_2 & x_3 & x_2 \\ x_1 & x_1 & x_1 \end{array}$

The allocation unfolds as follows:

• Round 1: $$(m_1,x_3)$$
• Round 2: $$(m_2,x_2)$$
• Round 3: $$(m_3,x_3)$$, then $$(m_1,x_2)$$ (since $$m_1$$ cannot steal gift $$x_3$$ back from $$m_3$$), then $$(m_2,x_1)$$ (since $$m_2$$ cannot steal gift $$x_3$$, because it has been stolen $$N=1$$ time already)

The final allocation is therefore

$\{(m_1,x_2),(m_2,x_1),(m_3,x_3)\}$

But what if $$m_2$$ had submitted preference ranking $$x_3\succ_2x_2\succ_2x_1$$? Then the allocation would unfold as:

• Round 1: $$(m_1,x_3)$$
• Round 2: $$(m_2,x_3)$$, then $$(m_1,x_2)$$
• Round 3: $$(m_3,x_2)$$, then $$(m_1,x_1)$$

The final allocation when individual $$2$$ lies in this way is therefore

$\{(m_1,x_1),(m_2,x_3),(m_3,x_2)\}$

Since $$x_3\succ_2x_1$$, individual $$2$$ is strictly better off by misreporting! The mechanism is therefore not strategy-proof.

What can we say about efficiency?

Theorem: in the case where $$N=1$$, the allocation determined by white elephant is efficient.

Proof. Suppose white elephant results in allocation $$(y_1,\ldots,y_N)$$ which is inefficient. Then there is a set (and indexing) of agents $$\{i_k\}_{k=1}^K$$ such that agent $$i_k$$ prefers $$y_{i_{k+1}}$$ to $$y_{i_k}$$ (modulo $$K$$). Consider such a transfer of gifts, and WLOG let $$i_1$$ be the agent who first selected his final gift during the running of white elephant. We have assumed that $$y_{i_2}\succ_{i_1}y_{i_1}$$. Three cases arise:

• $$i_2$$ selected $$y_{i_2}$$ from the pile of gifts. Then $$y_{i_2}$$ was available when $$i_1$$ made his final choice, contradicting $$y_{i_2}\succ_{i_1}y_{i_1}$$.
• $$i_2$$ stole $$y_{i_2}$$ from $$i_1$$. Since $$y_{i_2}$$ has then been stolen $$N=1$$ times, $$i_2$$ will end with this gift and will make no further choices; however, $$i_1$$ must now choose another gift, contradicting $$i_1$$ selecting his final gift before $$i_2$$.
• $$i_2$$ stole $$y_{i_2}$$ from $$j\neq i_1$$. Since $$y_{i_2}$$ was steal-able, $$i_1$$ either passed on the opportunity to select it from the pile (since $$N=1$$) or neglected to steal it himself; both contradict $$y_{i_2}\succ_{i_1}y_{i_1}$$

In all cases we reach a contradiction, hence the allocation resulting from white elephant with one steal allowed must be efficient. $$\square$$

### lots of stealing: N > 1

To observe the failure of strategy-proofness, consider the following two preference profiles:

$P_{333}:\;\;\;\begin{array}{ccc}m_1&m_2&m_3\\\hline x_3&x_3&x_3\\x_2&x_2&x_2\\x_1&x_1&x_1\end{array}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P_{323}:\;\;\;\begin{array}{ccc}m_1&m_2&m_3\\\hline x_3&x_2&x_3\\x_2&x_3&x_2\\x_1&x_1&x_1\end{array}$

We will consider the white elephant outcome of each profile, and show that the outcomes — when considered in tandem — prove that this mechanism is not strategy-proof. To start, let's trace the allocation of preference profile $$P_{333}$$ when $$N=2$$.

• Round 1: $$m_1$$ picks $$x_3$$
• Round 2: $$m_2$$ steals $$x_3$$, then $$m_1$$ picks $$x_2$$
• Round 3: $$m_3$$ steals $$x_3$$, $$m_2$$ steals $$x_2$$, then $$m_1$$ picks $$x_1$$

For more general $$N$$, notice that when her initial turn comes to pick, $$m_3$$ will always steal $$x_3$$; the choice then passes to $$m_2$$, who because of no steal-backs will steal from $$m_1$$. If $$x_3$$ has not been stolen the maximum number of times, $$m_3$$ will steal from $$m_1$$, otherwise he will pick from the pile (because he cannot steal back from $$m_2$$). In this way, we can see that the order of selection in the final round is

$\langle m_3,m_2,m_1,m_3,m_2,m_1 ,\ldots\rangle$

Moreover, $$m_3$$ steals $$x_3$$, implying that $$m_2$$ cannot; $$m_1$$ will then steal $$x_3$$ if it is feasible to do so (if it has not already been stolen $$N$$ times), and $$m_3$$ cannot steal it back. In this way, every-other individual steals $$x_3$$, until it has been stolen the maximum number of times. At the beginning of the final round, $$x_3$$ has already been stolen twice; therefore the person at the $$t=(2k+1)^\text{th}$$ position, upon stealing it, will render it stolen $$k+2$$ times. Since the gift may be stolen $$N$$ times, it reaches its final holder at $$k=N-2$$, or

$t^\star = 2 N - 3$

Since there are three individuals choosing in order, the individual who obtains $$x_3$$ can be identified by $$2 N - 3 \mod 3 = 2 N \mod 3$$. The subsequent individual ($$2N + 1 \mod 3$$) obtains $$x_2$$, and the final individual obtains $$x_1$$. This gives allocations of:

• $$N\equiv0 \mod 3: \{ (m_1,x_3),(m_2,x_1),(m_3,x_2)\}$$
• $$N\equiv1 \mod 3: \{ (m_1,x_2),(m_2,x_3),(m_3,x_1)\}$$
• $$N\equiv2 \mod 3: \{(m_1,x_1),(m_2,x_2),(m_3,x_3)\}$$

Now we will consider the preference ordering given by $$P_{323}$$.

In the simple case of $$N=2$$, the white elephant allocation is found by

• Round 1: $$m_1$$ picks $$x_3$$
• Round 2: $$m_2$$ picks $$x_2$$
• Round 3: $$m_3$$ steals $$x_3$$, $$m_1$$ steals $$x_2$$, $$m_2$$ steals $$x_3$$, $$m_3$$ steals $$x_2$$, then $$m_1$$ picks $$x_1$$

Following the same logic as used in the discussion of the preference relation $$P_{333}$$, we can see that the order of selection is

$\langle m_3,m_1,m_2,m_3,m_1,m_2,\ldots\rangle$

The same no-steal-back logic applies, with every-other individual stealing $$x_3$$; since $$x_3$$ has been stolen only once at the beginning of the final round, the person at the $$(2k+1)^\text{th}$$ position, upon stealing $$x_3$$, will render it stolen $$k+1$$ times. It reaches final holder when $$k=N-2$$, or

$t^\star = 2 N - 1$

Now the individual who obtains $$x_3$$ is identified by $$2N-1\mod 3$$. The subsequent individual ($$2N\mod 3$$) obtains $$x_2$$, and the final individual obtains $$x_1$$. This gives allocations of:

• $$N\equiv 0\mod 3: \{ (m_1,x_3),(m_2,x_2),(m_3,x_1)\}$$
• $$N\equiv 1\mod 3: \{ (m_1,x_2),(m_2,x_1),(m_3,x_3)\}$$
• $$N\equiv 2\mod 3: \{ (m_1,x_1),(m_2,x_3),(m_3,x_2)\}$$

Importantly, between these two analyses, we can see that for all $$N>1$$, the allocation to individual $$m_2$$ under $$P_{333}$$ differs from that of $$P_{323}$$. Since preferences are strict, $$m_2$$ must prefer one allocation to the other; since moreover these preference orderings differ only in the report of $$m_2$$, either outcome is feasible. It follows that the mechanism is not strategy-proof.

To address efficiency, we begin by considering the following additional preference ordering:

$P_{332}:\;\;\;\begin{array}{ccc}m_1&m_2&m_3\\\hline x_3&x_3&x_2\\x_2&x_2&x_3\\x_1&x_1&x_1\end{array}$

Following the logic of the previous discussion, we obtain allocations for $$P_{332}$$ of:

• $$N\equiv 0\mod 3: \{(m_1, x_2), (m_2, x_1), (m_3, x_3)\}$$
• $$N\equiv 1\mod 3: \{(m_1, x_1), (m_2, x_3), (m_3, x_2)\}$$
• $$N\equiv 2\mod 3: \{(m_1, x_3), (m_2, x_2), (m_3, x_1)\}$$

Putting all of this together, we can see that (restricting ourselves to the case of $$N>1$$)

• When $$N\equiv 0\mod 3$$, the allocation is not efficient for the preference ordering $$P_{332}$$: individuals $$m_1$$ and $$m_3$$ are strictly better off by swapping their final gifts
• When $$N\equiv 2\mod 3$$, the allocation is not efficient for the preference ordering $$P_{323}$$: individuals $$m_2$$ and $$m_3$$ are strictly better off by swapping their final gifts

The case of $$N\equiv 1\mod 3$$ is somewhat more complicated.

Exercise: show that, for all possible preference orderings of individuals $$\{m_1,m_2,m_3\}$$ over gifts $$\{x_1,x_2,x_3\}$$, the white elephant allocation is efficient when the number of permissible steals of a gift is $$N=3k+1$$, for any $$k\in\mathbb{N}_{+}$$.

By careful consideration, we introduce the following preference orderings:

$P_{54325}:\;\begin{array}{ccccc} m_1&m_2&m_3&m_4&m_5\\\hline x_5&x_4&x_3&x_2&x_5\\ x_3&x_5&x_2&x_4&x_4\\ x_4&x_2&x_5&x_3&x_3\\ x_2&x_3&x_4&x_5&x_2\\ x_1&x_1&x_1&x_1&x_1 \end{array} \;\;\;\;\;\;\;\;\; P_{55532}:\;\begin{array}{ccccc} m_1&m_2&m_3&m_4&m_5\\\hline x_5&x_5&x_5&x_3&x_2\\ x_4&x_4&x_3&x_4&x_3\\ x_3&x_3&x_4&x_5&x_5\\ x_2&x_2&x_2&x_2&x_4\\ x_1&x_1&x_1&x_1&x_1 \end{array}$

Iterating the previous analyses — albeit in a somewhat more intricate and involved manner — we find that:

• When $$N\equiv 1\mod 9$$, the allocation is not efficient for the preference ordering $$P_{55532}$$: individuals $$m_1$$ and $$m_5$$ are strictly better off by swapping their final gifts, $$x_2$$ and $$x_3$$
• When $$N\equiv 4\mod 9$$, the allocation is not efficient for the preference ordering $$P_{54325}$$: individuals $$m_2$$ and $$m_4$$ are strictly better off by swapping their final gifts, $$x_2$$ and $$x_4$$
• When $$N\equiv 7\mod 9$$, the allocation is not efficient for the preference ordering $$P_{54325}$$: individuals $$m_1$$ and $$m_2$$ are strictly better off by swapping their final gifts, $$x_2$$ and $$x_3$$

The above cases constitute a proof that the white elephant allocation is not necessarily efficient when $$N\equiv 1\mod 3$$ (since in this case we must have $$N\in\{1,4,7\}\mod 9$$). Since in each case ($$\mod 3$$) there is a preference ordering which is not efficient, it follows that the allocation induced by white elephant gift exchange is not (in general) efficient. $$\square$$

Does anything change if giftees are randomly ordered, rather than exogenously labeled $$m_1$$, $$m_2$$, etc.? It is clear that efficiency must also fail in this setting: since individuals would in any case be happy to trade their ex post allocations, they would surely be willing to trade probability shares over possible allocations.

Strategy-proofness is a trickier issue. In fact, for systems with three agents and three gifts, this random mechanism is strategy-proof. I'll leave the rest for a later date, at which time it's probably worth considering the fact that, in actual white elephant, gifts are not left unwrapped in the central pile (i.e., there is uncertainty surrounding the selecting of a gift from the pile, but near-total certainty regarding theft). There are of course variants in which the gifts are unwrapped — this is the way my family distributes prizes to mini-golf tourney winners, for starters — so the lack of informational frictions in this discussion may not be such a terrible oversight.

### conclusion

A (stylized) variant of white elephant isn't such a good idea, if your goal is to distribute holiday gifts in an efficient and truthful manner. Of course, that's not to say that this should be your goal in such a game; but leave it to economists to ruin anything.

Included $$\LaTeX$$ graphics are generated at LaTeX to png or by .