Solution to Avalon board game

Question

Question: If players are able to discuss strategy before playing Avalon, does the game have an optimal solution?

The strategy can be as convoluted as you want. I just want to know if in principle this is a "solved" game.

The game rules are fairly simple and for reference the details of number of good vs evil players, and rounds can be read here: https://en.wikipedia.org/wiki/The_Resistance_(game)

If there are G good and E evil players, at the end of the game team evil can always just randomly guess Merlin to win. So an optimal solution will be defined as:

• for team good, a strategy in which (regardless of what team evil chooses to do) they can guarantee succeeding at least 3 missions and team evil can't do any better than 1/G chance of choosing Merlin
• for team evil, a strategy which (regardless of what team good chooses to do) maximizes their chance of winning the game, with a chance greater than the trivial solution of guessing with chance 1/G

As far as I know, the rules are not entirely clear on what communication the players may do (besides forbidding just directly showing their character cards), for the purposes of this question, consider the following rule on communication (if playing by email, it would be equivalent to every message must be sent to all):

• Cannot rely on 'under the table' note passing, texting, etc. All statements made by a player must be public, in the sense that the every player has the raw message (even if not all players have enough context to derive the same meaning - ie. an Evil person stating he is Merlin is never confusing to an evil character since the evil characters all know each other, but can be misleading to a good character. Only the raw message itself must be public, asymmetric knowledge of intentions gained from a message is fine.)

I have a suspicion that despite not being able to trust any particular character is telling the truth, there might be a solution in favor of the good characters which takes advantage of the inherent asymmetry caused by the character Merlin and there always being more good characters than evil.

Can anyone think of a solution?

Answer 1

Despite not being able to trust any particular character is telling the truth, in some circumstances there appears to be a solution in favor of the good characters which takes advantage of the inherent asymmetry caused by the character Merlin and there always being more good characters than evil.

Here is an attempted mathematical solution for team good.

This relies on Merlin knowing all the evil characters. So will not work if the character Mordred is included (an evil character Merlin does not know about). If other special characters are used, it should not affect anything. It is also a work in progress in that this strategy gives quite a bit of extra information to "team good", but there may still be some details that need working out. (For example, I've already had someone point out to me that one must be careful to pad out messages appropriately or just knowledge of the length is enough context to figure out who Merlin is with this strategy.)

---

After dealing character cards, a good person suggests:

1. the following strategy will allow good to win, so provably deviating from these rules will indicate you are evil
2. whoever is the first mission leader will be now referred to as player #0
3. players clockwise from #0 get numbered accordingly
4. each player (i) comes up with a secret phrase: phrase_i
5. from this, each player (i) generates a secret number for other player (j) as secret_ij = HASH( phrase_i + string(j) )
6. use these secret_ij numbers along with public key exchange to generate a crypto key between each player: Key_ij = Key_ji = result of public key exchange between player (i) and (j)

Now with that setup, the good player goes on to suggest the following:

7. Special round of discussion: all players openly/publicly give encrypted messages to the other players stating one of the following:

   7a) declaring themself as not-merlin

   7b) declaring themself as merlin, stating who all is good, and providing his phrase_i so all keys and therefore messages from him can then be read by that person

8. Merlin should declare "merlin" to all good guys, and "not-merlin" to all evil. Normal loyal servants should just declare "not-merlin" to everyone.

9. if a good player gets a message deviating from this rule, they can immediately release the related key used for that communication to out the evil person. So evil effectively must pretend to be normal good or merlin.

10. More generally, a good person should immediately expose any fake merlin (release his secret phrase) if they can prove they are fake without giving information about merlin.

    For example, if a fake merlin ever claims another person claiming to be merlin is good, this outs themselves as fake, as the real merlin would never do this. Unfortunately, a good person might need to keep this to themself, as revealing this could reveal information about Merlin. However if multiple merlins choose groups such that there is no consistent way for one to be real (for example two merlins claiming each other as good, or three merlins claim such that it makes a cycle), then the entire group is fake and should be exposed.

11. Now a round of plaintext discussion (no encryption). Each player states which groups of good guys were declared to them by people declaring to be merlin. (Note: only the groups are released, not who claimed the group.)

12. 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 > the number of evil, any group with the correct number of people will necessarily include at least one good. This means evil cannot usefully mislead here.

13. If there is a player who appears in all proposed sets of good players, he must be good. All good players should release all secret phrases they know to this player. Now even more restrictive than before, this player then can expose fake merlins whose group selections include each other in a revealing manner.

14. If there is enough information that every one should be able to deduce a guaranteed good team without revealing merlin, someone can just explain it. Good, having superiority in numbers, can now ensure the correct group is sent each time.

15. If there is not enough information for everyone to determine good/evil, the mission leader picks a team which will eliminate as many proposed "good groups" from consideration as possible. If Merlin was the mission leader, he could purposely pick a correct or incorrect group here, so no information about Merlin is lost here. If the mission wouldn't actually eliminate a possible "good group", and the person still insists on this mission team anyway or calls a vote before discussion, 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.

16. 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 the next one.

I may be missing something, but I do not believe team evil gains any information about merlin from this strategy. I also am not sure how to prove it, but it appears to me there is enough information to always have good win.

First note that if every time a mission fails, at least one possible "good group" is eliminated, there have to be at least 3 fake merlins for team evil to have a chance. So the only potential issue is in the 7-10 player version.

Second, note that the intersection of all proposed good sets must actually be good.

Third, if the intersection between two proposed sets has only one person, that person must be good.

This along with previous information and other simple deductions is quite restrictive.

---

For a concrete example, consider the seven person game: 3 evil, 4 good.

All three evil characters need to successfully claim to be merlin to have a chance. So if we can eliminate one by deduction, good wins.

If no fake merlins include an additional evil member in the proposed group, then there are E+1 people that have only been included in one group. The complement of this must be good.

If all fake merlins include an additional evil member in the proposed group, then there will be a cycle of fake merlins claiming other fake merlins are good, and thus out each other.

So at least one fake merlin must include G-1 good members in the proposed group. Thus if there is a proposed group that doesn't have an intersection of size G-1 with at least one other group, it can be discarded. (Taking the number of groups down to 2, thus allowing the good to win.)

For a seven player game, there are three missions requiring <= G-1 people. So if no proposed group can be eliminated only with deduction, then always choose for the mission the intersection of at least two groups. If evil fails the mission, they eliminate more than one group, and thus good again wins.

Answer 2

It seems all evil has to do is: all the evil players conspire who they think Merlin is (it can be a random guess), and they each pretend to be Merlin and out the other spies and declare the real Merlin as also a spy.

If they are right in their random Merlin guess, the other players gain no new information, and Merlin appears indistinguishable from other players. Play continues as normal, with the spies knowing they were right about their Merlin guess, so the assassin will win the game for them.

If, as is more likely, they are wrong, the spies are easily outed, the missions are brief and obvious, and the assassin has already eliminated one possible target for Merlin, and has a slightly better chance in picking.

Point is, still far from a guaranteed "good" win.