Welcome to analyze stuff! For our first post, I wanted to reflect on the time of year; after all, ‘tis the season for hams and yams, caroling and sledding, and of course gifts! One popular party gift exchange game is the White Elephant, where each person brings a wrapped (typically regifted or otherwise odd-ball) gift, and then picks one in order with the option of “stealing” another unwrapped gift. Relative to other matching problems, for example, the stable marriage problem or the secretary problem, both of which have elegant defined solutions, strikingly little research has been done on the fairness of this game (with perhaps one exception).
|Sample game outcome|
Player 1 gets gift 3, 2 gets 6, and so on
- Each round consists of a new player joining the game, based on a predetermined order
- At each round, the player either steals an unwrapped gift or unwraps one herself
- Upon someone else’s gift being stolen, the “stealee” makes the same choice of stealing vs. choosing. A round completes when someone unwraps a gift. While this part is consistent, the following rules are subject to variation:
- No gift can be stolen more than once per round
- No gift can be stolen more than three times total
- The game ends when the final gift is unwrapped
- Players will steal each round with probability p = (# stealable gifts) / (# stealable + wrapped gifts)
- If players choose to steal, they will steal their favorite gift
- Players’ preference for each gift is governed by averaging two uniformly--that is, U(0, 1)--distributed factors:
- Each gift’s innate utility (players will partially agree that some gifts are better than others)
- Preferences differing randomly across players
- Gift utilities are completely unknown prior to unwrapping, i.e. I’m assuming players can’t tell the difference between a wrapped fruitcake and a wrapped Ferrari
> result n.players player gift steals utility rank run 1: 1 1 1 0 0.5550705 1 1 2: 1 1 1 0 0.5971866 1 1 3: 1 1 1 0 0.4942946 1 1 4: 1 1 1 0 0.6106313 1 1 5: 1 1 1 0 0.7207114 1 1 --- 2099996: 20 16 10 1 0.7030580 10 20 2099997: 20 17 17 0 0.5422361 9 20 2099998: 20 18 18 1 0.6655989 2 20 2099999: 20 19 20 1 0.7376923 4 20 2100000: 20 20 14 2 0.7768777 7 20
current.n <- 6 # Note that result is a data.table, enabling these operations result[n.players == current.n, list(mean.utility = mean(utility), mean.rank = mean(rank), pct.favorite.gift = sum(rank == 1) / .N, pct.least.favorite.gift = sum(rank == current.n) / .N), player]
Varying the number of players
library(ineq) # For Gini n.player.summary <- result[, list(mean.steals=mean(steals), mean.utility=mean(utility), mean.utility.first.player= mean(ifelse(player == 1, utility, NA), na.rm=T), mean.utility.final.player= mean(ifelse(player == n.players, utility, NA), na.rm=T), utility.per.turn=mean(utility / (steals + 1)), gini=ineq(utility, type="Gini")), n.players]
summary(lm(utility ~ n.players + player, data=result))
Call: lm(formula = utility ~ n.players + player, data = result) Residuals: Min 1Q Median 3Q Max -0.70304 -0.12404 0.01915 0.14726 0.47971 Coefficients: Estimate Std. Error t value Pr(>|t|) (Intercept) 5.147e-01 4.156e-04 1238.34 <2e-16 *** n.players -4.462e-04 3.309e-05 -13.48 <2e-16 *** player 1.057e-02 3.309e-05 319.28 <2e-16 *** --- Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1 Residual standard error: 0.2001 on 2099997 degrees of freedom Multiple R-squared: 0.05847, Adjusted R-squared: 0.05847 F-statistic: 6.521e+04 on 2 and 2099997 DF, p-value: < 2.2e-1
- Does an extra turn from player 1 affect overall utility, and equity of it? Since average utility rose and inequality fell as players were added, one might expect this extra turn to improve outcomes; however, such a rule may further diminish player 2’s already poor fortune.
- How about other variations? For example, some games only prohibit immediate steal-backs, while allowing gifts to be stolen multiple times in the same turn. This could reduce the final player’s advantage, since the current rules mean they typically get their first or second choice.
- How else could we evaluate fairness? Metrics like average utility and Gini coefficient tell part of the story; other alternatives could include comparisons to stable-match solutions as proposed by Gale-Shapley, or perhaps an efficiency measure more nuanced than raw utility per turn.
- When should players steal? An analysis of optimal stealing strategy could begin with tweaking each player’s stealing probability. However, the more interesting model assumes players try to estimate the utility distribution of all gifts based on those they’ve seen so far. From this distribution, they can weigh the odds that the next gift will surpass their favorite unwrapped one, and decide to steal accordingly. If a player sees ten fruitcakes unwrapped and then a Ferrari, they can be pretty sure the Ferrari is an outlier that won’t be matched in the next gift.
- Special thanks to Ben Ogorek for numerous suggestions and an extra set of eyes on the code.
- Thanks to Mindy Greenberg for a thorough review (in particular, weaning me off my semicolon addiction).
- Thanks to Bo Cowgill for introducing me to literature surrounding matching problems.