Solving Resistance

To solve a game is to learn how to play it best. Resistance has two teams (the good guys and the traitors), so each team's best strategy must be the best response to the other team's best strategy. Nash's theorem on the existence of equilibria guarantees that such a pair of best strategies exists.¹ [¹ If strategies allow random choices and players can each have a unique strategy, or under a number of other assumptions.]

These “strategies” tell each side what to do whenever they have to make a decision. As a group, the good guys decide who to send on missions throughout the course of the game, and the bad guys decide whether or not to let the mission succeed. Individual play involves more than this: you have to argue who should be on which mission, vote no-confidence in team captains, and accuse people of trying to take control of the game. Luckily, these details can be simplified away.

First, the team leader position is unnecessary. Since there is a best team for the good guys to choose, any good guy team leader would choose them.² [² When multiple strategies have the same likelihood of winning, a unique best can be chosen by numbering the players and choosing the lexicographically smallest equivalent team. Otherwise, bad guy team leaders would use their extra knowledge to choose bad "equivalent" options.] Any other proposal would be voted against, so no bad guy team leader would want to propose it. (If five team leaders' proposals are shot down, the bad guys automatically win, but no game size has five bad guys, so this edge case does not come up.) Similarly, accusing people of being bad guys because they try to take control of the conversation isn't necessary with optimal players, because optimal bad guys are indistinguishable from good guys.

When a team is selected for a mission, each team member chooses to sabotage the mission or not. Obviously, good guys never want to sabotage the mission. The bad guys might want to sabotage the mission, or might not (to stay hidden, say), but they need to coordinate if they don't want multiple sabotage cards to be turned in at once. I'm going to assume that bad guys can always do this: there is always one or no sabotage cards turned in.³ [³ For more than 7 players, the minimal number of sabotage cards is 2, and in this case I assume that two sabotage cards are turned in, but no more. In other words, there is never information in sabotage other than whether or not the mission succeeded.]

After these simplifications, the game is reduced to alternating rounds of the town deciding who to send on the mission, and the bad guys deciding whether or not to sabotage the mission. For both decisions, the groups know who was chosen for previous missions, and whether or not those missions succeeded.

This isn't that big a space of strategies. The smallest Resistance game is five players—two bad guys and three good guys. That means there are 10 possible teams of two (missions 1 and 3) and 10 possible teams of three (missions 2, 3, and 5). So there aren't that many possible sets of teams and outcomes: 20 per round, or less than 160 000 total.⁴ [⁴ And some teams can't fail, since they only contain good guys.] This is a small enough space that exploring it by computer becomes possible.

Furthermore, the space of strategies is actually much smaller. The good guys sometimes can't distinguish between players, especially in the earlier rounds. For example, there's no getting around choosing two players at random for the first round, because before the first round, all players have an identical, null history, and optimal bad guys don't act differently from good guys. So in fact there is only one strategy the town can have on the first day, and only three possible outcomes of that strategy (10% chance of choosing two bad guys, 30% of no bad guys, and 60% chance of one bad guys).

Given such a small strategy space, I decided to find the best strategy for the town by brute force. To keep things simple, I assumed the bad guys never want to allow a mission to succeed, and then will check that assumption later. To do the brute force, I implemented data structures for:

• Initializing game states
• Stepping games (knowing the players chosen and the outcome)
• Determining which players can be distinguished by the good guys and by the traitors
• Finding the distinguishable teams of players
• Weighing possible teams by their likelihood (since good guys can't distinguish between some players)
• Implementing backward induction to determine optimal play

The backward induction is the most interesting bit. The possible strategies are the good-guy-distinguishable teams. The value of each strategy is the probability of victory for each possible team from that strategy, weighted by the likelihood that the good guys, in their ignorance, choose that team. The optimal strategy is that strategy with the highest likelihood.

It's some gnarly code, but overall it works fairly well. It also did not require any optimization; it takes a second for 5 players and two seconds for 6. Larger games take longer, of course.

Once an optimal strategy is chosen, the next step is to check the assumption that bad guys always sabotage missions. To check this, I look to see whether the probability of winning is higher if the mission fails than it succeeds. If sabotaging the mission decreases the good guys' chances of victory, the bad guys will sabotage it; otherwise not. This requires computing optimal strategies (and probabilities of victory) for many game states—all those reachable by the optimal strategy. So the assumption checking is pretty computationally expensive.

All of the code is freely available; if it's buggy please let me know!

The most striking finding was that the bad guys should always sabotage a mission if they can. Against optimal play, it is never worth allowing a mission to succeed in order to "throw the good guys off". For example, I've played many games where we long debated whether a successful first mission could possibly have bad guys on it. If you otherwise play optimally, it's not worth worrying about. If the bad guys could have sabotaged it and didn't, they made a mistake. (In fact, it seems there is a guaranteed win for five players in this case.)

The overall chances are that the good guys win 80% of the time. This matches with some suggestions I've heard that Avalon was intended to fix a significant imbalance in the game. 80% seems high, but I'm not sure the optimal game has that chance at 50%. In particular, more people are on the "good guys" side, so it makes sense for that team to win slightly more often.

More precisely, suppose that winning, when the odds of winning are \(p\), gives you utility \(\log p\). If the teams were of equal size, then the optimal \(p\) would optimize \[ f(p) = p \log p + (1 - p) \log (1 - p) \] The optimum here is \(p = \frac12\).⁵ [⁵ Taking the derivative yields \(\log p = \log (1 - p)\).] However, for a five player game, there are 3 good guys and 2 bad guys, so the optimal probability should be slightly higher; it should optimize \[ f_5(p) = p (3 \log p) + (1 - p) (2 \log (1 - p)) \] which is maximized at about \(p = .5698\).⁶ [⁶ The exact form is amazingly complex.] Of course, I just made up the \(\log p\) utility function, so you can sub in your own, but I tried a few functions and kept getting numbers near about 60%. Of course that makes sense, since that's the breakdown of players. So in fact, 80% chance of victory is still too high.

At higher player numbers, the game is more balanced, with 8 players getting very close to the optimum:

Players	Win%	Goal%
5	80%	60%
6	80%	66%
7	71%	57%
8	57%	62%

Are there alternative five-player games that are a bit more balanced? Well, for five players, you can't increase the number of bad guys (if they make up a majority, they always win, since they win votes). So the only thing you can change is the team sizes at each round. Here are various sequences of team sizes, and the town win probability for each:

Win%	R1	R2	R3	R4	R5
80%	2	3	2	3	3
80%	2	3	3	3	3
70%	3	3	3	2	2
70%	3	3	3	3	2
70%	3	3	3	3	3
60%	5	2	2	2	2
50%	4	3	3	3	3
50%	2	3	4	3	3
50%	4	3	2	3	2
40%	2	3	2	3	4
30%	3	3	4	3	3

It looks in general like small teams early in the game help the town, presumably since they give more info. But the variants 4/3/3/3/3 and 3/3/4/3/3 break this streak, and in general:

Win%	R1	R2	R3	R4	R5
50%	4	3	3	3	3
50%	3	4	3	3	3
30%	3	3	4	3	3
30%	3	3	3	4	3
30%	3	3	3	3	4

Here the larger group early seems to help.⁷ [⁷ Actually… Shouldn't a team of size 4 always fail? I think I have a bug…]

The optimal game mode, according to this table, seems to be 2/2/2/2/5. That's not an interesting game, though. It's instructive to consider the 30% win rate option 2/2/2/5/5. The 30% win rate comes from the fact that 30% of pairs don't contain bad guys, so if you pick such a group on the first round, you're good, and otherwise you're not. With 5/2/2/2/2 things are similar. 30% of the time the first round wins the game. Otherwise, pick two of the remaining guys. Either way, the strategy is very very simple and comes down to basically luck. So I wouldn't recommend this modification, even though it achieves "optimal" win probability.

More generally, the game becomes quite boring once you realize that against optimal play, the bad guys always sabotage. Knowing this, it is not too hard to figure out optimal play as you go.

Though these experiments are fun, they only cover particular player numbers. The most striking result is that bad guys should always sabotage, and that's the biggest take-away. However, while I have empirical results demonstrating that fact by brute force enumeration, I don't have any concise explanation for it. Is there a clever thought experiment or comparison that shows why sabotaging is always better?