A popular game at holiday parties in North America is the [white elephant gift exchange][1]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. [1]: http://en.wikipedia.org/wiki/White_elephant_gift_exchange