You can trust me, but should you? Illustrating Mafia by Graph Theory
Link: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1227&context=statistics_papers
In the classic party game of Mafia, a tense and drawn out psychological battle occurs between an informed minority (the mafia) and uninformed majority (townsfolk). The mafia performs killings at night, their actions unknown to townsfolk until the light of day when it is announced who had perished. All players then enter discussion: voicing suspicions, forming alliances, colluding in the open, crafting smokes and mirrors etc. in their own interests, that is to correctly identify the guilty (if you’re a townie) or send an innocent on the block otherwise. Everyone votes for who shall be lynched during the day, tentatively or resolutely and everything in between, often painting what looks like desperate mob rule especially in early stages of the game. It is rather common for a successive lynching of innocent people to occur, which the simple fact that more people are assigned townsfolk than mafia from the onset can easily account for and it is tempting to assume everyone shares an equal probability of being lynched by the town. Perhaps that isn’t quite the case, as we view the game through the lens of Graph Theory.
It is fitting to denote players as individual nodes connected by edges, the level of trust they have for each other. A directed graph is appropriate as non-mafia players are generally only truly confident about their individual identity. In lecture, these edges were arbitrarily assigned strong or weak labels to indicate the level of closeness, in this setup— at least in the very beginning— we can denote any edge between two mafia members as strong (they’ve seen other at night) and all other edges in the graph as weak. When a player dies, their node is removed from the setting for the graph to remain connected.
As the game goes on, mafia players intend to convince innocent members to trust them. So it could be helpful to relabel an edge from A to B to “strong” when A decides B can be trusted (correctly or not.) Now we can enlist the “Strong” Triadic Closure Property to understand why it is a common technique for mafia members to target innocent individuals in seek of their trust. The STCP purports a strong edge is then likely to form between the unknowing townie and a different mafia member. It is in mafia’s interest to expand the number of strong ties to the pre-existing subgraph of mafia members, and as they inch towards becoming a (strong-labeled) giant component they are outnumbering the isolated townsfolk swiftly.
That the graph is unbalanced to begin with well explains why the mafia, provided they collude effectively, have a strong chance of winning. Clearly not everyone in the graph has strong ties with each other since innocent players are much more hesitant to “trust” other players, and nor do we have a bipartite network as townsfolk are unable to identify each other. This leaves us to muse on the power of an agenda-driven informed component of a graph, however small they are to begin with, because their rate of expansion outstrips that of an unaware majority.