Traitors is a fun national UK TV show, that is often lamented as having little to no information to go on, but is this True? I don’t think so, with one key assumption:
Traitor do not vote for each other
- With possible relaxation: Unless the other traitor is successfully banished.
This is because in the context of the show, the Traitors are working together, voting out your fellow Traitor (and failing) is obviously bad strategy.
From here we can create “clusters” of players that have not directly opposed each other, and can infer that at least one of these clusters incorporates all of the traitors.
I represent this as a graph, starting fully connected between all players, and once a player votes against someone else, we remove the linkage.
We can then cluster the graph into fully connected nodes. Nodes may be part of more than one cluster, but all traitors must be in at least one cluster.
Since this is symmetrical, we only need the top half, and of course players don’t vote for themselves so we don’t need the diagonal either.
import numpy as np
n_players = 8
# graph = ~np.identity(n_players).astype(bool)
graph = np.triu(np.ones((8, 8)), k=1)
traitors = {7, 3, 5}
graph # fully connectedarray([[0., 1., 1., 1., 1., 1., 1., 1.],
[0., 0., 1., 1., 1., 1., 1., 1.],
[0., 0., 0., 1., 1., 1., 1., 1.],
[0., 0., 0., 0., 1., 1., 1., 1.],
[0., 0., 0., 0., 0., 1., 1., 1.],
[0., 0., 0., 0., 0., 0., 1., 1.],
[0., 0., 0., 0., 0., 0., 0., 1.],
[0., 0., 0., 0., 0., 0., 0., 0.]])Them we can start making our clusters! Let’s start with all connected pairs, then we can merge them together from there.
def cluster_pairs(graph):
def has_edge(i, j):
return graph[i, j]
n = len(graph)
return [set([i, j]) for i in range(n) for j in range(i+1, n) if has_edge(i, j)]
pairs = cluster_pairs(graph)
pairs[{0, 1},
{0, 2},
{0, 3},
{0, 4},
{0, 5},
{0, 6},
{0, 7},
{1, 2},
{1, 3},
{1, 4},
{1, 5},
{1, 6},
{1, 7},
{2, 3},
{2, 4},
{2, 5},
{2, 6},
{2, 7},
{3, 4},
{3, 5},
{3, 6},
{3, 7},
{4, 5},
{4, 6},
{4, 7},
{5, 6},
{5, 7},
{6, 7}]Nice! now we want to iteratively merge these clusters together.
This can be shown as the property: (0, 1) (1, 2) (0, 2) => (0, 1, 2)
In the case shown above, we have a fully connected cluster between (0, 1, 2).
def merge_clusters(clusters: list[set[int]]):
"""
(0, 1) (1, 2) (0, 2) => (0, 1, 2)
(0, 1, 2) (1, 2, 3) (0, 3) => (0, 1, 2, 3)
"""
new = True
while new:
new = False
for i in range(len(clusters)):
c = clusters[i]
for c2 in clusters[i+1:]:
req = c.symmetric_difference(c2)
new_c = c.union(c2)
if req in clusters and new_c not in clusters:
clusters.append(new_c)
new = True
return clusters
clusters = merge_clusters(pairs)
clusters[::13] # one every 13, there's alot, and this is evenly divisible by len(clusters) so we see first and last[{0, 1},
{2, 3},
{5, 7},
{0, 3, 4},
{1, 2, 6},
{0, 1, 3, 6},
{0, 1, 6, 7},
{0, 1, 2, 3, 4},
{0, 1, 2, 4, 5},
{1, 2, 6, 7},
{0, 1, 3, 4, 7},
{3, 5, 6},
{1, 2, 3, 5, 7},
{0, 4, 5, 6},
{0, 1, 2, 4, 5, 7},
{1, 2, 3, 4, 5, 6},
{0, 3, 4, 6, 7},
{1, 2, 5, 6, 7},
{0, 1, 4, 5, 6, 7}]That’s better, but we get many clusters that are subsets of others. For the base case before anyone has voted, we should just have a single cluster of every player: 0, 1, 2, 3, 4, 5, 6, 7
def prune_clusters(clusters: list[set[int]], must_include: None | set[int]):
def is_child(i, j):
return clusters[i].issubset(clusters[j])
n = len(clusters)
disjoint = [clusters[i] for i in range(n) if not any(is_child(i, j) for j in range(i+1, n))]
if must_include:
return [c for c in disjoint if c.issuperset(must_include)]
return disjoint
prune_clusters(clusters, must_include=None)[{0, 1, 2, 3, 4, 5, 6, 7}]Nice! prune_clusters also has one extra functionality, must_include, for when we require all clusters must include certain players.
This will be useful later when we find a traitor, we will be further able to filter the clusters!
Now let’s package this all together.
def get_clusters(graph, must_include: None | set[int]) -> list[set[int]]:
pairs = cluster_pairs(graph)
clusters = merge_clusters(pairs)
clusters = prune_clusters(clusters, must_include)
return clusters
get_clusters(graph, must_include=None)[{0, 1, 2, 3, 4, 5, 6, 7}]from typing import List, Set, Optional, FrozenSet
def _build_neighbors(graph) -> List[Set[int]]:
"""
Turn an adjacency matrix into a list of neighbor sets.
Assumes `graph[i][j]` (or graph[i, j]) is truthy if there's an edge i--j.
"""
n = len(graph)
nbrs: List[Set[int]] = [set() for _ in range(n)]
for i in range(n):
for j in range(n):
if i != j and graph[i][j]:
nbrs[i].add(j)
return nbrs
def _bron_kerbosch_pivot(
R: Set[int],
P: Set[int],
X: Set[int],
nbrs: List[Set[int]],
out: Set[FrozenSet[int]],
):
"""
Bron–Kerbosch with pivoting.
R = current clique we're growing
P = candidates that can still join R
X = nodes already processed (to avoid duplicates)
out = set of maximal cliques we’ve found (as frozensets)
"""
if not P and not X:
# R is maximal. Only keep size >= 2 to match your original behavior.
if len(R) >= 2:
out.add(frozenset(R))
return
# Pivot heuristic: pick u that maximises |P ∩ N(u)| to reduce branching
u = max(P | X, key=lambda u_: len(P & nbrs[u_])) if (P or X) else None
# Explore all vertices in P that are NOT neighbors of the pivot
# This is the standard pivot trick to cut search.
for v in list(P - (nbrs[u] if u is not None else set())):
_bron_kerbosch_pivot(
R | {v},
P & nbrs[v],
X & nbrs[v],
nbrs,
out,
)
P.remove(v)
X.add(v)
def _maximal_cliques(graph) -> Set[FrozenSet[int]]:
"""
Return all maximal cliques (as frozensets of node indices).
"""
nbrs = _build_neighbors(graph)
P = set(range(len(graph)))
out: Set[FrozenSet[int]] = set()
_bron_kerbosch_pivot(set(), P, set(), nbrs, out)
return out
def get_clusters(graph, must_include: Optional[Set[int]]) -> List[Set[int]]:
"""
Public API: return maximal cliques as sets of ints.
If must_include is not None, only return cliques that contain all of those nodes.
"""
cliques = [set(c) for c in _maximal_cliques(graph)]
if must_include:
cliques = [c for c in cliques if c.issuperset(must_include)]
return cliques
get_clusters(graph, must_include=None)[{0, 1, 2, 3, 4, 5, 6, 7}]Now we have foundational data structures, lets do something interesting with them!
As we mentioned before, voting removes edges in the graph so let’s implement that and see the effect on the clusters.
def rm_edges(graph, edges: list[tuple[int, int]]):
new = graph.copy()
for i,j in edges:
new[i, j] = False
new[j, i] = False
return new
votes = [[0,1], [1,2], [2,7], [3,4], [4,0], [5,6], [6,3], [7,2]]
graph_voted = rm_edges(graph, votes)
get_clusters(graph_voted, must_include=None)[{4, 6, 7},
{1, 3, 5, 7},
{0, 2, 6},
{0, 2, 3, 5},
{1, 4, 5, 7},
{0, 7},
{1, 4, 6, 7},
{4, 5, 7}]Great! so from just one voting round, we can start to narrow down our options. For example, if player 1 is a traitor player 7 is also a traitor, player 4 can be a traitor with 2 and 1, etc. And this will get further filtered in subsequent rounds.
We can first count the votes to see who lost this round (a tie means noone is removed)
def max_vote(votes):
send, recv = zip(*votes) # we only care about receiving votes
vals, counts = np.unique_counts(recv)
idx = counts.argmax()
most_voted_player, n_votes = vals[idx].item(), counts[idx].item()
if np.sum(counts == n_votes) != 1:
print(f"tie of {n_votes} votes, no player removed")
return None
else:
print(f"player {most_voted_player} got {n_votes} votes!")
return most_voted_player
lost_player = max_vote(votes)
f"{lost_player=}"player 2 got 2 votes!'lost_player=2'Now lets handle the logic of when a player is voted out.
must_include.
rm_edge_traitor flag.def rm_player(graph, i):
new = graph.copy()
new[i, :] = False
new[:, i] = False
return new
def is_traitor(i):
return i in traitors
def do_vote(graph, votes, must_include, ignore, rm_edges_traitor: bool = False):
lost_player = max_vote(votes)
if lost_player:
ignore = ignore[:] + [lost_player]
if is_traitor(lost_player):
must_include = must_include[:] + [lost_player]
else:
graph = rm_player(graph, lost_player)
# tie or not traitor or remove edges anyway
if (not lost_player) or (not is_traitor(lost_player)) or rm_edges_traitor:
graph = rm_edges(graph, votes)
return graph, must_include, ignore
g, mi, ignore = do_vote(graph, votes, must_include=set(), ignore=[])
get_clusters(g, mi)player 2 got 2 votes![{1, 3, 5, 7}, {0, 6, 7}, {1, 4, 5, 7}, {1, 4, 6, 7}, {0, 3, 5, 7}]def one_game(graph, votes, must_include, ignore, rm_edges_traitor: bool = False, i2p = lambda i: str(i)):
"""Wrapper around do_vote"""
vote_str = " | ".join([f"{i2p(i)} -> {i2p(j)}" for i, j in votes])
print(f"Votes: {vote_str}")
# WORK
graph, must_include, ignore = do_vote(graph, votes, must_include, ignore, rm_edges_traitor=rm_edges_traitor)
must_include_str = ', '.join(map(i2p, must_include)) if must_include else "None"
print(f"Traitors found: {must_include_str}")
print("Clusters at end of turn:")
print("\n".join([" ".join([i2p(i) for i in s if i not in ignore]) for s in get_clusters(graph, must_include)]))
print("-" * 20)
return graph, must_include, ignore
game = [
[ [0,1], [1,2], [2,7], [3,4], [4,0], [5,6], [6,3], [7,2] ], # player 2
[ [0,5], [1,4], [3,0], [4,0], [5,2], [6,4], [7,6] ], # tie -- noone removed
[ [0,7], [1,0], [3,7], [4,7], [5,4], [6,5], [7,2] ] # player 7 traitor, traitor 3 votes for 7 too
]
# regen incase run twice
graph = np.triu(np.ones((8, 8)), k=1)
must_include = []
ignore = []
for votes in game:
graph, must_include, ignore = one_game(graph, votes, must_include, ignore, rm_edges_traitor=False)Votes: 0 -> 1 | 1 -> 2 | 2 -> 7 | 3 -> 4 | 4 -> 0 | 5 -> 6 | 6 -> 3 | 7 -> 2
player 2 got 2 votes!
Traitors found: None
Clusters at end of turn:
1 3 5 7
0 6 7
1 4 5 7
1 4 6 7
0 3 5 7
--------------------
Votes: 0 -> 5 | 1 -> 4 | 3 -> 0 | 4 -> 0 | 5 -> 2 | 6 -> 4 | 7 -> 6
tie of 2 votes, no player removed
Traitors found: None
Clusters at end of turn:
0 6
1 3 5 7
1 6
0 7
4 5 7
--------------------
Votes: 0 -> 7 | 1 -> 0 | 3 -> 7 | 4 -> 7 | 5 -> 4 | 6 -> 5 | 7 -> 2
player 7 got 3 votes!
Traitors found: 7
Clusters at end of turn:
1 3 5
0
4 5
--------------------If we assume 3 traitors, we can discard cluster (0, 7), making the remain traitors either 2 of (1, 3, 5) or both (4, 5).
(True answer is the traitors are (3, 5, 7)).
| Player | Round 1 | Round 2 | Round 3 | Round 4 | Round 5 | Round 6 |
|---|---|---|---|---|---|---|
| Alan | Niko | Celia | David | Mark | Mark | Joe M. |
| Cat | Kate | Stephen | Stephen | David | David | Stephen |
| Celia | Charlotte | Cat | David | Jonathan | David | Joe M. |
| David | Niko | Stephen | Clare | Stephen | Stephen | |
| Joe M. | Niko | Kate | Jonathan | Mark | Mark | Jonathan |
| Jonathan | Niko | Ruth | Clare | David | David | Stephen |
| Kate | Tameka | Tameka | Clare | Mark | Mark | Nick |
| Lucy | Niko | David | Clare | Mark | Mark | Jonathan |
| Nick | Niko | Tameka | Celia | Kate | Mark | Stephen |
| Stephen | Niko | Charlotte | Clare | David | David | David |
| Joe W. | Tom | Jonathan | Clare | David | David | |
| Mark | Tameka | Tameka | Charlotte | Kate | ||
| Charlotte | Niko | Tameka | Clare | |||
| Clare | Niko | Alan | Charlotte | |||
| Ruth | Kate | Jonathan | ||||
| Tameka | Kate | Celia | ||||
| Tom | Niko | |||||
| Niko | Tom | |||||
| Paloma |
players = ["alan", "cat", "celia", "david", "joe_m", "jonathan", "kate", "lucy", "nick", "stephen", "joe_w", "mark", "charlotte", "clare", "ruth", "tameka", "tom", "niko", "paloma"]
game = [
# Round 1
[
("alan", "niko"),
("cat", "kate"),
("celia", "charlotte"),
("david", "niko"),
("joe_m", "niko"),
("jonathan", "niko"),
("kate", "tameka"),
("lucy", "niko"),
("nick", "niko"),
("stephen", "niko"),
("joe_w", "tom"),
("mark", "tameka"),
("charlotte", "niko"),
("clare", "niko"),
("ruth", "kate"),
("tameka", "kate"),
("tom", "niko"),
("niko", "tom")
],
# Round 2
[
("alan", "celia"),
("cat", "stephen"),
("celia", "cat"),
("david", "stephen"),
("joe_m", "kate"),
("jonathan", "ruth"),
("kate", "tameka"),
("lucy", "david"),
("nick", "tameka"),
("stephen", "charlotte"),
("joe_w", "jonathan"),
("mark", "tameka"),
("charlotte", "tameka"),
("clare", "alan"),
("ruth", "jonathan"),
("tameka", "celia")
],
# Round 3
[
("alan", "david"),
("cat", "stephen"),
("celia", "david"),
("david", "clare"),
("joe_m", "jonathan"),
("jonathan", "clare"),
("kate", "clare"),
("lucy", "clare"),
("nick", "celia"),
("stephen", "clare"),
("joe_w", "clare"),
("mark", "charlotte"),
("charlotte", "clare"),
("clare", "charlotte")
],
# Round 4
[
("alan", "mark"),
("cat", "david"),
("celia", "jonathan"),
("david", "stephen"),
("joe_m", "mark"),
("jonathan", "david"),
("kate", "mark"),
("lucy", "mark"),
("nick", "kate"),
("stephen", "david"),
("joe_w", "david"),
("mark", "kate")
],
# Round 5
[
("alan", "mark"),
("cat", "david"),
("celia", "david"),
("joe_m", "mark"),
("jonathan", "david"),
("kate", "mark"),
("lucy", "mark"),
("nick", "mark"),
("stephen", "david"),
("joe_w", "david")
],
# Round 6
[
("alan", "joe_m"),
("cat", "stephen"),
("celia", "joe_m"),
("david", "stephen"),
("joe_m", "jonathan"),
("jonathan", "stephen"),
("kate", "nick"),
("lucy", "jonathan"),
("nick", "stephen"),
("stephen", "david")
]
]
def p2i(p): return players.index(p)
def i2p(i): return players[i]
def vp2vi(vp): return [(p2i(i), p2i(j)) for i, j in vp]
print(i2p(2))
vp2vi(game[1])celia[(0, 2),
(1, 9),
(2, 1),
(3, 9),
(4, 6),
(5, 14),
(6, 15),
(7, 3),
(8, 15),
(9, 12),
(10, 5),
(11, 15),
(12, 15),
(13, 0),
(14, 5),
(15, 2)]n_players = len(players)
graph = np.triu(np.ones((n_players, n_players)), k=1)
must_include = []
ignore = [p2i("joe_w"), p2i("charlotte"), p2i("ruth"), p2i("tom"), p2i("paloma")]
for votes in game:
graph, must_include, ignore = one_game(graph, vp2vi(votes), must_include, ignore, rm_edges_traitor=True, i2p=i2p)Votes: alan -> niko | cat -> kate | celia -> charlotte | david -> niko | joe_m -> niko | jonathan -> niko | kate -> tameka | lucy -> niko | nick -> niko | stephen -> niko | joe_w -> tom | mark -> tameka | charlotte -> niko | clare -> niko | ruth -> kate | tameka -> kate | tom -> niko | niko -> tom
player 17 got 10 votes!
Traitors found: None
Clusters at end of turn:
alan cat celia david joe_m jonathan lucy nick stephen tameka
alan kate lucy nick stephen mark clare
alan kate lucy nick stephen
alan cat celia david joe_m jonathan lucy nick stephen
alan cat celia david joe_m jonathan lucy nick stephen mark clare
alan cat clare tameka
--------------------
Votes: alan -> celia | cat -> stephen | celia -> cat | david -> stephen | joe_m -> kate | jonathan -> ruth | kate -> tameka | lucy -> david | nick -> tameka | stephen -> charlotte | joe_w -> jonathan | mark -> tameka | charlotte -> tameka | clare -> alan | ruth -> jonathan | tameka -> celia
player 15 got 4 votes!
Traitors found: None
Clusters at end of turn:
celia stephen mark clare
clare
alan cat lucy nick mark
celia david kate nick
alan cat david joe_m nick
alan cat david joe_m nick mark
alan stephen
alan kate lucy nick
alan stephen mark
stephen celia
alan kate lucy nick stephen mark
celia david kate nick mark clare
alan kate lucy nick stephen
celia david joe_m nick
celia david joe_m nick mark clare
alan cat lucy nick
--------------------
Votes: alan -> david | cat -> stephen | celia -> david | david -> clare | joe_m -> jonathan | jonathan -> clare | kate -> clare | lucy -> clare | nick -> celia | stephen -> clare | joe_w -> clare | mark -> charlotte | charlotte -> clare | clare -> charlotte
player 13 got 7 votes!
Traitors found: None
Clusters at end of turn:
celia kate lucy stephen mark
david kate nick
david joe_m nick mark
alan cat joe_m lucy nick
david jonathan kate nick
celia kate lucy stephen
alan kate lucy nick stephen
david kate nick mark
alan cat jonathan lucy nick mark
alan stephen mark
alan kate lucy nick
david jonathan kate nick mark
alan cat joe_m lucy nick mark
celia jonathan kate lucy stephen mark
celia joe_m lucy stephen mark
david joe_m nick
alan cat jonathan lucy nick
david joe_m nick
alan cat joe_m lucy nick
alan stephen
alan kate lucy nick stephen mark
celia joe_m lucy stephen
david kate nick
--------------------
Votes: alan -> mark | cat -> david | celia -> jonathan | david -> stephen | joe_m -> mark | jonathan -> david | kate -> mark | lucy -> mark | nick -> kate | stephen -> david | joe_w -> david | mark -> kate
tie of 4 votes, no player removed
Traitors found: None
Clusters at end of turn:
celia kate lucy stephen
alan kate lucy stephen
david joe_m nick
alan cat joe_m lucy nick
celia mark
alan stephen
david kate
alan stephen
celia kate lucy stephen
mark
alan kate lucy stephen
celia joe_m lucy stephen
celia joe_m lucy stephen
alan cat joe_m lucy nick
david mark
alan cat jonathan lucy nick
alan kate lucy
--------------------
Votes: alan -> mark | cat -> david | celia -> david | joe_m -> mark | jonathan -> david | kate -> mark | lucy -> mark | nick -> mark | stephen -> david | joe_w -> david
tie of 5 votes, no player removed
Traitors found: None
Clusters at end of turn:
celia kate lucy stephen
alan kate lucy stephen
david joe_m nick
alan cat joe_m lucy nick
celia mark
alan stephen
david kate
alan stephen
celia kate lucy stephen
mark
alan kate lucy stephen
celia joe_m lucy stephen
celia joe_m lucy stephen
alan cat joe_m lucy nick
david mark
alan cat jonathan lucy nick
alan kate lucy
--------------------
Votes: alan -> joe_m | cat -> stephen | celia -> joe_m | david -> stephen | joe_m -> jonathan | jonathan -> stephen | kate -> nick | lucy -> jonathan | nick -> stephen | stephen -> david
player 9 got 4 votes!
Traitors found: None
Clusters at end of turn:
david joe_m nick
celia mark
mark
alan kate lucy
alan cat jonathan nick
alan kate lucy
celia kate lucy
joe_m lucy nick
celia kate lucy
celia
david kate
david mark
joe_m lucy nick
alan cat lucy nick
alan cat lucy nick
--------------------