Project for Multi-Agent Systems

Reasoning in the game of Mafia

by
Ben van Os
ben.van.os@gmail.com
&
Margreet Vogelzang
margreetvogelzang@gmail.com

Overview:

  1. Introduction
  2. Problem description
  3. Implementation
  4. Output and results
  5. Documents

1 Introduction

The game of Mafia (“Weerwolven”) is a popular party game, based on the principle of informed minority versus uninformed majority. Mafia can be played with different numbers of players and in many different versions. In this project we analyzed the reasoning processes in the so-called Dethy variant, a 5-player variant. We have chosen this variant because it involves a greater amount of logical reasoning about other players than most other variants, and because the relatively small amount of players keeps the project at a manageable size.

2 Problem description

At the beginning of the game, the following 5 roles are randomly assigned to the 5 players:
  • 1 Mafia
  • 1 Sane Cop
  • 1 Insane Cop
  • 1 Paranoid Cop
  • 1 Naïve Cop
    Cops are not aware of their own sanity, e.g. all 4 of them receive a generic “Cop” role.

    The game objective of the town faction, consisting of the 4 cops, is to eliminate the mafia from the game. The mafia wins by eliminating all 4 cops. The game consists of the following phases:

    Night 1:
    All 4 cops can investigate 1 of the players, including themselves, and get a result from the game master: guilty if they perceive their target as the Mafia member, innocent if they believe it's a fellow cop. However, there's a twist: each cop has a sanity. Only the sane cop gets correct results. The paranoid cop will always get a guilty result, even if he targeted a fellow cop. The naïve cop will never detect the Mafia – he always gets innocent. The insane cop is truly mad: He'll always find the opposite result of the sane cop, guilty on fellow cops and innocent on the mafia.
    During the first night the mafia does nothing.

    Day 1:
    All 5 players can now debate. The 4 cops aim to discover who the Mafia player is, and the Mafia attempts to convince the cops of his innocence by any lies and deceit he can think of. Usually players reveal the results of their investigations in this phase – the Mafia can of course fake an investigation result. Discussion continues until a majority of the players agrees on a lynch target: the lynched person 'dies' and is not allowed to participate in the game any further.
    If the lynched person was the Mafia, the game ends in a town win. If it was a cop, the game continues with a second night.

    Night 2:
    In night 2 the 3 surviving cops again get the opportunity to investigate one of the other players. However, in this night the Mafia also murders 1 of the remaining cops.

    Day 2:
    Day 2 begins with the announcement of the murder by the game master. The murdered cop is eliminated from the game, therefore there are now 3 players alive: the Mafia and 2 cops. After another round of discussion another player is lynched by a majority vote.
    After the lynch the winner is declared: on Mafia elimination the town wins, if the Mafia is still alive, nothing can prevent him from shooting the cop the next night and complete his winning objective, and he is declared the winner.

    Example game

    On day 1, the following 5 results are claimed:
    Aristotle claims Plato is innocent
    Plato claims Descartes is guilty
    Wittgenstein claims Descartes is innocent
    Kripke claims Descartes is innocent
    Descartes claims Kripke is innocent

    After observing a green apple and a black raven our philosophers get to work. It is immediately obvious Plato must be paranoid – the paranoid cop always gets a guilty result, and there is only 1 guilty player who got this result. Since Plato is guaranteed to be innocent, then, it follows that Aristotle is either naive or sane.

    However, when we then examine Descartes we run into a discrepancy – if Descartes were a cop, both Aristotle and Wittgenstein would have to be either naive or sane. That doesn't match with the information we have about Aristotle. We are left with only two possible explanations:

    1:
    Aristotle – Sane
    Plato - Paranoid
    Wittgenstein – Naive
    Kripke – Insane
    Descartes – Mafia

    2:
    Aristotle – Sane
    Plato - Paranoid
    Wittgenstein – Insane
    Kripke – Naive
    Descartes – Mafia

    In both of these possible Kripke worlds Descartes is the Mafia, so our philosophers now know what to do. Descartes attempts to demand a surprise execution before the next Friday, but the others will have none of it and club him to death with a copy of Tractatus.
    Town wins!

    3 Implementation

    Possible worlds

    Each player has a Kripke Model containing all 120 (5!) possible worlds. A cop can immediately eliminate all worlds in which he is the Mafia because he knows he is innocent. Each player therefore starts with 94 connected worlds in their personal Knowledge Base (the Vector KB). The mafia also keeps his KB updated based on the premesis that he is innocent: to act reliably like a player it's important he reasons about the knowledge the other players have.

    After each night, the Knowledge Bases of all the players are updated with the new knowledge that came available from the latest investigations and the deaths. All the investigations made are announced in the group and therefore become Common Knowledge (they are saved in the Vector CK). The Mafia fakes an investigation. The Knowlede Bases are updated by checking all possible Kripke Worlds for contradictions.

    Tactics and assumptions

    For the purposes of this implementation we have assumed the following:

  • All cops behave rationally - they use all deducible information and they aim to lynch the player with the highest odds of being Mafia. This is the person who is the Mafia in most of the remaining worlds. If there is a tie (the odds of two players being the Mafia are equal), one of the people with the highest odds is lynched randomly.

  • All cops tell their investigation results truthfully. The only one who lies (makes up an investigation) is the Mafia. There are therefore always 4 truthful results and 1 made up result the first night and 2 trusthful results and 1 made up result the second night. The program can handle the lying of the Mafia because it only deletes worlds from a Knowledge Base when it is certain that a player can not have a certain sanity anymore. So, a world is not deleted because e.g. player 0 can not be the Mafia, but because player 1 can not be naïve. The only way you can throw away worlds because you know a certain player is not the Mafia is because either he is dead (after deadth it is annouced whether the player was a civilian or the Mafia) or he is the only one left that could have a certain sanity of a cop.

  • The Mafia wants to kill the cop with the lowest probability of being the Mafia, to increase his own chances. That is, he wants the town to lynch someone other than himself, so he will leave other players with a high Mafia probability alive. This is computed the same way as the odds for the person to be lynched by the town are computed, only the person with lowest score is murdered here.

    4 Output and results

    An example of the output of the the program is given below. The vectors labeled sanities show all possible worlds one player has left in his Knowledge Base. E.g. on day 1 the in first world player 0 still has in his KB player 1 is the Mafia (sanity 0), player 0 is the sane cop (sanity 1), and so on.
    The vector named 'odds player #' shows, given the possible worlds, what the odds are of each player being the Mafia. Player 0 knows he is not the Mafia so the odds of him being the Mafia are 0. Player 0 thinks the odds of player 1 being the Mafia, however, are 0.5.

    Output

    player 0 has sanity naive
    player 1 has sanity insane
    player 2 has sanity mafia
    player 3 has sanity sane
    player 4 has sanity paranoid

    NIGHT 1

    Investigator: 0 Target: 3 Result: false
    Investigator: 1 Target: 2 Result: false
    Investigator: 2 Target: 0 Result: false
    Investigator: 3 Target: 2 Result: true
    Investigator: 4 Target: 4 Result: true

    DAY 1

    possible worlds player 0:
    sanities: 1 0 4 2 3
    sanities: 1 0 4 3 2
    sanities: 1 4 0 2 3
    sanities: 3 1 4 0 2
    sanities: 3 4 1 0 2
    sanities: 4 0 1 2 3
    sanities: 4 0 1 3 2
    sanities: 4 3 0 1 2
    odds player 0:
    0.0 0.5 0.25 0.25 0.0

    possible worlds player 1:
    sanities: 0 1 4 2 3
    sanities: 0 1 4 3 2
    sanities: 1 4 0 2 3
    sanities: 3 1 4 0 2
    sanities: 3 4 1 0 2
    sanities: 4 3 0 1 2
    odds player 1:
    0.33 0.0 0.33 0.33 0.0

    possible worlds player 2:
    sanities: 0 1 4 2 3
    sanities: 0 1 4 3 2
    sanities: 1 0 4 2 3
    sanities: 1 0 4 3 2
    sanities: 3 1 4 0 2
    sanities: 3 4 1 0 2
    sanities: 4 0 1 2 3
    sanities: 4 0 1 3 2
    odds player 2:
    0.25 0.5 0.0 0.25 0.0

    possible worlds player 3:
    sanities: 0 1 4 2 3
    sanities: 0 1 4 3 2
    sanities: 1 0 4 2 3
    sanities: 1 0 4 3 2
    sanities: 1 4 0 2 3
    sanities: 4 0 1 2 3
    sanities: 4 0 1 3 2
    sanities: 4 3 0 1 2
    odds player 3:
    0.25 0.5 0.25 0.0 0.0

    possible worlds player 4:
    sanities: 0 1 4 2 3
    sanities: 0 1 4 3 2
    sanities: 1 0 4 2 3
    sanities: 1 0 4 3 2
    sanities: 1 4 0 2 3
    sanities: 3 1 4 0 2
    sanities: 3 4 1 0 2
    sanities: 4 0 1 2 3
    sanities: 4 0 1 3 2
    sanities: 4 3 0 1 2
    odds player 4:
    0.2 0.4 0.2 0.2 0.0

    Mafia probabilities: 1.03 1.9 1.03 1.03 0.0
    Lynch time! Town lynches player 1 with sanity insane

    NIGHT 2

    possible worlds player 2:

    sanities: 0 1 4 2 3
    sanities: 0 1 4 3 2
    sanities: 3 1 4 0 2
    sanities: 3 4 1 0 2
    odds player 2:
    0.5 0.0 0.0 0.5 0.0

    Investigator: 0 Target: 4 Result: false
    Investigator: 2 Target: 2 Result: true
    Investigator: 3 Target: 0 Result: false
    Mafia kills player 4 with sanity paranoid

    DAY 2

    possible worlds player 0:
    sanities: 4 3 0 1 2
    odds player 0:
    0.0 0.0 1.0 0.0 0.0

    possible worlds player 2:
    odds player 2:
    0.0 0.0 0.0 0.0 0.0

    possible worlds player 3:
    sanities: 4 3 0 1 2
    odds player 3:
    0.0 0.0 1.0 0.0 0.0

    Mafia probabilities: 0.0 0.0 2.0 0.0 0.0
    Lynch time! Town lynches player 2 with sanity mafia
    TOWN WINS

    Results

    Using this program the Mafia wins about 18% of the games, which can be seen running MafiaStatistics.jar. We can therefore conclude that this particular variant of Mafia is rather unbalanced in the town's favour. With human agents in real life the Mafia tends to perform significantly better than this, most likely due to the complexity of the reasoning.

    5 Documents

    MafiaOutput.jar executable with output of the game.
    MafiaStatistics.jar executable with statistical output of the game.
    MafiaOutput.zip zip file with the NetBeans project and the java code.
    MafiaProjectProposal.pdf the original project proposal.

    To run the executable:
    go to the right folder in your konsole and type "java -jar documentname.jar".