White elephant gift exchanges: mechanisms for fair division
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.