The optimal white elephant strategy

To answer these deep philosophical questions, I wrote a gift exchange simulator to test different strategies against each other as well as help me answer some of these other troubling questions.

Check out my analysis and answers below.

The game setup

There are lots of different game configurations for white elephant gift parties and the rules can have a major impact on the probability of getting a good gift depending on your position and strategy. For the purposes of the simulation code I wrote, I assumed the following game rules.

• There are N players and each brings a gift.
• Players gift selection position in the game is random.
• Each round a player can choose to open a new gift or steal a gift. If they steal, the person they stole from has the same options.
• Within one round, a gift can’t be stolen twice.
• A gift can be stolen only up to a maximum number of times.

Optionally, I also considered the game rule where the first player to go gets an extra turn at the end of the game.

Game algorithm and strategies

The simulator I wrote tests five different strategies:

1. Always open a gift – The player always opens a random gift if there is one available. If not, they randomly steal a gift. This strategy is not likely to perform well given that the player isn’t really optimizing for anything, but it helps set a baseline for comparison. Additionally, I feel like I’ve played with people that take this approach. They just want to open gifts and don’t really care what’s available to steal.
2. Always steal – The player always steals an already opened gift with the highest value. If no gifts are available, then open a random gift.
3. Steal on coin flip – The player flips a coin and if it’s tails, they steal the highest value opened item. Otherwise, open a random gift.
4. Steal based on mean – Based on the current mean value of opened gifts, steal the highest value item that is above the mean. Otherwise, open a random gift. This article was the inspiration for this strategy.
5. Optimize for no steals – Based on the current mean value of opened gifts with MAX_STEALS – 1 steals, take the gift with the highest value above the mean. Otherwise apply the always steal strategy.

Assumptions:

• I’m assuming that all players perceive the value of a gift the same
• All players are trying to optimize the value of the gift they receive

The simulatOR setup

The simulator creates N players and N gifts. For each gift, the simulator assigns a random gift value between 0 and 1. For each player, the simulator assigns a randomly selected strategy. Then the game is plays out M times, keeping track of positional and algorithmic performance.

You can see the Java code for this below or the exact implementation here.

// Run game simulation
for(int i = 0; i < iterations; i++) {
  List<Gift> gifts = initGifts(totalPlayers);
  List<Player> players = initPlayers(totalPlayers);

  // Setup game with players, gifts, and rules
  YankeeSwap yankeeSwap = new YankeeSwap(players, gifts, maxSteals,         
        letPlayerOneGoAgain);

  while(gifts.size() > 0) {
    yankeeSwap.playGame();
  }

  // Store history of the game
  gamesLog.add(players);
}

Tests

I ran a variety of tests. For all tests, unless otherwise specified, I assumed there were 20 people playing, I used a maximum of 3 gift steals per gift, and I ran 100,000 games to compute the averages.

The first test I ran was to answer the question does the order you select a gift matter?

Does order matter?

Long story short, yes, yes it most certainly does.

If you look at the graph below, the y-axis represents the average gift value players received after 100,000 simulated games. Clearly, there’s a huge disadvantage to choosing early. This levels out a bit through the middle point of the game and then goes up again during the final selections.

I was curious how the maximum number of gift steals might impact this distribution because if the number of steals is really low, then presumably someone who is later in the game has less options to steal. I ran the same 100,000 games again but with a maximum number of steals of only one. The results are below.

As you can see, the distribution flattens out earlier, but there’s still a noticeable advantage to choosing late in the game.

And here’s one more test where I increased the maximum steals to 10. In this scenario, few items are likely not stealable, giving late stage players the ultimate flexibility to take what they want and optimize their outcome.

Does your strategy matter?

So clearly position matters, but what about the strategy you use?

The graph below shows the results comparing the average gift value based on the strategy used by the player. Unsurprisingly, always opening a gift is not ideal. Surprisingly, the pure greedy method of stealing the highest value item currently available does very well.

I wanted to see if a player’s position could be offset by strategy. I setup the simulator such that the first 10 players to play used the steal above the mean strategy and the last 10 used the always open strategy. The chart below shows the impact of this.

Clearly, the first 10 players are playing a completely different game than the next 10.

However, changing the final 10 to use a slightly better strategy of flipping a coin and then based on the outcome of the flip choosing to steal the best gift is enough to still outperform the optimal strategy based mostly on the player’s position in the game.

Taking this idea further, I looked at the impact strategies have on different stages of the game: early, mid, and late. Stages are evenly distributed across the total number of rounds/players. For example, if the NUM_OF_PLAYERS = 21, then the early stage is rounds [0, 7), mid stage is [7, 14), and late stage is [14, 21). The image below shows the average gift value based on algorithm and game stage.

It appears that the strategy used has the most impact in the later stages of the game. There’s only so much you can do in the early stages as a player’s options are limited.

For example, a player stealing above the mean can only improve their gift value by a factor of 1.7X during the early stage of the game compared to just always opening a gift. However, in the later stage of the game, the same strategy can yield a 2.2X improvement.

How much does allowing the first player to go again matter?

In some versions of a white elephant party the first player is able to play again once all players have a gift. Presumably, this is to help the first player overcome their positional disadvantage. It’s clear from the earlier tests that the first position is at a big disadvantage regardless of the strategy they use.

In this test, I let the first player play again after all players had received a gift. As you can see from the graph below, this puts the first position on equal footing with the final player and shifts the worst player positions to players two and three.

Final thoughts

In the spirit of Greg Davies, “What have we learn today?“

We learned that the order players participate in a white elephant party drastically impacts their chances of getting a good gift. We also learned that strategy does matter and ideally, you should be optimizing to steal based on the current mean value of open gifts. If that feels complicated, using the greedy method of stealing the highest value item is still a pretty solid strategy. Finally, using the first player goes again rule does significantly help the first player, but someone (namely players two and three) is still going to walk away with a terrible gift.

There’s a version of the game where someone always opens a gift first and then chooses to steal. That could be interesting to analyze as well. I suspect it causes fewer cascading steals since the current player might just open a good gift and end the round. Additionally, since every player is bringing a gift with them, they could factor the value of that gift into their strategy. For example, when calculating the mean of known items, a player’s existing unwrapped gift could be part of that calculation. I didn’t account for this in my code, but could be something interesting to consider.

If you have ideas for strategies or analysis, please let me know, or grab the code and try it out yourself.