The sideways view

I’ve been playing some Avalon recently, and became curious about winning probabilities under perfect play.  (Avalon is the most common variant of The Resistance, rules are here, this post probably won’t be interesting if you haven’t played.)

In this post I consider the version of the game where players are able to send secret messages to one another (“whisper”). Most groups I’ve played with use rules such that whispering possible if players are sufficiently determined and patient. Some groups make whispering overtly legal and a smaller number have strict norms against things like winking.

With whispering and Merlin, I show that the good team can always pass 3 quests without leaking any information about Merlin. Without Merlin, I show that whispering doesn’t matter and compute all the victory probabilities. I don’t consider Mordred or the lady of the lake (other roles don’t affect the analysis).

For groups that make whispering possible but difficult, this implies that the whole game hinges on the question “can you successfully whisper?” For players who don’t enjoy this aspect of the game, it may be worth either allowing whispering explicitly (and making the game more difficult for good players by adding other roles) or disallowing whispering altogether (and making the game easier for good players).

For players who do enjoy this aspect of the game, they could also consider the following simpler game between Alice, Bob, and Eve: Alice has a secret, she wants Bob to learn it without leaking it to Eve. It’s a classic. You can play this game under whatever informal rules about whispering you normally play Avalon, and if Alice and Bob can reliably win at this game then they can reliably win at Avalon using modestly more time.

The version of Avalon with no private communication of any kind is more complex. I originally expected that if Merlin used any private information and evil players reasoned optimally, then Merlin would reveal too much about their identity. But that turns out to be false—Evan Chen found a simple strategy for 5 players where the good players win 23.7% of the time (while they only win 20% of the time if Merlin doesn’t use their private information).

What does “solving” mean?

A “strategy” for the good team specifies what each player would do if they are good. A strategy for the evil team specifies what each player would do if they are evil.

We say the good players win with probability p if:

• There is a strategy for the good players that wins with probability at least p for all evil strategies.
• There is a strategy for the evil players that wins with probability at least (1-p) for all good strategies.

Each player knows what they would have done if they had been assigned a different role (since they can just imagine receiving that role). So we allow a player’s strategy as an evil player to depend on what they would have done if they had been good—that is, we allow the evil players’ strategy to use an oracle for the good players’ strategies. This allows the evil players to do things like “Do exactly what you would have done if you were good, until event X occurs,” which is important—it prevents the good players from e.g. using a secret passphrase known only to good players.

Similarly, we allow the good players to use an oracle for the evil players’ strategies. To prove that games have a unique value, we use a fixed point argument. (Though we can still define “the good players win with probability > p” without using fixed points, just based on the existence of an oracle strategy for good players that wins for all concrete strategies of the evil players.)

I. Solving The Resistance (no Merlin)

Without Merlin, the game is relatively straightforward. Understanding this setting is important because it will allow us to significantly simplify the full game.

Victory probabilities are:

• 5 players: 30%
• 6 players: 33%
• 7 players: 26%
• 8 players: 16%
• 9 players: 29%
• 10 players: 17%

Simplifying the structure of the game

The simplified game: Consider the 3 largest quests. (Ignoring * quests that require two failures—these are strictly easier than a smaller quest, and so effectively are never amongst the 3 hardest quests to pass.) We will define a simplified meta-game where a single good meta-player chooses a group for each of the 3 largest quests, without having any information at all. They win if one of their 3 choices contains no evil players.

Let p be the probability that the meta-player wins the simplified game. We now prove two claims: that the good players can guarantee a win with probability p, and that the evil players can guarantee a win with probability 1-p. Note that the meta-player might as well be deterministic, since we can just choose whatever random seed has the highest winning probability.

Strategy for good players: Every good player simulates the meta-player internally to guess 3 groups. We initially mark each guess as “live.” In each round, we choose the smallest “live” group that and send it on the quest—i.e., all good players propose that group, and approve a proposal iff it is that group. If a quest fails, we mark the corresponding guess as “dead.”

Our first claim is that until we’ve failed three times, there is always a live group that is large enough to go on the next quest. This is true because we always choose the smallest “live” group and our 3 guesses correspond to the 3 largest groups.

Our second claim is that the good players always successfully select a group. This is true because the number of proposals allowed before automatic failure is always larger than the number of evil players, and any good player will make the unique proposal that would be accepted by the good majority.

The final claim is that if one of our 3 guesses consists of only good players, we won’t fail 3 missions. This is true because each failure marks a “live” guess as “dead,” and the group of good players will never be marked as “dead.”

So the good players end up winning with at least the probability that the meta-player successfully guesses a good set, regardless of what the evil players do.

Strategy for evil players: The evil players behave exactly as if they were good players, unless one of them is selected to go on one of the 3 hardest quests. At that point, if a quest contains an evil player exactly one of them fails the quest (for example, they can decide to have the first evil player clockwise from the initial king fail).

If the good players are able to win with probability p against this strategy for the evil players, we can construct a meta-player for the simplified game that also wins with probability at least p. The meta-player simply runs a simulation of 5 honest players, assumes that all hard quests fail and all easy quests pass, and outputs the teams selected for the 3 hardest missions. If the meta-player loses, then the honest players will also lose in the original game against the strategy we’ve described for the evil players.

So the good players win with at most whatever probability the meta-player can win, regardless of what they do.

Winning probabilities in the simplified game

The simplified game is very simple. The strategy for the meta-player is simply to pick three guesses such that at most one of them can possibly succeed.

To compute the probabilities, we verify that it’s possible to find 3 incompatible guesses, for each guess we can count the number of “possible worlds” (subsets of players who are evil) for which that guess is correct, add up these three numbers. That gives us the number of possible worlds in which the good team wins. We divide this by the total number of possible worlds to get the win probability.

If picking a team of size X when there are Y good players and Z total players, the number of worlds in which it wins is simply (Z-X) choose (Y-X), i.e. all the ways to pick the remaining good players.

• 5 players. Quests are 3/3/3, out of 5 good players. They win with probability (1+1+1)/10 = 30%.
• 6 players: Quests are 3/4/4, out of 4 honest players. They win with probability (3+1+1)/15 = 33%. (At most one of {ABCD, CDEF, AEF} can be all good.)
• 7 players: Quests are 3/3/4, out of 4 honest players. They win with probability (4+4+1)/35 = 26%. (At most one of {ABC, DEF, ABDE} can be all good.)
• 8 players: Quests are 4/4/5, out of 5 honest players. They win with probability (4+4+1)/56 = 16%. (At most one of {ABCD, EFGH, ABCGH} can be all good.)
• 9 players: Quests are 4/4/5 out of 6 honest players. They win with probability (10+10+4)/84 = 29%. (At most one of {ABCDE, FGHI, ABHI} can be all good.)
• 10 players: Quests are 4/4/5 out of 6 honest players. They win with probability (15+15+5)/210 = 17%. (At most one {ABCDE, DEFG, GHIJ} can be all good.)

II. On “whispering”

We can modify Avalon by allowing “whispering,” private communication from one player to another. (It’s not important whether other players can observe that a pair is whispering—we will show that with whispering the good players can always win, even if the evil players are able to observe when whispering occurs but the good players are not.)

In this section, I’ll argue that whispering is likely to be possible, unless we adopt rules specifically designed to prevent it.

For N>6 players our strategies only require Merlin to whisper to the other good players who is good, and then for the good players to whisper to each other who claimed to be Merlin. To perfectly preserve anonymity, this requires each player to whisper (or pretend to whisper) N bits to each other player—only the whispers between Merlin and good players matter, but everyone else needs to whisper to provide cover.

For N=5 players we use a strategy that involves more whispering (order N² log(N) bits between every pair of players). This strategy is combinatorially simpler (and I could have used a similar idea to give simple strategies for N>6 players), but it would be hard to implement in normal Avalon without looking like you are breaking the spirit of the game. There is a single case with N=7 players that requires additional whispering.

Step 1: Exploiting limitations

The first step is to use players’ limitations to send a message that some but not all players can detect:

• Limited perception. I can’t see everything that everyone is doing simultaneously. If someone winks, gestures with one hand, taps their foot, or shrugs a shoulder, I will sometimes not notice. Even if I’m looking at one person intently I probably can’t  notice every possible signal they could send, and it’s even more hopeless to monitor multiple people simultaneously.
• Limited information. Any given pair of people are likely to have some knowledge in common that at least some other players lack. For example, if I choose a random trivia fact of an appropriate level of difficulty, I might assume each good player has at least a 10% chance of knowing that fact while each evil player has at most an 20% chance of knowing the fact. Or I may have common context with particular other players (from shared experiences or past games).
• Limited computation.
  • Merkle’s puzzles. Suppose I have a type of puzzle that’s easier to construct than to solve (like an anagram). I can construct a large number of puzzles and broadcast them. Someone who wants to communicate with me can choose one puzzle and solve it, and then broadcast an opaque hint about which one they solved (that’s only obvious to someone who already knows the solution). Then we have a shared secret, namely the solution to that puzzle. An eavesdropper needs to solve a large fraction of the puzzles to have a good chance of recovering that secret. For example, if I can make anagrams in 2 seconds and they take 3 minutes to solve, then I can broadcast 90 anagrams, you can pick one to solve (and give an opaque hint like “it’s a noun, changing the second letter makes it a verb”). Each of us spent 3 minutes and we end up with a shared secret, but it would take more than 2 hours on average for someone to recover our secret.
  • Public key cryptography. If no holds are barred, I can publicly announce the product two large primes and go crazy. I think the other forms of whispering have realistic analogs in normal conversation, but this one doesn’t.
• Limited memory.
  • Memory puzzles. We can all agree on 10 different functions of a list of numbers—sum of x, sum of x^2, sum of x where you reverse the digits, the sum of concatenations of pairs of consecutive numbers, etc. Then one player can quickly read a list of 30 numbers. Everyone else can pick a single function and keep track of the value of that function. After the stream of numbers is done, everyone reveals which function they were keeping track of. If two people were keeping track of the same function, then they have a shared secret. The eavesdroppers can only recover it if they are able to remember all of the numbers, or compute all of the functions online, or get lucky and pick the same function. If there are 4 good players and 2 evil players, good players can compute one number and evil players can compute 2, then doing this process once gets you one shared secret between good players and the eavesdroppers only have a 40% chance of knowing it.
  • Long-term memories. If a player remembers lots of information that other players don’t know, and its hard for other players to quickly commit new information to memory, then we can improve on the previous scheme. One player can choose a string they remember (e.g. digits of pi, a poem, the periodic table of the elements…) and can recite that string. Another player can choose a function, e.g. “the total number of letters in words that start with e,” and compute that function as the first player recites. Then the receiver can reveal the function, and the sender can compute the value of that function by repeating the string in their head.
• Physical props. If we allow non-trivial physical props then signaling usually becomes easy. As an example, suppose that players are allowed to cast anonymous ballots, each writing down the name of a player, putting those names in the center of the table, then shuffling them and revealing how many votes each player received (but not who voted for them). This can be used to generate shared secrets: (i) each player votes randomly, (ii) one player who submitted a unique vote A chooses another unique vote B, and announces “I voted for either A or B,” (iii) the player who voted for B also says “I voted for either A or B.” Then those two players know who voted for whom, but no one else knows anything. (It’s a bit complicated to analyze what happens if an evil player lies to try to mess up the process, but it turns out to be fine.)

Some of these measures sound pretty weird, but I think they mostly have innocuous-looking versions, many of which occur routinely in games:

• Limited perception is frequently used (often e.g. between two evil players subtly indicating which one should fail a mission—in my experience this usually works and is considered fair game).
• Limited information or computation may take the form of subtle logical errors or cues, that come up during the normal verbal reasoning process, that won’t be notable to most players but will be obvious to someone with appropriate context or happens to notice the weirdness.
• Limited memory can be applied similarly, but now by leaving hints that require piecing together information across time, e.g a slight inconsistencies or a systematic bias in an apparently random process.

Step 2: amplifying privacy

Now suppose that player A wants to send a private message to player B without being eavesdropped on. Here’s what they do:

• Use one of the channels above to send a message that player B may or may not receive.
• Repeat the process multiple times. This ensures that in expectation B will receive several messages, and that with high probability the eavesdroppers miss at least one of those.
• B acknowledges to A which messages she successfully received. It’s OK if eavesdroppers overhear this.
• A and B combine the contents of those messages to obtain a shared secret. (As a degenerate example they can do this by sending one bit per message and XORing the bits from the successful messages.) This gives a shared bit which is completely hidden from a player who didn’t observe every message.

Performing this procedure explicitly would look very weird in a game of Avalon. But, again we can do crude approximate versions that achieve reasonable confidence and don’t look weird. For example, I can ask questions like “do you know what I mean?” and try again if the intended recipient doesn’t seem to get it; or I can send cues that only make sense given the common context that two players have established over the course of a game.

Complementary mechanisms

Whispering is possible if any of the mechanisms for private communication work.

On top of that, there are some complementary mechanisms to make it easier:

• Good players can conspicuously limit their own abilities, for example by looking in useless directions, closing their eyes, having distracting side conversations, engaging in cognitively demanding tasks, etc. A player can do this some but not all of the time, so that a player is alert sometimes to receive messages. A player who is alert too much of the time looks clearly evil.
• Rather than simply having A transmit messages to B, we can also have B transmit messages back to A; we can combine the two streams to get a more secure secret (which can be used for either transmission from A–>B or from B–>A). This is useful if e.g. evil players could choose one person to pay close attention to—now in order to eavesdrop on the A<–>B link they need to constantly monitor both A and B.
  • In principle this can be generalized to more than 2 players, though it becomes much more complex. I believe that the good players can win perfectly even if the evil players can eavesdrop sometimes, as long as they can’t simultaneously intercept messages from every good player.

Is whispering practical / should it be allowed?

Different groups have different rules concerning whispering. Most don’t allow overt whispering (though some do). I’ve never played with a group that had strong norms against things like winking or exploiting bounded memory, and in practice it usually seems to be possible for determined players to whisper. This becomes more true for longer games—in a 10 minute game it might not be possible for good players to whisper enough, but in a 60 minute game they have plenty of opportunities.

My preference is to either allow overt whispering—e.g. by allowing players to meet in separated rooms—or else to have bridge-style norms against private communication. In games with informal whispering norms, whether Merlin is able to successfully signal seems to be overwhelmingly important question, and I enjoy that problem less than other aspects of the game.

Strictly enforcing rules against whispering would be difficult, but it seems fine to have informal rules against anything-kind-of-like-whispering rather than literally using screens and preregistered conventions. (There are definitely tricky border cases.)

With whispering and 6+ players the good team just wins outright (for 5 players it seems reasonably balanced). So with whispering the evil team should probably be given an advantage. Without whispering the good team needs a large advantage. Random proposals that seem likely to be balanced are {Mordred, Percival, Morgana} with whispering and {Percival, Oberon} without whispering.

III. 6+ players

The basic strategy

We will show that for 6+ players, the good players can win flawlessly, i.e. they can reliably pass 3 missions without leaking any information about the identity of Merlin. They will then lose with probability exactly 1/(# of good players), since the evil players will sometimes guess correctly by chance.

I will use “we” to refer to the good players.

All of our strategies have the same basic outline:

• We play the simplified game, in which we (sequentially) nominate teams for each of the three hardest quests.
• Each player whispers to each other player. If they are Merlin and the other player is good, they whisper the set of good players. We call these sets “claims.” (If they don’t make a claim, they just whisper some filler of the same length.)
• If only Merlin makes claims, then the good players will win flawlessly. The difficulty is that evil players may also make claims. We call any player who makes at least one claim a “claimant.”
• Each player reports the set of claims they receive (but not the claimants).
• Each player then whispers to all other players who are in a claim with them and tells them the person who sent them the claim. If they hear conflicting evidence, they discard the claim.
• We publicly report the list of claims that survive the last step, and use it to decide which guesses to make in the simplified game described above.
• If a player reports more than (#evil + 1) claims, then we know that this player is evil. Similarly, if a claim is not reported by all the players it contains then we know that it’s wrong, and in particular each valid claim is reported at least (#good) times. Call a claim valid if it hasn’t yet been excluded.

Call a claim “live” if it can’t yet be excluded by the meta-player. Initially the live claims are the same as the valid claims, but over time the set of live claims will shrink as we make guesses.

We use some basic definitions and observations repeatedly:

• The number of valid claims is < (#evil + 1) * (#players) / (#good). We’ll use the pigeonhole principle frequently: if there are enough players, then we can make statements like “There are at least X players each of whom belong to at least Y claims.”
• If there are at most 3 valid claims, then the good players can simply make three guesses, one for each of the three claims. So we can assume that there are more than 3.
• Say that two claims are adjacent if they have intersection of size (#good – 1). We will often consider the adjacency graph of claims, in which two claims are connected by an edge iff they are adjacent.
• When we need to guess a team of size (#good – 1), we can make a guess that will succeed if either of two adjacent claims is correct—we say that such a guess tests those claims. This is extremely important. For 9 or 10 players we sometimes need to guess a team of size (#good – 2), for which we can make a guess that tests a single claim and two of its neighbors (or two claims with intersection (#good – 2)).
• Say a player is informed if they know the identity of every claimant. Any player who receives the maximum (#evil + 1) claims is informed. But a player can also become informed by applying reasoning (though in that case it may not be common knowledge that they are informed).
• Information can be safely used to guess a fact about Merlin if and only if it is common knowledge.
• The true claim contains at most one claimant. So the set of claims consistent with the informed players’ knowledge form a clique in the adjacency graph (since all of them contain all non-claimants and hence have pairwise intersection (#good – 1)).
• In particular, the informed players know which connected component of the adjacency graph contains the true claim. Moreover, this fact is common knowledge and so can safely be used to make guesses about Merlin. (The good players can usually narrow the truth down to a much smaller list of possibilities, but which mistakes they make would reveal something about the identity of Merlin.)
• In general the set of players in a claim cannot leak the identity of the claimant to the players outside of the claim, because that would compromise Merlin. However, if a claim has already been falsified, then the claimant’s identity can be published. Players in the claim may disagree about who was the claimant. In that case, we can divide the players into two groups that make disjoint reports, and we know that at least one of the groups is all evil. We will often talk about getting a “5-1” or “4-2” or “3-3” split in the case of disagreeing reports—there may be more than two distinct reports, such that it’s really a 2-2-2 split (say), but that’s OK because we can always merge them to obtain two groups, at least one of which is all evil.
• If two claims with the same claimant intersect, then all of the players in the intersection must be evil (since a good player will report at most one claim per claimant, and both claims must be reported by all players in the intersection).
• We do a ton of casework. To aid in the casework, we aggressively exploit symmetry. If we’ve labeled the players A, B, C…, and an event involves (say) one of the players AB, but currently the players AB are symmetrical, then we can just choose the labels to assume that the event involves player A.

We will describe our strategies from the perspective of the meta-player from the simplified game, and that’s really what “we” refers to. The meta-player makes guesses one at a time, and players can communicate between those guesses.

This means that the order of the hardest 3 missions is potentially relevant. The only important fact for our purposes is that the last mission is always the hardest.

The details of our strategies are combinatorially complicated and are described in the appendix. The actual moves that the good players make are usually pretty simple. The combinatorial difficulty is showing that there is no possible defense for the evil players.

For illustration, we describe how we respond in the case where there are 7 players and 7 valid claims. This is the most interesting and challenging case, and honestly I’m pretty surprised it worked.

Special case: 7 players, 7 valid claims.

Setting: 3 evil, 4 good. Quest sizes are 3/3/4.

A valid claim appears at least 4 times, and each player reports at most 4 claims. So every player appears in exactly 4 claims, from 4 different claimants, and all players are informed.

If the adjacency graph isn’t connected, then all players know which component contains the truth, so we can throw out all of the other components and so reduce the number of valid claims (we cover cases with fewer claims in the appendix). So assume that the adjacency graph is connected.

If an evil player makes two different claims, then those claims can only intersect on evil players. Therefore the 7 claims consist of the real claim, and 3 sets of claims (corresponding to the 3 evil claimants) such that the pairwise intersections within each set are disjoint from the real claim. We can rule out any claim X for which such a partition is not possible. If any claim is ruled out in this way, then we can once again reduce to a smaller number of valid claims, handled in the appendix. Call this assumption (*).

• Suppose there is a claim W=ABCD which is adjacent to three other claims XYZ. Choose a partition of the claims other than W satisfying (*), and call two claims “opposite” if they are in the same part of the partition.  Note that none of XYZ can be opposite one another, since each contains three of ABCD and hence their intersection contains one of ABCD.  Therefore there is one of them in each part of the partition. Moreover, each of them can be opposite from at most one other claim, since e.g. ABCE can only be opposite DEFG (since ABC are good, E must be the claimant, and ABCE can only be opposite something that it intersects in only player E). Thus each of XYZ is opposite exactly one other claim (since there are 6 claims other than W, each of which must be in one part of the partition).
  • One of XYZ contains each of E, F, G, since each part of the partition corresponds to one claimant. If two of them contain the same subset of ABCD, we can label players such that Y=ABCE and Z=ABCF. Then Y and Z both must be opposite DEFG, contradiction.
  • So XYZ involve different subsets of ABCD, and we can label the players so that they are X=ABCE, Y=ABDF, Z=ACDG.  There is then only one choice for their opposites, and so the set of claims is {ABCD, ABCE, ABDF, ACDG, DEFG, CEFG, BEFG}. In step 1 we guess EFG. If this fails we rule out all of {DEFG, CEFG, BEFG}. Then we guess ABCD. If this fails, then one of B,C or D was the claimant (A can’t be the claimant since they are known to be good). In any case, this rules out two of the remaining claims and our third guess will be correct.
• So assume there is no vertex in the adjacency graph with degree 3. That implies the graph is either a cycle or path. If it’s a path, then we can just perform a binary search (guess the middle claim, then everyone knows which of the length 3 paths contains the true claim, guess the middle of that chain, then everyone knows which claim is true).
• So assume the adjacency graph is a cycle. Label the claims 0, 1, …, 6 around the cycle. For any claim N we could use our first two quests to test (N-1, N-2) and (N+1, N+2), leaving only {N, N+3, N-3} (mod 7). Everyone can tell whether N is true or one of {N+3, N-3} is true, since they are in different connected components. If it’s N, we win. Otherwise, label players such that {N-3, N+3} are {ABCD, BCDE}. All other claims have been ruled out and so their claimants are known to be evil. We also know that BCD are honest.
  • Suppose that AEFG is not one of the five other claims. Then every claim contains one of BCD, and so one of BCD can publicly report the claimant and be trusted. If either A or E was the claimant in any of these claims then we know that player is dishonest so we can distinguish between ABCD and BCDE and win.  So all of the claimants are either F or G. Of the five excluded claims there must be three claims made by one of those players; say F made three claims. No two claims from F can have intersection containing BCD, and if they have intersection containing A or E then we know that player is evil and so can win. Thus each of AEBCD appears in at most one of the three claims made by F, and FG appear in total at most six times in these three claims, so there can be at most 11 total appearances, less than the total size 12 of the three claims. So this can’t happen, and therefore we win.
  • Thus for every pair of adjacent claims that can be labeled {ABCD, BCDE}, AEFG must be one of the five other claims (otherwise we can use the argument above to win, choosing the first two quests so that we are left with ABCD and BCDE as the live claims). Note that AEFG must be at a distance of 3 from each of ABCD and BCDE in the adjacency graph. It turns out this uniquely constrains the set of claims. If we go in clockwise order, we can label the players such that claim 0=ABCD, 1=BCDE, 2=CDEF. We then know that claim 4=AEFG, 5=ABFG. Then claim 3 contains EF and claim 6 contains AB. So claim 6 can’t contain E or F and claim 3 can’t A or B. So claim 3 and 6 both contain G. C and D are so far symmetrical, so we can label players such that claim 3 contains C and claim 6 contains D.

So we win unless the 7 claims can be labeled: ABCD, BCDE, CDEF, CEFG, AEFG, ABFG, ABDG. Everyone can tell that we are in this case as soon as the claims are revealed. Now we describe a strategy for this case.

Say two claims are opposite if they have intersection of size exactly one. The opposite claims also form a cycle: ABCD, CEFG, ABDG, CDEF, ABFG, BCDE, AEFG. If an evil player makes two claims, we can see that they must be opposite. There is exactly one partition of the six claims other than the true one into opposite pairs. So for example, if ABCD is the correct claim, then {CEFG, ABDG} are claimed by G, {CDEF and ABFG} are claimed by F, {BCDE and AEFG} are claimed by E.

Suppose that ABCD is true (the other cases are exactly symmetrical). If Merlin is either B or D, then the good players know that immediately and have won, because they observe a pattern of claimants inconsistent with any other true claim. So consider the case where Merlin is A (the case where Merlin is C is exactly symmetrical).

All of BCD know that A is a claimant. That allows them to rule out all other claims including A. By process of elimination, that means that D knows that C is good, and B knows that both C and D are good. So B is comfortable telling everything they know to CD, and C is comfortable telling everything they know to D. By applying similar logic to the claim BCDE, where E is the claimant, we conclude that all of BCD trust each other and can share information freely. Of course A also trusts BCD. So it is up to BCD to choose which sets to pick.

Now for every claimant, and every person they claimed to be honest, we ask them to report the claimant of every other claim they heard.

All of AEFG are claimants in sets including BCD, and so each of AEFG is expected to send reports on everything they’ve seen to BCD. At least one of BCD observes every claimant other than AEFG, so if E lies about any claim other than AEFG then BCD will know that E is evil.

If the evil players are EFG, we say they respect the set BCD if they tell the truth to BCD about all claimants other than AEFG claim. Similarly, they respect the set ABD if they tell the truth to ABD about all claimants other than CEFG. We make a similar definition in case a different set is evil, for example we say that AFG respect BCD if AFG are evil and they tell the truth to BCD about all claimants other than AEFG.

I claim that the good players can win in the first quest by implementing the following strategy: if exactly one set of good players is respected, output that set, otherwise output a random set of good players. This leaks no information about Merlin, since the evil players know exactly whom they respected and so can predict what the good players will do.

To see that they can implement this strategy:

• If the evil players respect both ABD and BCD, then both B and D learn the truth about everything, they know who exactly is evil, and they can tell who is respected. Thus the good players can pick uniformly at random from the good sets.
• If A is Merlin, then the good players can’t tell between the case where EFG respect BCD and the case where AFG respect BCD. But they know that BCD were respected, and they know that at most one set of good players was respected (or else we’d be in the preceding case) so they can output BCD.
• If A is Merlin and the evil players don’t respect BCD, then the good players know everything. So they trust A, and can tell whether the evil players also respected ABD. If they did, the good players output an arbitrary good set, if they didn’t, the good players output BCD.

IV. Using more whispering

To win with 5 players, we will need to use a more complicated strategy that transmits more information. Based on experience with whispering I believe that the strategies for 6+ players can be implemented by patient players within an hour; in contrast, the strategy with 5 players is a little bit more speculative and might take a long time.

Step 1: preventing evil players from claiming twice

As in the previous strategies, we allow each player make a “claim” to each other player about who is good, and then the players all report the claims they heard. We will add an additional mechanism to ensure that any player makes at most one valid claim.

After a player makes a claim, we choose a sequence of (#good-1)² players pseudorandmly from that claim. Each chosen player generates a secret—say a secret word—and then whispered to the claimant. The key property is that if there are two sets each containing at least one good user, then with high probability there is an index i such that good players were chosen as player i in each of the two groups. This property is basically satisfied if we choose O(#good²) secrets at random (since each secret has a 1/#good probability of being generated by the good player, for each of the 2 groups). I think we do it deterministically with exactly (#good-1)² secrets using an appropriate combinatorial design, but it doesn’t really matter.

After this, each player publicly announces a sequence of secrets. If the player made a claim, then the ith string they state should be the secret chosen by the ith player in their claim. If they fail to achieve this property, then the ith player simply announces that the claim is invalid (everyone can trust them since they were in the claim). We discard all claims which are announced as invalid. If a player didn’t make a claim, then they just announce random secrets.

If an evil player makes two distinct claims X and Y, then each of those claims contains a good player, say A in X and B in Y. There is some round i for which A and B are chosen to generate secrets. With high probability they generate distinct secrets; the evil player can only publicly state one of those secrets, and the other claim will be thrown out.

At the same time, Merlin can simply follow the protocol, so their claim will never be thrown out in this way.

This should leave us with at most (#evil + 1) claims, one of which is true. If we have more claims than that, then the evil people got lucky, so we consider the process a failure and repeat. If the number of possible secrets is at least (#good)(#evil), then it’s easy to see that this process has at least a 1/2 chance of succeeding, so they only have to carry it out O(1) times in expectation.

Moreover, this strategy leaks no information about Merlin. From the perspective of evil players, every good player privately whispers a random secret to each claimant and publicly states a sequence of (#good-1)² random “secrets.” And the evil players know in advance which of the claims will be thrown out by this process. So all of their observations are the same regardless of Merlin’s identity.

Step 2: winning

The main point of this scheme was to win with 5 players. In this case, there can be at most (#evil + 1) = 3 valid claims, so we test them all and win.

We can also use the same idea to simplify the proofs for other players, allowing us to skip the whole appendix, at the expense of more whispering (and deviating further from the spirit of the game).

For 6 players we can have at most 3 claims, so we can test them all.

For 7-9 players we can have 4 claims, so we use the strategies for the 4 claim case described in the appendix.

For 10 players we can have 5 claims, so we use the strategies for the 4 and 5 claim cases described in the appendix.

I would not have written this epic appendix if I’d noticed the above strategy earlier, though at least it ended up being a fun combinatorial puzzle, like some kind of absurd sudoku. (Writing it up was a bit tedious though.)

Appendix: “simple” strategies for 6+ players

I’m sure there are tons of typos here. There are likely to be some errors, but at this point I don’t believe any of them are essential / unfixable. Not for the faint of heart.

6 players

Setting: 2 evil, 4 good. Quests are 4/3/4. At most 4 valid claims.

If there are < 3 valid claims we win. If there are four claims, then some pair must be adjacent (since non-adjacent claims have disjoint complements, and you can’t find four disjoint two-element subsets of a six element set). Use our second guess to test an adjacent pair of claims, and the remaining guesses to test the other two claims.

7 players

Setting: 3 evil, 4 good. Quests are 3/3/4. At most 7 valid claims.

This is the most complex case by far. We do casework on the number of valid claims (we’ll also have to do casework in larger games, but it will generally be easier).

Case I: 4 claims. If there is an adjacent pair we win, so assume no pairs are adjacent.

Say that a claim X is friendly if it has intersection at least size 2 with every other live claim. Say that a player is isolated if they appear in at most one claim.

When we guess a friendly claim X containing no isolated players, we are able to eliminate an additional claim for free: the claimant A appears in some other claim Y, and there is another player B in both X and Y. This player can publicly state that A is the claimant, after which everyone knows that either A or B is bad, and hence can rule out claim Y.

• Suppose there is no isolated player, and there is a friendly claim. In this case, we guess the friendly claim, eliminate a second claim for free, and then guess the other two claims.
• Now suppose there is an isolated player A. In this case, guess the claim containing A. The other 3 claims involve only 6 distinct players, so each pair has intersection exactly 2 and all live claims are friendly. And they cannot contain any isolated players (since if they did, the other two sets would be subsets of the remaining 5 players and hence be adjacent). So we can guess one of these claims, eliminate a second claim for free, and then guess the last claim.
• So we win unless there is neither any friendly claim nor any isolated player. Then every claim has intersection 1 with another claim. It’s easy to see that two claims Y and Z can’t both have intersection 1 with X, otherwise they would be adjacent. That implies that we have a pair XY of claims with intersection 1, and another pair ZW of claims with intersection 1. Label the players such that X=ABCD, Y=AEFG.
  • If the intersection of ZW is A, then one of Z and W must contain two of BCD and hence be adjacent to X. So the intersection of ZW isn’t A.
  • Label B the intersection of ZW, and label Z such that it contains A. Then Z contains A, B and two of EFG (it can’t contain C or D or it would be adjacent to X). Label players such that Z=ABEF. Then W=BDCG. So the claims are X=ABCD, Y=AEFG, Z=ABEF, W=BDCG. Our first two guesses will be Z and W. If these fail, we know that A is good. Then do casework on the claimant in Z. If A claims, then A is Merlin and knows the truth. If B claims, then A knows that they are evil and so X isn’t the correct claim. If E or F claims, then A knows that they are evil and so Y isn’t the correct claim. In any case A knows the correct claim, and so can state it.

Case II: 5 claims.

• If there are two disjoint pairs of adjacent claims, we win (by testing each pair, then testing the last vertex).
• If there are three claims all of which contain some three players ABC, we can test all 3 simultaneously and win.
• Otherwise if there are three pairwise adjacent claims, we can label them as X=ABCD, Y=ABCE, Z=ABDE. Our first two guesses rule out the other two claims, so that A is known to be good. If A is Merlin, they now know the truth. Otherwise, consider the claimant in X: if B is the claimant, then A can rule out Y and Z and guess the truth. If C is the claimant, then A can rule out Y, and either B or E must be the claimant in Y which allows A to rule out Z. If D is the claimant then A can rule out Z and either B or E must be the claimant in Z which allows A to rule out Y. In any case, A can guess the truth now.
• (Taken together these imply that there is a single claim X such that all pairs of adjacent claims involve X—otherwise there would either be a triangle or two disjoint edges.)
• If there is a player A in four claims, then our first guess tests the claim not containing A. Now A is good and informed. Of the remaining four claims, if there is no adjacent pair then A knows the truth and we win. If there is an adjacent pair, we guess it. Now there can be no further adjacent pair, so A knows the truth and we win.
• If the players can be labeled such that the claims are {AEFG, ABCG, ABDF, BCDE, CDEF}, we start by testing ABDF. Note that all of ABDF appear in at least two of the other sets, and each other set contains exactly 2. If we get a 2/2 split (or 2-1-1 or 1-1-1-1, which we can group arbitrarily) then there can be at most one claim consistent with each hypothesis. If we get a 3-1 split, then every other claim contains one of the 3, so the odd one out really is the claimant and hence evil, so we can rule out two claims and be left with only two more to test.
• Otherwise, there are 6 players in 3 claims each. If all pairs of adjacent claims involve X, there must be a player A who is in 3 claims but not in X (since X contains only 4 players), and hence is in no pair of adjacent claims.
  • If the two pairs not containing A are adjacent, label them X=BCDE and CDEF. Test both of them with our first guess. If it fails, have everyone from each set report the claimant. Don’t allow players to point to themselves, or to point to the same player in both cases (since they should only report one claim per claimant). Note that there is no pair of adjacent live claims.
    • If in either case we get something other than a 3-1 split, then we got either a 1-1-1-1 or 2-1-1 or 2-2 split. In any case we can label the players so that neither of BC agree with either DE, and hence one of those pairs is all evil; there is at most one hypothesis consistent with each claim and we can guess both.
    • If in both cases we get a 3-1 split, then in each case we either know all 3 are evil or that the 1 is evil.
      • If there is intersection at least two between the 3’s, then we either know that both of the people in the intersection are evil, or that both of the 1’s are evil. Each hypothesis can be consistent with at most one of the remaining claims, so we can test both.
      • Otherwise, we can label players so that the 1’s are E and C. So the hypotheses for evil players are BCD, DEF, and EC. At most one live claim is consistent with each hypothesis.
        • If AEFG and ABCG don’t both appear, then at most two of these three hypotheses are live and we can test both.
        • If AEFG and ABCG both appear, the only possibility for the last claim is ABDF. So all the claims are {AEFG, ABCG, ABDF, BCDE, CDEF}, but then the previous clause would have triggered.
  • If the two pairs not containing A aren’t adjacent, label them X=BCDE and Y=DEFG. Try to choose (X,Y,) such that there is no claim which intersects with X in exactly one position—so either there is no claim that intersects with X in exactly one position, or for every triple (A, X, Y) such that A isn’t in X or Y and all adjacent pairs involve X, there is another claim intersecting X in exactly one place. We know that Y can’t be adjacent to any claim involving A, since X is part of every adjacent pair. Test BCDE with our first guess and assume it fails. If there is a claim Z adjacent to X, also test it. Have everyone report the claimant.
    • As above, if we have anything other than a 3-1 split, then we get two hypotheses for two evil players. Each of these can be consistent with some set of claims, all of which must be adjacent to one another. There can’t be an adjacent triangle so neither set can have size 3. We can’t have two disjoint adjacent pairs, so at most one of these sets is an adjacent pair. Use the first guess to test one adjacent pair, and the second to test the other.
    • If we get a 3-1 split, then note that all of BCDEFG must co-occur with A at least once, or else the three claims involving A would all involve three of the other five remaining players and so some pair would intersect. So:
      • If the one is D or E, then label it is as D. We can rule out DEFG. Now:
        •  If D co-occurs with any other of BCE we can also rule out that one and win. But the only other way that D can occur is as ADFG, which is adjacent to DEFG, contradicting the claim that every adjacent pair involves X=BCDE.
        • So D never occurs in any of the claims with A, contradiction.
      • If the one is B or C, label it B. We can rule out all claims involving B other than ABFG.
        • If B occurs exactly twice, then:
          • If it occurs in ABFG, then:
            • F and G must both occur a third time (since everything other than B occurs three times), with A, but can’t appear together. C occurs in both of these, and D includes one and E includes one. So the set is {BCDE, DEFG, ABFG, ACEF, ACDG}.
            • In this case we were free to pick X=BCDE or X=DEFG, since neither is adjacent to anything. Only BCDE has an intersection of size exactly one with another set, so we would have avoided this case.
          • Otherwise, one of F and G (say F) doesn’t occur with B. Then it must occur in both other claims involving A. The other two members of each of those claims must be disjoint or they’d be adjacent, so form a partition of CDEG. But one of those parts includes two of DEG, so together with F must be adjacent to DEFG, contradiction.
        • If B occurs three or more times, then:
          • If two or more of them are not ABFG, then we can eliminate both and then guess the two remaining claims. So B occurs twice with A, once in ABFG.
          • The non-ABFG claim involving AB can contain neither F or G (or else they’d be adjacent). But then it contains two of CDE. We can label such that it contains D and one of C or E. Then D can’t appear again; the last claim can’t contain both F and G, so we can label so that it contains F, meaning it is AFCE.
            • If the ABD claim is ABCD, then the set of claims is {FDEG, FABG, FACE, ABCD, BCDE}, which is isomorphic to {AEFG, ABCG, ABDF, BCDE, CDEF}, so a preceding clause would have triggered.
            • If the ABD claims is ABDE, then we could just as well have chosen X=ABDE, Y=BCDE with the player F being the player in neither of them, thereby avoiding the situation where there is another claim that intersects with X in exactly one place.

Case III: 6 claims. There are at least 3 players in 4 claims. These players are informed (but might be evil). Call them ABC.

• Suppose there is a set of players ABC that appear jointly in 3 claims.
  • If any other pair of claims are adjacent, make ABC our first guess, then test the other pair of claims, then win. If not, then ABC must be informed players—otherwise assume that A isn’t informed and D is. Then the other three claims all contain D, and none contain A, meaning each of them contains 3 of BCEFG, and hence two of them must be adjacent.
  • If any of A, B, C appears in two of the three other claims, assume it’s A; our first guess is ABC, then test the claim not containing A, then we know A is honest+informed so we can ask them which of the two remaining claims is true (those claims aren’t adjacent).
  • If two of ABC appear in any of the other 3 claims (say AB), then neither of them can appear in the fifth or sixth claim. So the other two claims are subsets of CDEFG, and hence are adjacent. Thus each of the other 3 claims can include at most one of ABC. Each of ABC must appear in at least one, so each appears in exactly one.
  • So no other claim can be adjacent to any of the three involving ABC. So if any of ABC is good, they can say whether the ABC component contains the truth. If they all agree that it contains the truth, then we can test it and if it fails we know that DEFG are good. Otherwise, we know that ABC doesn’t contain the truth, and we can guess the other 3 claims and win.
• So henceforth assume there is no set of players that appear jointly in 3 claims. Suppose there are exactly 3 informed players, call them ABC.
  • Suppose X=DEFG is a claim and it is adjacent to nothing else. Then all other claims contain at least two of ABC (or else it would be adjacent to X), and DEFG are each in at most two of the remaining claims (or else they would be informed). That means that ABC must appear in exactly two claims, say ABCD and ABCE, and the other three claims contain {AB, BC, and AC} (since DEFG in total can appear 8 times amongst these 5 claims, they must be split 2-2-2-1-1). At any time we can ask the informed players which component contains the truth. If 2 agree, then we know that they are either correct or they are both evil and hence DEFG are good. If all 3 disagree then we know that DEFG is correct (since no two of them could both be good) and we win. If all 3 agree, then we have a single guess, such that either that guess is right or DEFG are all good. In any case, we can operate under the assumption that we know which component contains the truth, as long as we guess DEFG in the final quest.
    • Suppose that the 5 claims other than X aren’t connected, or can be cut by removing one edge. Then we can test all of them in two quests, and then in the final quest can test DEFG.
    • If the claims other than X form a 5-cycle, we can label players such that the cycle is ABCD, ABCE, ABE?, BCE?, and ACE?. But then E is in five claims, a contradiction.
    • The only other possibility is a 4-cycle XYZW and another claim V connected to X and Z. If XZ is an edge, then we can still disconnect this by testing the edge XZ. If YW is an edge, then VXYWZ is a 5-cycle. So there are no edges other than XY, YZ, ZW, WX, VX, VZ.
      • If the ABC-ABC edge is in the 4-cycle, then we can label the first vertices around the 4-cycle ABCD, ABCE, ABEF, but then no claim involving BC or AC can be adjacent to both ABCD and ABEF, a contradiction.
      • So the ABC-ABC edge must be incident to V, say it’s VX. Label the players such that V=ABCD, X=ABCE, Y=ABEF, but then no claim involving BC or AC can be adjacent to Y but not X, a contradiction.
  • Suppose X=DEFG is a claim and is adjacent to another claim Y=AEFG. Then BC are both in all remaining claims (since they appear 4 times) and A must be in three of the remaining claims, so there are three claims with ABC, contradicting the earlier hypothesis.
• Suppose there are exactly 4 informed players ABCD. At any time we can ask the group which connected component of the adjacency graph contains the truth. If there is consensus, then that is correct.
  • Suppose that initially the adjacency graph is disconnected. Then we can consult the informed players to decide which component to investigate.
    • If there is consensus, we have now reduced to fewer than 6 claims and can use the previous case from the analysis (of 5 valid claims).
    • If there is a split, then there is a particular pair of players A and B who disagree. But A and B both appear in 4 claims, so they appear jointly in at least one claim. We can throw that claim out and reduce to the case of 5 valid claims.
  • So the adjacency graph is connected. Call two vertices “related” if they intersect on one of ABCD, but aren’t adjacent. If the first two quests leave a pair of related vertices, then we win: the intersecting vertex from ABCD knows which of them is true and we can defer to them.
    • Suppose there is a claim containing a single element of ABCD, call it AEFG. There are only 5 more claims, and must be 16 total occurrences of ABCD, so ABCD must appear as a claim and three of ABC must appear in all other claims. But then no other claim can be adjacent to AEFG, a contradiction.
    • Thus any pair of non-adjacent and non-related claims must consist of two claims each of which contains exactly two of ABCD. Suppose that there is a non-adjacent + non-related claim.
      • Suppose that ABCD is not a claim. Then there can be at most two claims with only two of ABCD, and that can be the unique non-related + non-adjacent pair. Label them ABEF and CDFG (preserving the A-B symmetry, the C-D symmetry, and the ABE-CDG symmetry).
        • Suppose F appears in a third claim. By swapping ABE and CDG, and potentially A and B or C and D, we can assume label such that ABCF is a claim. Now F can’t appear again (or F would be informed). CDFG must be adjacent to a claim not including F, which is therefore CDG(A/B), we can label it as ACDG. The remaining two claims both containing D and B (since they are informed), and A and C must appear one more time, so the remaining claims are BCD? and ABD?. The ?’s must either be EE, EG, or GE (there can’t be two G’s, or G would be informed). But these two claims must serve to connect the ABEF/ABCF component and the CDFG/CDGA component. It’s easy to check that none of the three possibilities do that, a contradiction.
        • So F can’t appear in a third claim. ABEF must be adjacent to a claim not including F, call it ABCE (breaking the C-D symmetry). CDFG must be adjacent to a claim not including F, call it ACDG (breaking the A-B symmetry). Then BD appear in both remaining claims, and E appears in one and G appears in the other, i.e. the others are BDE? and BDG?, where the ?’s are AB or BA. But BDE can’t be adjacent to CDFG or ACDG, and BDG can’t be adjacent to ABEF or ABCE. And BDE? and BDG? can’t be adjacent, so we can’t make the graph connected, a contradiction.
      • So ABCD is a claim.
        • Suppose F appears in a third claim with three of ABCD, we can make it ABCF by breaking symmetry. Then CDFG is adjacent to something not in F, call it ACDG. Then the last claim must contain BD and not AC, i.e. it must be BDEG. But BDEG isn’t adjacent to anything.
        • Suppose F appears in a third claim with either AB or CD (and not the others). Assume AB by symmetry, and then it must be ABFG (since ABEF has already been counted). CDFG is adjacent to something not containing F, which we can label ACDG by symmetry. The last claim is BCDE (it can’t AFG or else FG would be informed or A would be in five things). But then ABCD/BCDE aren’t connected to other claims.
        • Suppose F appears in a third claim with one of AB and one of CD, label it ACEF (breaking the AB symmetry, the CD symmetry, and the ABE/CDG symmetry). B must be in both remaining claims and F in neither. Thus CDFG must be adjacent to BCDG. The last claim is ABD(G/E), it must be ABDE in order to connect to the ABEF/ACEF connected component. Now we can win by testing ABEF/ABDE on the first quest and ABCD/BCDG on the second quest, leaving CDFG and ACEF and asking C (who is informed and known to be good) which of these two claims is correct.
        • Suppose F doesn’t appear a third time. Then ABEF is adjacent to a claim not containing F, which we can label ABCE. CDFG is adjacent to a claim not involving F which we can label ACDG. Then by counting the final claim must be BDEG, but BDEG isn’t adjacent to any other claim.
    • Thus all non-adjacent claims are related. That means we can look only at the adjacency graph, and try to eliminate two edges (and both incident vertices) such that the remaining pair of edges are non-adjacent. We then win, because that pair of edges must be related.
      • We show in the 8 player case III below that this is always possible unless the adjacency graph is either K(6)—where every pair of claims are adjacent—K(3, 3)—where the claims can be divided into two parts, and two claims are adjacent iff they are in different parts.
      • Suppose the graph is K(6). Consider an arbitrary claim X containing four players. Then every other claim is adjacent to it, so contains three of those four players. So those four players altogether appear in 4 + 3 * 5 = 19 claims, i.e. one of them appears in 5 claims, a contradiction.
      • Suppose the graph is K(3, 3). Consider a claim X involving players 1234 (we’ve already used the labels ABCD…), in part I of the partition. Then each claim in part II involves three of 1234. Hence one player, call them 1, appears in every claim in part II. Now player 1 has appeared in 4 claims already, so can’t appear in either of the other claims in part I. Thus a claim Y in part I needs to contain the three of the non-1 players from every claim in part II. That implies that all claims in part II contain player 1 and three of the four players from Y. But that means that all of those pairs intersect, contradicting the fact that the graph is K(3, 3).
• Suppose there are at least five informed players, ABCDE. As in the last case, we know that the graph must be connected or we can eliminate some claims. Define two vertices to be related if they intersect in one of ABCDE but aren’t adjacent.
  • If there are two claims involving two of ABCE, then all other claims must involve four elements of ABCDE (since the total number of occurrences of ABCDE is 20), and so the adjacent graph cannot be connected. So there is at most one claim with only two elements of ABCDE.
  • If every pair of non-adjacent claims is related, then we can win as in the last section, by finding two edges whose removal disconnects the graph and then winning.
  • Suppose there is a non-adjacent and non-related pair of claims. One has two elements from ABCDE and the other has three elements. We can label them ABCF and DEFG. At most one other claim X involves only three elements of ABCDE. DEFG must be adjacent to X, which we can label either ADEF or ADEG. All other claims involve four of ABCDE. ABCF must be adjacent to another claim, which must involve ABC and which we can label ABCD.  X must be adjacent to another claim, which must include ADE and which we can label ABDE (breaking the B-C symmetry). But now C only appears in two claims, and so C cannot be informed, a contradiction.

Case IV: 7 claims. This is addressed in the body of the post.

8 players

Setting: 3 evil, 5 good. Quests are 4/4/5. At most 6 valid claims.

Case I: 4 claims. If there are two adjacent claims, we test them both in the first guess and then win. So assume there are no adjacent claims.

There is a player A in at least three claims. Pick the first claim X to be one that doesn’t contain A, label the players such that X=BCDEF. Assuming X fails, we know A is good. Ask the five players to report who was the claimant.

• Suppose there is a 4-1 split, say that BCDE say that F is the claimant. Then F really is the claimant since there are only 3 evil players. If F is also one of the other claimants, then we can rule out that claim and guess the other two. If F isn’t one of the other claimants, then A is informed and we win (since there are no adjacent pairs).
• Otherwise, we can partition BCDEF into two sets BC and DEF who pointed at different players (if 3 people agreed make them DEF, if 2 people agreed make them BC). Those give us two hypotheses about the evil players, each of which implies that all good players are within the complementary set of size 5 or 6. Because there are no adjacent pairs, at most one live claim is consistent with each hypotheses and we can guess both.

Case II: 5 claims. There is a player A in four claims, who is informed. For the first two rounds, if there are two adjacent claims involving A, guess one of those. If there are no pairs of adjacent claims involving A, then if A is good they knows exactly who is good and so can guess that. After at most two guesses we’ve either won or verified that A is evil, in which case we can just guess the remaining claim.

Case III: 6 claims.   There are at least six players in exactly 4 claims. All of these players know which connected component the true claim lies in. At most 3 are evil, so if they all state which component then either we get a plurality in favor of one component (in which case it really contains the true claim) or we get a 3-3 split.  If we get a 3-3 split, we know that both of the other 2 players are honest. These players each know of at least 3 claimants, and so can rule out one side of the 3-3 split because it contains two claimants. So all good players can identify the connected component containing the truth.

Our goal is now to remove 2 pairs of connected vertices from the graph such that the remaining two vertices aren’t adjacent—we will then use our first two guesses to eliminate these edges, and pick the correct claim with our final guess.

In fact we can do this unless the graph is a complete graph K(6) or a complete bipartite graph with two 3-vertex parts, K(3, 3).  To see this, consider the length of the longest cycle in the graph and suppose that we can’t leave two isolated vertices by removing two edges.

• If the graph has a 6-cycle, then we can choose two opposite edges from that cycle, leaving two opposite vertices from the cycle. Therefore all of these pairs of vertices need to be connected by an edge. This leaves 6 pairs of vertices that may or may not be connected. If one of those pairs are connected but not all are, then we can use the connected pair to separate the graph (choose a pair AB that are connected for which one of the disjoint pairs CD is not connected, then remove the edges AB and EF—all we have to check is that EF is always an edge). If either all are connected or none are, then we have either K(3, 3) or K(6).
• If the graph has a 5-cycle, then we can remove two of the edges to remove any 4 vertices from the cycle. Thus the sixth vertex must be connected to every vertex from the cycle. But then there is a 6-cycle.
• If the graph has a 4-cycle ABCD and other vertices EF, then one of the other vertices must be connected to the cycle, say that AE is an edge. We can remove ABCD, so EF must be an edge. We can remove AE and BC, so FD must be connected. Thus FDCBAEF is a 6-cycle.
• If the graph has a 3-cycle ABC, then there must be some vertex D connected to the cycle, say that AD is an edge. If D were connected to either B or C, then we’d have a 4-cycle. If no other vertex were connected to B or C, then we could separate the graph either by removing AD and BC (if EF isn’t an edge) or by removing AB and EF. So we must have another edge incident to the cycle, we can label vertices such that it’s EB. Now we can remove AD and EB, so we must have FC as an edge. But we must have EF as an edge, or removing AD and BC would disconnect the graph. So BCFE is a 4-cycle.
• If the graph has no cycles it is tree. If it’s a chain, then we can remove the 4 interior vertices. If there is a vertex of degree > 3, we can remove that vertex and its neighbor which has largest degree. At most one of the remaining neighbors can have degree > 1, so we remove that vertex and one of its neighbors and we are done.

The adjacency graph can’t be K(6), because that would imply that all pairs of claims are adjacent, which in turn implies that there is a pair of players A, B who appear in no claim. But both A and B are claimants, and must appear in their own claims.

The adjacency graph can’t be K(3, 3) either: we can label players so that X=ABCDE is one claim, and Y=ABCDF is an adjacent claim. There must be a claim Z adjacent to Y but not X, which we can label Z=ABCFG. Then there must be a claim W adjacent to X and Z but not Y, which must be ABCEG.  There must be a claim adjacent to Y and W, and thus must contain ABC, but not adjacent to Z or X, so must not contain any of DEFG. That is a contradiction.

So we can always remove two edges to separate the remaining two vertices, and then win with our final guess.

9 players

Setting: 3 evil, 6 good. Quests are 4/4/5. |S| < 6.

The quests of size 4 can test paths of length 3 instead of paths of length 2 in the graph, and makes this the easiest size by far.

Case I: 4 claims. If there any adjacent pair (or even a pair at distance 2) we win. Otherwise, there is a player A in at least 3 claims. Guess the claim X they aren’t in. All players in X state the claimant. There are at least 6 players in that claim at most 3 of whom are evil. If we have a 4-2 split then A knows an additional claimant, if it’s the same as one of the claimants A knows then they rule out that claim and win. If it’s not the same then A is now informed and since there are no adjacent pairs of claims we win. If we have a 3-3 split, A now has two hypotheses for the evil players and tests both.

Case II: 5 claims. There is a player A in at least four sets, i.e. who is informed. We first guess the claim they aren’t in. Then on our next guess we can eliminate up to 3 claims from the connected component containing the true claim, and then we win since there is at most one remaining claim in that component.

Case III: 6 claims. All players are in four claims and so are informed. So we know which connected component contains the truth. With each of our first two quests we can test 3 claims from the corrected connected component, so we win without ever using the final quest.

10 players

Setting: 4 evil, 6 good. Quests are 4/4/5. There are at most 8 valid claims.

As with 9 players, the ability to test three claims at once is very strong.

Case I: 4 claims. Same deal as usual. If there is a pair of claims with overlap 4 we win since we can test them both at once. Otherwise, there is a player A in at least 3 claims. Guess the claim X that doesn’t contain A. Ask everyone to report the claimant for X. There are 6 people in the claim and only 4 evil people. If we get a 5-1 split then we know the last claimant (and either A can eliminate the other set they claimed or is now knows 4 claimants, either way we win since any two sets that contain at most 1 claimant will have an overlap of 4 with each other). Otherwise we can construct two pairs of people least one of which is all evil; each of those can be consistent with at most one claim (since any two 6-element subsets of the 8 possibly-good players will have overlap at least 4), so we can test those two claims.

Case II: 5 claims.

• Suppose there is a player A in at least 4 claims. Then guess the set not containing A.
  • If we get a 5-1 split we know another claimant B.
    • If B didn’t claim anything else, then A knows all claims. So A is informed, and then can go to town on the connected component containing the truth (eliminating 3 at a time).
    • If B claimed something else, we can eliminate that. Now there are three claims left. If two of those claims have intersection of size 4, we can test both and win. But A knows four claimants, any two six element sets that contain at most one of them must contain at least 5 of the other 6 players, and so must have intersection at least 4. So there can be at most one claim that contains 5 of the 6 non-claimants, and so A can guess that and we win.
  • In a 3-3 split, the claims consistent with either hypothesis must be pairwise adjacent. So we can test up to 3 (or all) claims consistent with the hypothesis consistent with more claims. Then either we’ve eliminated 3 claims and there is only one left so we win, or we’ve eliminated 2 claims and the other hypothesis is only consistent with 2 claims, so we can test both and win.
  • In a 4-2 split:
    • If there is unanimity amongst the 4, then let B be the player they all claim is the claimant.
      • If B is not the claimant of any other claim, then A is now informed if the 4 are correct. So A knows which connected component contains the truth. They can then test that entire connected component, either establishing that the other 4 are evil and then winning in the next step, or eliminating 3 claims from that connected component and leaving only a single claim that can be tested in the final step.
      • If B is the claimant of any other claim Y, then we can eliminate that claim (and eliminate as evil all players in the intersection between our original claim X and Y); there is at least one player C in the intersection call them C. The remaining claims must involve A and can’t involve either B or C (or they could be eliminated), so they must involve 5 of the remaining 8 players. Therefore two of them have intersection of size 4, and we can test both and win.
  • In a 3-3 split, any two claims consistent with either hypothesis must be adjacent. So we can test all claims consistent with either hypothesis with our second quest, then the < 2 claims consistent with the other hypothesis with our third quest.
• Suppose that every player A is in at most 3 claims. Then there can be at most 30 total claims, and a true claim must appear at least 6 times, so every player is in exactly 3 claims. If there is a pair of claims with intersection 4, test that pair with the first quest, otherwise test at random. If it fails, ask people to report the claimant.
  • If we get a 5-1 split, we know the claimant. That person appears in exactly 2 other claims. We can rule those out, and test the last claim in the last step.
  • If we get a 3-3 split, then we have two hypotheses for a set of 3 evil players. Any claim consistent with one of these hypotheses contains 6 of the other 7 players, and hence any two claims are adjacent. So we can test up to 3 claims consistent with the hypothesis that has more claims in our first attempt, either winning or proving the other hypothesis is right. Then the other hypothesis is consistent with at most 2 claims and we test them both with the last quest.
  • If we get a 2-4 split, then any two claims consistent with the 2 hypothesis have 6 of the 8 others and so have intersection of size at least 4. If there is any pair with intersection of size at least 4, then we eliminated 2 claims in the first step so have at most 3 left. So we can verify either the one or two consistent with the 2 hypothesis, either being left knowing that the 4 hypothesis is correct (in which case we know exactly who is good), or having only a single claim left consistent with the 2 hypothesis.

Case III: 6 claims. This was the last case I considered; I think the analysis is right but it almost certainly could be shortened by combining similar cases. Apologies to the reader.

• If there is a player in 5 claims, test the claim they aren’t in, then they are informed and can win easily.
• If there is a set of 3 adjacent claims XYZ, test all of them with the first claim, leaving only 3 more.
• Otherwise, there are at least six players in 4 claims.
  • Suppose there is a pair of claims XY that have intersection 4, and a player A who is in neither claim. Then test X and Y with the first quest. If it fails, everyone reports claimants and divide into two maximally balanced groups with non-overlapping reports.
    • If either X or Y has a 5-1 split, we identify a new claimant B. If that’s not the same claimant in any other claim involving A, then A is informed and we win. If it is the same, then A can rule out that claim. There is also at least one more player C in the intersection between those two claims, who A can rule out as evil. If the remaining 3 claims don’t involve either B or C, then they must involve five of the other 7 players. Thus each pair have overlap 4, so we can test two of them with our next quest and win.
    • If either X or Y has a 3-3 split, then we have two hypotheses. As usual, at most one of the remaining claims can be consistent with each (or else there is a pair we can simultaneously test), so we win.
    • If both X and Y have a 4-2 split, then the possible worlds are that both 2’s are evil, both 4’s are evil, or one 2 and one 4 are evil. If the two 4’s are identical, then there are effectively only two hypotheses, and we win. The 4+2 can both be evil only if a 2 is contained in the 4. In this case the two 2’s are disjoint so have union of size 4, and uniquely determine who is evil. Therefore all three hypotheses uniquely pin down all evil people, and the two people not in either of X or Y must be good. We win unless the complement of each of these 3 hypotheses appear as claims, so assume they do. Each hypothesis implicates 4 people as evil, out of the 8 involved in X or Y , so in total they implicate 12 people and there must be least 4 people who are implicated by at most one of the hypotheses. Two of these 4 people must be implicated by the same hypothesis. If we pick those two people, together with the two people not in X or Y, we can send that group on the second quest to rule out two of the three hypotheses. In the last step we test the last hypothesis.
  • Suppose that for every player A in four claims, the two claims not involving A have intersection only 3, or equivalently that each of the other 9 players appears in one of those two claims. Pick a pair X=BCDEFG, Y that intersect in size 3 such that A is in every other set. Our first test is X. If it fails, everyone reports the claimants.
    • If we get 5-1, then A knows another claimant.
      • If it’s not the same as a claimant in one of A’s sets, then A is informed, and so all possibilities consistent with A’s knowledge are adjacent. There can’t be three adjacent things all at once, much less four, so we can test all possibilities consistent with A’s knowledge in our second quest. If that fails, then A was evil and so we test claim Y (the only other claim not involving A).
      • If the claimant is B, who also claimed another set involving A, then A can rule out their other claim, plus the other person C in the intersection. Now we test Y (assuming it doesn’t contain B, if it does we skip the test); if it fails, we have players to report.
        • If we get 5-1, A learns yet another claimant. If different from A’s known claimants we win. Otherwise A gets to eliminate yet another claim, leaving only two possibilities. If the claimant is C, then there must be some other element D!=B in the intersection between C’s claim not involving A and C’s claiming involving A. (B isn’t in C’s new claim.) So now A knows the truth doesn’t contain BCD. If the claimant is D!=C, then again A knows the truth doesn’t contain BCD. Either way, there are only 7 potentially good people, so any two feasible quests are adjacent and we can test two of them.
        • If we get 4-2, we know that the 4 are good (since B isn’t in Y, there can be at most 3 evil people). This gives us two more evil people. Together with B, we have identified three evil people, and the remaining hypotheses are adjacent. Since we didn’t find three adjacent hypotheses before, there can be at most 2 and we can test both.
        • If we get 3-3, A is left with two hypotheses about the evil people. Neither of those hypotheses involves B, and at most one of them involves C. The hypothesis involving neither B nor C would now implicate 5 people and so is impossible. So A can figure out exactly who is good.
    • If we get 3-3, we have two hypotheses each of which implicates 3 people as evil. The set of claims consistent with either hypothesis are mutually adjacent. Neither can have size 3, or we would have found a set of 3 adjacent claims. So we can test each hypothesis with one additional query.
    • If we get 4-2, then assume that BC is the reporting group of size 2 and DEFG is the reporting group of size 4, and that B is the purported claimant by the group of size 4.
      • If ABCHIJ is not a claim, then we know that DEFG can’t all be evil.  In this case we know that B and C are evil.
        • If B is distinct from A’s other claimants, then A is informed and we can win easily (next test all claims consistent with A’s knowledge, assuming A is good, and then finally test claim Y).
        • Otherwise, A can rule out all claims containing B or C. Now we test claim Y, unless it contains B in which case we can rule it out immediately. If claim Y fails, we ask for claimants.
          • If we get 5-1, A gets another non-B claimant, and either becomes informed (in which case we win), or can rule out another pair of elements, one of which is not B, leaving only 7 plausibly good players. At that point any pair of legitimate claims are adjacent and we can test both to win (there can’t be three).
          • If we get 3-3, then only one contains C, neither contains B, so only one is possible and we win.
          • Similarly if we get 4-2 then we know the 2 are evil, so we win.
      • So assume Z=ABCHIJ is a claim.
        • If the intersection between X and Y contains one of BC, then it must also contain one of DEFG (since it has 3 > 2 elements) and so we can rule out Y. Likewise, if there is any claim involving A that contains one of BC and one of DEFG, we can eliminate it. If the claimant in that set was one of EFGHIJ then A can announce that fact, and we can rule out Y unless there is disagreement.
          • Suppose that  there was a claim W involving A that contains one of BC and one of DEFG, A claims the claimant is in EFGHIJ, but there is 4-2 or 3-3 disagreement. Label this claim W=ABD???.
            • If we have A on a side of size 2 or 3, then test EFGHIJ. If it fails, then A is good, we know 3 evil people, and we can test the remaining claims and win.
            • Otherwise we have a 2-4 disagreement with A on the side of size 4. The 4 can only plausibly be all evil if it is the complement of one of the plausible claims. The only live claim not including A is EFGHIJ, so the 4 must be ABCD.
              • If A’s reported claimant in W is in EFG, then the only options are that ABCD are evil, or that DEFG are evil. We can test each of those with two quests and win.
              • If A’s reported claimant in W is one of HIJ, call it H, then testing EFGHIJ would verify that A is good and that H is evil, hence DEFG aren’t all evil, hence BC are evil. Then there are only two live claims involving A, which now can be eliminate if they involve any of BCH, so must be adjacent, so we can test both with our final claim.
          • We now know that A is good and Y is false, and can ask people in Y to report claimants.
            • If we get 5-1, we get an extra claimant. If that’s a new claimant, then A wins. If it’s the same claimant, then A finds two new evil people (the claimant and the other person in both Y and that person’s other claim). Then we have three remaining live claims, and two players who are known as evil. The remaining live claims all involve 6 of the other 8 players, so have pairwise intersection 4, so we can test two at once with our second quest and then win with our third quest.
            • If we get 4-2, then we have four possible hypotheses: (i) the two reporting groups of size 4 are both all evil, (ii) the first group of size 4 and the second group of size 2 are both evil (which is possible only if the group of size 2 is a subset of the group of size 4), (iii) the first group of size 2 and the second group of size 4, (iv) the two groups of size 2 are both evil. Case (i) is impossible since the union would have size at least 5. At most one of case (ii) and case (iii) is possible, and it uniquely pins down the set of evil users, so we can test this with either our second or third quest.
              • If three claims involving A are pairwise adjacent, then we can test those three with our second quest and win with our first quest.
              • If the two reports in case (iv) involve different claimants and 3 distinct players, then in the second quest we can test the claim consistent with case (ii) or case (iii); if those fail we’ve identified two evil claimants and 7 players.
                • If either claimant is new for A, then A is informed, so A knows which connected component contains the truth, that component has size at most 2 (since there are no three pairwise adjacent claims) and so can win.
                • If both claimants are the same as existing claimants, then A can eliminate those existing claims leaving only two claims. Those two claims must not involve any of the three players A now knows to be evil, so they must be adjacent, so we can test both with our final quest and win.
              • If the two reports in case (iv) involve different claimants and only two distinct players, then label the claims X=BCDEFG, Y=BCDHIJ. But then neither case (ii) or (iii) is plausible, so we know that BC are are evil and we can win.
              • If the two reports in case (iv) involve the same player, then in case (iv) all three players in the intersection are evil. So all claims consistent with that hypothesis are adjacent, and up to 3 of them can be tested with our second quest. Then in our final quest we test the claim consistent with case (ii) or (iii).
            • If it’s 3-3, then we have a 4-2 disagreement and a 3-3 disagreement.
              • If the reporting group of size 4 contains a reporting group of size 3, then the 2 can’t both be evil (since there are only 3 elements in the intersection, which are apparently both in the reporting group of size 4, so this would imply 5 evil people.) So we know the 4 are evil and win.
              • If the reporting group of size 4 doesn’t contain a reporting group of size 3, then the 2 must be evil. A reporting group of size 3 that is all evil must intersect the reporting group of size 2. If there is only one, then we know at least 3 evil players and win. If there are two, then each uniquely determines the evil players and so we can test those two hypotheses with the remaining turns.
        • If the intersection between X and Y is disjoint from the reporters in the group of 2, then label such that X=BCDEFG and Y=EFGHIJ.
          • Otherwise, we test Y. If it fails, we know A to be good and we ask everyone for claimants.
            • If we get 5-1, then we have found an additional claimant. If it’s different from claimants that A knows, then A is informed and we win (since there can’t be 3 mutually adjacent claims, there are at most 2 adjacent claims consistent with A’s info and we can test both). So assume it’s the same.
              • If it’s one of EFG, label such that it’s E. Now consider the other claim made by E. This claim can’t contain B or C, since then we would have been able to eliminate E as evil and wouldn’t have tested Y. Thus it must contain one of HIJ, say H. Then we know that H is evil, so we can rule out ABCHIJ as a claim, so DEFG can’t all be evil, so we also know that BC are evil. Thus the evil players are BCEH and we win.
              • If it’s one of HIJ, label such that it’s H. Then we know H is evil, so can eliminate ABCHIJ, so we know that DEFG aren’t all evil, so we know that BC are evil. The other claim made by H must involve one of EFGIJ, we also know that player is evil, and we have all four evil players and win.
            • If we get 4-2…
              • If the 4 include HIJ, we can label such that they are GHIJ. If GHIJ are all evil, then we can’t explain the BC vs. DEFG disagreement. Thus EF are evil and BC are evil, so we win.
              • If the 4 don’t include HIJ, then we can rule out ABCHIJ. That means that DEFG aren’t all evil, so we know that BC are evil. The reporting group of size 4 can’t also be evil, so the reporting group of size 2 is evil, and we know all 4 evil people and we win.
            • If we get 3-3,  then least one reporting group is evil. BC aren’t in that group, and we can’t have 5 evil people, so BC aren’t both evil. Hence DEFG are all evil, and we win.

Case IV: 7 claims. In this case there are 42 reports, so there are at least 2 people, A and B, who are in claims and hence know all 5 claimants.  A and B are each excluded from at most 2 claims.

Note that in either our first or second quest we have the option to test all claims that exclude both A and B, since all such claims must contain 6 of the remaining 8 players and so have intersection 4 (though we don’t do that yet).

• If all components of the adjacency graph have size < 2, then in the first quest we test whether A and B are both evil. If not, then we can use our second and third quests to test the connected components identified by A and B respectively.
• Otherwise the adjacency graph has a connected component of size at least 3, so we can pick a path of length 3 in the graph and test those three claims. We now are have at most 4 remaining claims.
  • If there is a component of size 3 then we can test that with our second quest and the last claim with our last quest.
  • If all components have size < 2, then we ask A and B which component contains the truth.
    • If they agree, then we use our second quest to ensure that AB aren’t both evil. If they aren’t both evil then we use our final quest to test the two connected claims in the component that we know contains the truth.
    • If they disagree, then the only live claims are those where one of A and B is good and the other is evil.
      • If there are four such claims, then we know that A and B can’t both be evil. So we’ve reduced to two possible connected components, each of which has size < 2. So we can test one of each with our second and third claims.
      • If there are two such claims, then we can test each of them and win.
      • If there are three such claims XYZ, then label such that claim X includes only A, claim Y includes only B, and claim Z includes neither.  Consider the three claims that we ruled out with our first quest. Each of these must have contained both A and B. Each of A and B must report three distinct claimants for these three claims (or else we know they aren’t good). Each other player in each of these claims can then state which of A and B they agree with.
        • If A and B disagree about two of these claimants, then we obtain 5 players CDEFG each of whom was in one of the disagreeing claims and so can state which of A and B they agree with. Because at least one of A and B is evil, there can be at most 3 evil players amongst CDEFG.
          • If we get a 5-0 split or 4-1 split, we know the majority is honest and so can rule out one of of A and B as evil, we rule out one claim and win.
          • If we get a 3-2 split, label such that CD support A and EFG support B.  Then X=ACDHIJ. Z cannot avoid the set EFG as well as AB, so it contains a player from EFG, so we can rule out Z unless it contains no players from CD. So we win unless Z=EFGHIJ. Then Y must avoid ACD, so it must contain B and five of EFGHIJ, so we can test Y and Z at the same time and win.
        • If A and B agree about two of these claimants, they agree that both C and D are evil. Then we know that the claim including A and the claim including B both most exclude C and D, or else we can rule them out and win. So they each contain 6 of the other 8 players, so have intersection of size 4, so we can test both with our second quest and then win with our third.

Case V: 8 claims. In this case, there are 48 claims, and therefore at least 8 people who are judged as honest in 5 claims, and hence who know all 5 claimants. We can ask these 8 to report which connected component of the adjacency graph contains the real claim. If they disagree and split 5-3, then the 5 must be correct. If they split 4-4, then the other two players are known to be good, and those two players still appear in at least 3 claims and hence can tell which of the two groups of size 4 is good (since the other contains 2 claimants) and we win.

So we can always tell which connected component the true claim is in. Our first two quests can test 3 claims from the connected component of the truth, and our final quest can test up to 2 claims, exhausting all claims.