A puzzle of trust and lies, allies and spies

Question

Here is a puzzle involving distrust and asymmetric knowledge. (It was inspired by, but not exactly following, the board game The Resistance: Avalon.)

There are ten resistance fighters trying to overthrow the evil empire. Among them there is actually a secretive resistance leader, 5 loyal allies, 3 spies, and an assassin.

The "good characters" (the leader and the 5 loyal fighters) out number the "evil characters" (the 3 spies and the assassin). The assassin and spies know each other, and the leader knows who all the evil characters are. Therefore by elimination the leader and the evil characters know who is 'good', but the evil characters don't know who the leader is, and the leader doesn't know who the assassin is.

The resistance fighters need to select teams to send on missions against the evil empire. They meet in a secret lair to discuss and vote on plans. The characters take turns (initial order is randomly chosen) being a "team captain", where the team captain selects people to send on the mission. Discussion can occur, the captain picks a team (not necessarily including himself), more discussion can occur, and then the captainr calls a vote to end discussion, and everyone votes whether or not to accept the team. Discussion can be done publicly in the war room, or take turns privately going off in pairs to discuss and come back to the war room. After a vote:

• If the team is accepted, the team is sent off on the mission. If there are enough evil characters on the mission, they can choose to secretly sabotage the mission so that it fails (they can also choose not to, in order to confuse the good guys trying to figure out who the spies are), otherwise the mission succeeds. The spies and assassin are good enough in their sabotage that the good characters don't know who caused the sabotage. The players gather again at the war room, to decide the team to send on the next mission.

• If the team is rejected, the next character around the table will act as team captain, and another attempt is made at selecting a team for the mission.

The details of the missions are:

mission    people to send     evil characters needed to sabotage
  #1             3                  1  
  #2             4                  1
  #3             4                  1
  #4             5                  2
  #5             5                  1

After the last mission, as a last ditch effort, the assassin can try to guess the leader and kill him.

The good characters win if:

• They succeed in at least three missions, and the leader is not killed.

The evil characters win if they can do one of the following:

• They sabotage at least three missions.
• They kill the leader at the end.
• Five successive votes for a team to put on a mission fails (good out number evil, so they can always prevent this, and with 5 votes this guarantees at least once the team leader was good).

---

The good have more in number, yet every evil character has full knowledge of who is good and evil, while only one good character does. Can you think of a strategy to help the good guys defeat the evil empire?

1: Is there some strategy the good characters can use when discussing and voting to eventually distinguish lies from truth and maximize their chance of beating the evil empire? What is the maximum probability of winning this strategy gives them?

2: Now consider if, in a twist, the leader only knows 3 of the 4 evil characters, and therefore cannot deduce at the beginning who all the good characters are. What is the optimal strategy now?

Answer 1

I'm not sure how to approach #2. Someone clever can probably come up with something better using the ideas here.

Alright for situation #1, where the leader knows all the evil characters, it is possible for good to win 5/6 of the time (the best possible, as with no knowledge the assassin can always just randomly kill one of the good guys hoping that it is the leader).

After gathering in the lair, any good person can suggest the following plan forward:

1. this strategy will allow good to win, so provably deviating from this plan will indicate you are evil

2. the characters should come up with a means of verifiably signing a note (possibly something as simple as an elaborate signature that no on there has the skill to forge, or more mathematically, publicly stating public keys for a signature algorithm)

3. the characters should go off in pairs to secretly discuss, until every possible pair has had a chance to discuss privately, and during this time the players will exchange signed notes stating (possibly lying) to each other one of the following:

   3a) declaring themself as not the leader

   3b) declaring themself as the leader, and stating who all is good

4. During these private discussions the leader, as he has knowledge of who all is evil, should declare "leader" to all good guys, and "not-leader" to all evil. Normal loyal fighters should just declare "not-leader" to everyone. Therefore the evil characters gain no information from these private discussions.

5. if a good player gets a message deviating from this rule, they can publicly release the verifiably signed message for that communication to out the evil person. So evil effectively must pretend to be normal good or the leader.

6. More generally, the strategy is for a good person to publicly expose any fake leader (release his messages) if they can prove they are fake without giving information about the leader.

   For example, if a fake leader ever claims another person claiming to be leader is good, this outs themselves as fake, as this cannot occur for the real leader if the good guys follow the plan. Unfortunately, a good person might need to keep this to themself, as revealing this could reveal information about the actual leader. However if multiple "leaders" choose groups such that there is no consistent way for one to be real (for example two claiming each other as good, or three claim such that it makes a cycle), then the entire group is fake and should be exposed as the evidence doesn't depend on who the actual leader is.

7. Now the characters gather in the war room for some public discussion. Each player states which groups of good guys were declared to them by people claiming to be leader. (Note: only the proposed groups of good are released, not who claimed the group.)

8. If there is a group declared such that not everyone in the group states they were told they are in the group, then that group is clearly false (as good has no reason to deviate from the plan).

   Since the number of good characters = 6, and the number of evil characters = 4, any group with the correct number of people will necessarily include at least two good. This means the evil characters don't have full freedom in how they mislead here.

9. If there is a player who appears in all proposed sets of good players, he must be good. All good players should release the messages they got from "leaders" to this player. Now even more restrictive than before, this player then can expose fake leaders whose group selections include each other in a revealing manner.

10. If there is enough information that every one should be able to deduce enough good players to succeed 3 missions without revealing the leader, someone can just explain it. Good, having superiority in numbers, can now ensure the correct mission teams are sent.

11. If there is currently not enough information to determine the correct teams to send on the missions, the mission captain picks a team which will eliminate as many proposed "good groups" from consideration as possible if it fails. If it is the leader's turn to be the mission captain, he should do the same, even if it means failing a mission, so that no information about the leader is lost here. If the mission wouldn't actually eliminate a possible "good group", and the person still insists on this mission team anyway, it outs themselves as evil and good can vote the mission team down. (Note this of course does not indicate good/evil for the team they suggested though.) So evil has to play along here to try to help narrow down a team.

12. If the mission fails, it should by design eliminate at least one, if not more, proposed "good groups". If the mission succeeds, it provides no information. Proceed to pick a team for the next mission.

---

Now let's analyze this plan.

There may not be enough information immediately available to succeed every mission. But I believe there is enough information here to guarantee succeeding at least three which is all that is necessary to win.

For simplicity I'll refer to a proposed group of good characters by someone claiming to be a leader as a "set". And we'll look at what information we can gain from these sets.

Some simple deductions:

• Since there is only one real leader, once the sets are shared it is obvious to everyone how many people are trying to fake being the leader (even though they don't all know who specifically is claiming to be a leader).

• Every time a mission fails, at least one set can be eliminated, so there have to be at least 3 fake leaders for team evil to have a chance. Less than this and straightforward application of the plan above is enough to win. So there need to be 3 or 4 fake leaders for evil to have a chance.

• If a set is eliminated, a good player can reveal the message from that fake leader making it clear who at least one evil person is. Any set containing that character is thus clearly wrong as well.

• Similarly, a good player can reveal a message from a fake leader if he claims that evil person is good. And so on.

• If only three evil characters fake being a leader, then they can't win if two sets are revealed as wrong in a single sabotaged mission, so none can include another fake leader in their sets. This means all fake leaders must have 4 good characters for their set, to have a chance. So for the first three missions, chose a team from such an intersection. Either this team is actually good (so it won't fail, and good will win the first three missions), or if evil sabotages it, it will eliminate two sets (since regardless who was evil, they were in both sets) and thus evil can at most sabotage only one more mission (as only at most one set from a fake leader remains), and so good wins. Thus evil cannot win with only 3 fake leaders.

• If there are 4 fake leaders (every evil character fakes being a leader), they can only afford to lose two sets at once on at most one mission, therefore at least two cannot include any other evil character in their set. Thus at least two fake leaders must select 5 good characters for their set, to have a chance. So if there are not two intersections of 5, play trying to eliminate sets as normal and good will win. Otherwise select from an intersection of 5 to send on the missions, and good will win.

Therefore team good can guarantee to win at least three missions without revealing who the real leader is.

---

For #2, it is very risky for the leader to reveal himself to anyone, since he doesn't know for sure who is good. Since there are more good characters, let's see what would happen if relied on chance and just publicly rolled dice for who to send on a mission.

chance of passing mission 1: (6*5*4)/(10*9*8) ~ 16.7%
chance of passing mission 2: (6*5*4*3)/(10*9*8*7) ~ 7.1%
chance of passing mission 3: (6*5*4*3)/(10*9*8*7) ~ 7.1%
chance of passing mission 4: (6*5*4*3*(2+4))/(10*9*8*7*6) ~ 7.1%
chance of passing mission 5: (6*5*4*3*2)/(10*9*8*7*6) ~ 2.4%

probability of winning > prob of winning exactly three > 0.167 * 0.071 * 0.071 (* 3 ways) + 0.167 * 0.071 * 0.024 ( * 3 ways) ~ 0.00253 + 0.00085 = 0.00338

The other ways of winning will contribute even less. So a random strategy is awful, with less than a 1% chance.

Let's try making it smarter:

If a mission succeeds, keep those characters for the next mission, else start from scratch again. Since the missions progress (or are equal) in difficulty, evil would be helping if they don't sabotage a mission just to ensure they can sabotage the next. So worse case scenario, evil sabotages every mission they can.

Ways to win:
win first two (third for free), same as prob of choosing 4 good at once ~ 0.0714
win first, lose second, win 3rd or fourth ~ 0.167*(1-0.0714)0.0714 + 0.167(1-0.0714)*(1-0.0714)*0.0714 ~ 0.0111 + 0.0103 = 0.0214
Others contribute less.

So this strategy gives roughly 10% chance of winning.

For #2, a cheap answer is for the leader to just guess who the unknown evil character is, and then use the strategy from #1. If he's wrong, he'll be revealing himself to an evil character and will get assassinated. He has a 1/6 chance of guessing correctly. Thus good can win at least with a chance (1/6)*(5/6) = 5/36 ~ 14% chance of winning.

Maybe there is some tradeoff solution, where less certainty of who is good/evil is traded for not fully revealing the leader (maybe he only reveals himself to a couple possible good guys, which is better than 1/6 chance of success).

But currently I'm not sure how to do that.

Answer 2

So, I have played this game probably 50+ times with friends, though not always with 10 and not always with the leader variant in the proposed puzzle.

One difficulty I have with the proposed solutions involving the leader is the weakness you correctly identify: why would the evil characters not behave exactly like the leader? As soon as you imply a 'perfect strategy' for the game, the other (opposing side) characters can always imitate it for themselves! The evil characters have exactly the same knowledge as the leader and, until missions fail, will have no leverage against the honest leader. The evil characters have no reason not to employ the same strategy as the honest one.

I do not think, and I could be wrong, that there is a closed form solution to the problem, even if our players were programmable bots that worked through logic only.

The fun of the actual game this puzzle is based from, of course, is that there are no perfect strategies -- people are always flawed in their analysis or there is a loud player who is capable of making convincing arguments during the discussions. That, and all discussions happen openly at the table and not in private (though we have had instances of signaling during games... which of course can always backfire!).

Answer 3

Since the rule was clarified and a more fitting answer proposed, this answer should be on hold (though I don't know how to do that), as I haven't thought of any better solutions to the current problem. Admittedly, I couldn't think of a formal way for bad guys to beat that strategy within its framework. But it feels rather complex, and that's not a good sign when the puzzle hinges on trust and human communication.

Should everyone assume everyone else to be purely rational? Can some good guy decide that he wants to deceive the baddies into thinking he was the leader, thus improving the rate from 5/6 to 1?

(Original answer)

Sorry for not solving it completely, but I think it helps. There can be no certainty, rather a probability of the good guys winning. Obviously there's an upper bound of 5/6, since whatever happens, they can kill a random good guy in case he's the leader.

But other than that, any decision is tricky, since there's an important aspect of the rules that I think is ambiguous. (I'll take that 5 votes is enough for a team, answering the most pressing question.) Namely, what does it mean exactly that the good guys "can use a strategy"? Do they know the same strategy and know that other good guys know it too? Do "they" include the leader? Do the bad guys know it? Or does the 5 or 6 good guys have to come up with a plan without preparations? Can the strategy involve unconstrained discourse or even general actions, or is it limited to some formal exchange? The possible strategies vary wildly between these cases.

As an optimistic example, if 6 good guys can have a strategy as common knowledge without the bad guys knowing it, then it is possible to use cryptography to establish each other's identity during discussion. Then, randomly choosing team members among themselves, they can ensure a 5/6 success rate.

On the other extreme, if the leader has to make up a plan without help, I think it's hard to see how the loyals are going to cooperate at all, since the bad guys can claim to be leaders and suggest multiple plans to confuse everyone. But if unconstrained actions are allowed on the part of the leader, and we take the rules literally, then the leader can commit suicide for a draw. Good cannot win since he's dead, but evil didn't kill him, hence draw.