## Addressing the (white) elephant in the room

Hi Folks,

As the final icicles begin to melt around Ithaca, it’s time to admit that the yuletide season is firmly behind us. That being said, when we first learned about matching markets with one-sided preferences, I immediately thought of America’s favorite Christmas party game, allegedly popularized by Cornell’s very own Ezra Cornell: the white elephant gift exchange. For anyone who is unfamiliar with this tradition, it essentially works like this:

• Each player contributes a wrapped gift to the exchange: N participants —> N gifts
• An ordering f(n) is randomly set amongst players. Here, f(n) = player with nth priority.
• Player f(1) begins the exchange by selecting and unwrapping one of the N gifts.
• Iterating through the ordering, each subsequent player f(n) may either:
1. Select and unwrap one of the remaining N-n-1 unwrapped gifts, or
2. Steal one of the known items—i.e., steal an item from a player in {f(1)…f(n-1)}
• If option 2 is chosen, then the player that is stolen from faces a similar choice: either steal from a player who already has a gift, or select an unwrapped gift from the ones that remain. This process continues until someone chooses the latter option (selecting an unwrapped gift).
• The game ends when the last player has taken her turn, and any resulting trade necessitated by her move has been completed.

It is clear from this definition of the gift exchange that, if one gift in particular is extremely coveted by everyone, then item #2 may never actually end: everyone will keep stealing the coveted item over and over again, and nobody will ever select an unwrapped gift. We will therefore add the following restriction: no gift may be stolen more than once within each turn.

Now, let’s put this game into the context of matching markets with one-sided preferences. We have a set of players P, and a set of gifts G, such that |P| = |G| = N. At any step in the game, we can further partition G into a set of unwrapped gifts Gu, and a set of wrapped gifts Gw. The tricky part now becomes formulating each player’s preferences.

On the one hand, we may assume that, at all k turns in the exchange, each player pi: i ∈ {1,2…N} has strict preferences g1,pi ≻ g2,pi ≻ … ≻ gk,pi over the k unwrapped gifts g ∈ Gu, and is indifferent amongst the set Gw of remaining wrapped gifts. However, we cannot figure out how each player pi is merging these two sets of preferences; in particular, for any given k and pi, we are not sure if pi’s complete preference profile looks something like this:

(1) g1,pi ≻ g2,pi ≻ … ≻ gk,pi ≻ Gw

something like this:

(2) g1,pi ≻ g2,pi ≻ …Gw… ≻ gk,pi

or even something like this:

(3) Gw≻ g1,pi ≻ g2,pi ≻ … ≻ gk,pi

Thus, the set of preferences ≻ = (≻pi)pi∈P is not well defined on its own. Suppose for simplicity, however, that we have some extra information that allows us to tell for each player pi whether their preferences follow type (1), (2), or (3)—in other words, suppose that we can fully specify each player’s preferences at each step in the game. This is conceivable, for example, if we have access to information on each player’s risk aversion. Recall that a mechanism consists of a rule that assigns a matching for each tuple (P, G, ≻ ); because we now have a setup that fully describes these tuples, we can start thinking of the white elephant exchange game as a sort of mechanism!

Pareto-efficiency:

We’d like to know whether the white elephant exchange is a Pareto-efficient mechanism. Consider this counterexample:

• players A, B, C; gifts x, y, z
• ordering f(i) is alphabetical
• all players have preferences of type (3): Gw≻ g1,pi ≻ g2,pi ≻ … ≻ gk,pi
• when Gw becomes empty after the last round, all gifts are unwrapped, and players finally form strict preferences over all of G. Suppose in this case their true preferences are as follows:    A: x>y>z, B: y>z>x, C: z>x>y

The implication from the third bullet point is that, rather than stealing an unwrapped item, each player will randomly select from the wrapped gift pile at his or her turn. Thus, if A randomly draws z, B randomly draws x, and C randomly draws y, the matching produced will be as follows: A-z; B-x; C-y

Clearly, this matching is not Pareto-efficient; each player is getting their last choice, while the matching A-x; B-y; C-z would prove to be a strict improvement for all three agents. Thus, the white elephant gift exchange mechanism is not Pareto-efficient.

Strategyproofness:

Consider the following example:

• players A, B, C, D, E; gifts v, w, x, y, z
• ordering f(i) is alphabetical
• players C, D, E, have preferences of type (1): g1,pi ≻ g2,pi ≻ … ≻ gk,pi ≻ Gw.
• players A and B have preferences of type (3): Gw≻ g1,pi ≻ g2,pi ≻ … ≻ gk,pi. Thus, the first two turns of the game are random draws from the wrapped gift pile. Suppose these random draws give the output A-v, B-w.
• Now, at the third round, suppose C and D both have true preferences v ≻ w ≻ Gw . Meanwhile, suppose E has true preferences w ≻ v ≻ Gw .

If C is honest, she will steal item v from player A. However, the next round, D will just steal v away from C. Thus, if C is honest, she will not end up with v.

However, suppose that holding all else constant, C reports false preferences w ≻ v ≻ Gw . According to the mechanism, C will now steal gift w at step 3, and D will steal gift v at step 4.

Ok, here’s the cool part. On E’s turn, E will steal gift w away from C. According to the rules of the game, C is now free to either steal from someone else, or take the last wrapped item. If C steals gift v from D, she has managed to end up with her most-coveted item! Recall that items may only be stolen once per turn—this ensures that C has effectively ended the game with her top choice, v.

Because agent C has benefitted by reporting something other than her true preferences, the white elephant gift exchange mechanism is not strategyproof!

Concluding thoughts: This game, while simple to learn, clearly has some complex interpretations when put into the context of matching markets with one-sided preferences. Interestingly enough, there really isn’t much research out there on the intricacies of this mechanism. It would be interesting to also incorporate some analysis using game theory and behavioral economics to model players’ preferences.

Source:

https://www.jstor.org/stable/3119303?seq=1#page_scan_tab_contents