-
Notifications
You must be signed in to change notification settings - Fork 10
/
README.Rmd
160 lines (132 loc) · 7.79 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
---
output: html_document
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r, echo = FALSE,message=FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "README-"
)
```
# The Game Theory of the Yankee Swap
### Introduction
What is the best strategy for a Yankee Swap (also known as a white elephant exchange)? This model attempts to use game theory to find the answer.
For a story and video based on this analysis, see [here](http://fivethirtyeight.com/features/white-elephant-yankee-swap-game-theory).
This model is inspired partly by [this approach](https://github.com/analyzestuff/posts/blob/master/white_elephant/white_elephant.R) by Max Ghenis. Thanks also to Max for providing some helpful coding suggestions.
Comments/questions/feedback? [email me](mailto:[email protected])
### Rules and Assumptions
There are endless variations of the game, some of which have significant strategic implications. The optimal strategy also depends heavily on underlying assumptions about how different players value each gift and how well they can estimate those values.
##### The rules of Yankee Swap used here:
- N players each bring one gift.
- Each round, a player can choose to pick a new gift or steal someone else's gift.
- If a person steals a gift, the steal-ee makes the same choice. (See code for `variant.R` to see an alternate version of this rule.)
- Players can't immediately "steal back" a gift that was just taken from them.
- Gifts cannot be stolen more than a fixed number of times each.
- OPTIONAL RULE: The first player gets a final turn at the end. Can set this by toggling the value of `extra` in the code.
##### A few assumptions:
- Gifts have an underlying value that is the same for all players (but not known to them).
- Gifts have a specific value to each individual player (based on the underlying value).
- Players can perfectly assess a gift's value to them, but NOT the underlying value (might be interesting to play with this assumption).
- Goal for each player is to maximize the (specific to them) value of the gift they hold at the end.
##### This model tests eight strategies:
1. Player steals with probability p = (number of gifts taken) / N (naive).
2. Player always steals most valuable gift available.
3. Player always steals second-most-valuable gift available (if only one gift is available, player steals that one).
4. Player never steals.
5. Player steals if any stealable gift has value (to them) greater than the mean value of all opened gifts.
6. Player steals about-to-be unstealable gift (steals == max.steal - 1) if one is available with a value greater than the mean value of all opened gifts.
7. Same as #5 but factor in knowledge of the gift the player brought.
8. Ghosh-Mahdian: Player steals if best available gift has value > $\theta$
**Note:** Stragy #8 is based off the approach developed by Arpita Ghosh and Mohammad Mahdian in [this paper](http://www.arpitaghosh.com/papers/gift1.pdf).
Player steals if value of best available gift exceeds $\theta$, where $\theta_i = \theta_{i-1} - \frac{\theta_{i-1}^{2}}{2}$
### Model Design
The model allows the user to adjust five variables, with the following presets:
```{r}
n.play <- 15 # Number of players
max.steals <- 3 # Maximum number of times a gift can be stolen
v <- .9 # How much variance is there in how different players assess value of gifts?
iterations <- 10000 # How many iterations.
extra <- FALSE # Does first person get an extra shot at the end?
```
The model randomly assigns:
- A strategy (1-8) to each player;
- An underlying value (between 0 and 1, evenly distributed) to each gift;
- A player-specific value for each player-gift combo, using the following formula:
```{r}
values <- data.frame(gifts = 1:n.play)
for (i in 1:n.play){
values[c(i + 1)] <- sapply(gifts$underlying.value, function(x) x * runif(1, min= 1 - v, max = 1 + v))
names(values)[i + 1] <- paste0("player_", i)
}
```
### Analysis
A few clear takeaways quickly emerge. (Charts are based on 10,000 iterations using default parameters, unless otherwise indicated.)
##### Player order
There is a big advantage to going later, and a particularly large advantage to going last. (Going first also seems to be slightly better than going second.)
```{r, echo = FALSE, message = FALSE}
require(dplyr)
require(ggplot2)
cumulative %>%
group_by(player.no) %>%
summarize(score = mean(result)) %>%
ggplot(.,aes(player.no,score)) + geom_line() +
ggtitle("Value by order of draw") + xlab("Player position") + ylab("Score")
```
##### Strategy
Strategy matters! Specifically:
- Never stealing is a terrible strategy;
- So, somewhat surprisingly, is the "take the second best" strategy;
- Strategies based on the expected value of unopened gifts (5,7 and 8) perform best, but;
- The simple "always steal" does surprisingly well;
- There is little difference in outcome between models 5 and 7.
```{r, echo = FALSE, message = FALSE}
require(dplyr)
require(ggplot2)
load("results_10k_iterations.RData")
cumulative %>%
group_by(strategy) %>%
summarize(score = mean(result)) %>%
ggplot(., aes(factor(strategy), score)) + geom_bar(stat = "identity") +
ggtitle("Value by Strategy") + xlab("Strategy") + ylab("Score")
```
We can see this using a regression analysis, controlling for player order:
```{r, message = FALSE}
regress <- lm(result ~ factor(strategy) + player.no, data = cumulative)
summary(regress)
```
Strategy is less important earlier in the game. Here are the same strategy-payoff charts for early (players 1-5), middle (6-10) and late (11-15) players.
```{r, echo = FALSE, message = FALSE}
require(dplyr)
require(ggplot2)
cumulative %>%
filter(player.no < 6) %>% # Early drawers
group_by(strategy) %>%
summarize(score = mean(result)) %>%
ggplot(., aes(factor(strategy), score))+geom_bar(stat = "identity")+
ggtitle("Value by strategy for early drawers") + xlab("Strategy") + ylab("Score")
cumulative %>%
filter(player.no >= 6,player.no < 11) %>% # Middle drawers
group_by(strategy) %>%
summarize(score = mean(result)) %>%
ggplot(., aes(factor(strategy), score)) + geom_bar(stat = "identity")+
ggtitle("Value by strategy for middle drawers") + xlab("Strategy") + ylab("Score")
cumulative %>%
filter(player.no >= 11) %>% # Late drawers
group_by(strategy) %>%
summarize(score=mean(result)) %>%
ggplot(., aes(factor(strategy),score)) + geom_bar(stat = "identity")+
ggtitle("Value by strategy for late drawers") + xlab("Strategy") + ylab("Score")
```
This can be tested formally by adding an interaction term between player order and strategy (results omitted for space):
```{r,eval = FALSE}
regress <- lm(result ~ factor(strategy) * factor(player.no), data = cumulative)
summary(regress)
```
##### Other notes & future analysis
- Changing variation of preferences affects shape but not overall conclusions. The greater the variation,the more important both strategy and player order become.
- Allowing gifts to be swapped more times makes the game take forever but doesn't change overall outcomes. (Allowing unlimited swaps can turn into a literally unending game if no other stop-points are built in.)
- The `extra <- TRUE` option, in which the first player gets an extra turn, gives a massive advantage to going first. It's actually much *less* fair than the default rules.
- Choice of strategy matters much less in the `variant.R` model, in which a stealee **must** open (no chains of steals). The relative ranking of the strategies changes little, however, with the exception that strategy #3 (steal the second best gift) performs far better under the alternative rules.
- It would be interesting to test a model in which players are able to estimate each other's preferences and adjust their strategies accordingly.
- It would also be interesting to test each strategy against the naive strategy (i.e. every player except one plays strategy #1).