White elephant gift exchanges: mechanisms for fair division

Question

A popular game at holiday parties in North America is the white elephant gift exchange. In brief (ignoring variations) it works as follows:

There are $n$ people and $n$ wrapped gifts. Players are ordered arbitrarily. In the $i^{\text{th}}$ round, player $i$ either

• chooses a wrapped gift and unwraps it as their present
• "steals" one of the already opened gifts (from some player $k < i$).

If a player's gift is stolen, they now have the opportunity to do the same thing. A round is complete when a player chooses a wrapped gift.

While there are many variations in the system, one point to note is that the player going last has an unfair advantage because they alone are guaranteed the ability to choose any unwrapped gift.

THis falls under the class of fair-division methods pertaining to indivisible goods (unlike cake cutting).

My questions is:

Are there mechanisms for disbursing the gifts that are fair (in that each player has the same opportunity to choose a high value gift under their valuation) ?

Note that some flexibility will be needed in the definition of fair since the goods are indivisible and we are not introducing monetary compensation for players.

Answer 1

This isn't a complete answer, but it's an incomplete one.

Some background and related lit for those who aren't familiar --

A nice property would be envy-freeness, in which no player would like to trade with another after the mechanism is complete. Unfortunately, for indivisible goods and no money we can see that this is impossible (there might be one good that two people both think is best). The other common property is proportionality, where everyone gets what they consider to be a value of more than $1/n$; this is also clearly impossible to always obtain (there may be an item that nobody wants, but someone must end up with it).

[1] focuses on computing the minimum-envy allocation in an indivisible-goods scenario. They show that a minimum-envy mechanism cannot be truthful. However, we might still be able to design a game with a good price of stability (even though players aren't truthful).

[2] apply the criterion of "max-min fairness". The idea is to consider each player's valuation function over subsets of the items, normalizing it to one on the whole set, and to find the allocation which maximizes the minimum utility of any agent. Again, though, they don't consider our setting here with unit demand. Others study approximation algorithms for this problem, but I don't know if anyone has considered this restriction.

--

It's worth noting that usually notions of fairness are extremely worst-case: A mechanism is usually (perhaps not always?) considered envy-free if every player has a strategy that guarantees she will not envy any other's allocation. If she is playing to maximize her expected utility, she may or may not end up envious. Same goes for proportionality.

Because of this, it's tricky to try to relax these notions in a way that's natural when taken with this philosophical approach to fair division. It might be tempting to define a criterion like "ex-ante envy-freeness" where we hope to be envy-free in expectation (whatever that means). However, I think this would really be setting off on a whole new track from the current philosophy. If one were to do that, I think we should throw out notions of envy-freeness or proportionality altogether and start thinking about how expected-utility-maximizers would play these fair-division games in the first place.

Instead, we might try to extend the traditional approach in a more consistent way. One question would be how often (over the randomness of the mechanism) a player can guarantee herself a constant fraction of optimal utility. However, consider the case where only one of the $n$ items has any value; then any fair mechanism gives each player a constant-approximation to utility only $\frac{1}{n}$ of the time.

To get around this, I think we must consider ordinal criteria instead. I propose the following as a "natural" relaxation:

A mechanism in our setting is $(\varepsilon,\delta)$-envy-free if with probability $1-\varepsilon$ an agent can guarantee herself one of her favorite $\delta n$ items.

Considering the case where everyone values each item the same amount, we see that no mechanism can possibly do better than $(\varepsilon,\varepsilon)$-envy-freeness here. (For any $\varepsilon$ -- Because only $\varepsilon n$ agents will get one of their $\varepsilon n$ favorite items.)

On the other hand, it is easy to see that your mechanism, if we order the players uniformly at random, is $(\varepsilon,\varepsilon)$-envy-free for all $\varepsilon$.[3]

I don't pretend that this captures nearly all the interesting questions about this setting or the white elephant mechanism. For example, the $(\varepsilon,\varepsilon)$-envy-free strategy for the second player is to take the first player's gift unless it is the worst of all the gifts. However, I think that this shows that our worst-case solution concepts simply don't capture a lot of what's interesting about these scenarios, so we should maybe think about something else like utility maximization instead.

--

[1] Lipton, Markakis, Mossel, Saberi. "On Approximately Fair Allocations of Indivisible Goods." EC 2004.

[2] Bezakova, Dani. "Allocating Indivisible Goods." SIGECOM 2005.

[3] Well, so is random serial dictator, but random serial dictator often has nice properties in theory. I'm also assuming that each item can only be stolen once per round.

Answer 2

Much of the white elephant gift exchange experience is also controlled by random selection. A popular variation includes the rule that the first picks last, but that is not always included in the rule. This takes the unfair advantage of being randomly selected first out of the equation. Another rule requires that there are no direct "steal-backs" in the game. In addition, most games are played with a "three-touch" rule, that says that once opened, then stolen once, then stolen twice it becomes frozen from future stealing. This rule creates another level of unfair advantage to those who choose to pick a gift that has been touched twice.

Our recreation specialist as AlbinoPhant study these gift swap games all year long. If you want to add an extra random dimension to the game, use a Left-Right story within the game play. The story of Lefty the White Elephant is suggested as a sample.

The actual benefit of the exchanging of gifts within this activity is the social engagement that this process produces - The gifts usually are secondary to the fun of great banter. Nevertheless, all players leave with some level of gift reward.

Answer 3

What we did this year was restrict the people you could steal from so that the later players didn't have as large an advantage. So the $n$ players sat in a circle and they could only steal along edges of a graph $G$. Picking $G$ to be reasonably expansive is enough to "mix" the gifts; the simple expander graph we used is to assign players 1 through $n$, and you can steal from your adjacent neighbors or your modular inverse mod $n$.

Then we did 2 rounds to mix the gifts enough. Perhaps $\Omega(\log n)$ rounds would have been better to invoke the right expander mixing properties.

Well, the above describes what we would have done if the players had been interested in spectral graph theory and/or computing modular inverses :) We actually just played the normal way.