White elephant gift exchanges: mechanisms for fair division 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
&quot;steals&quot; one of the already opened gifts (from some player $k &lt; 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.
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.