Skip to main content
Theoretical Computer Science

Return to Question

Tweeted twitter.com/#!/StackCSTheory/status/201269271274328065
added 55 characters in body
Source Link
Syzygy
Syzygy
  • 291
  • 1
  • 5

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.

Basically, it works as follows:

  • At the beginning, each of the $N$ players is secretly assigned a role, either aligned with the Mafia or with the Town. Each role may have special abilities; more about that later.

  • There are two game phases: Day and Night. At Night, the Mafia can communicate secretly with each other; and they may agree upon one target player who they murder that night. At Day, all (alive) players communicate in an open forum. The players may agree to lynch one player, an absolute majority of all players is needed.

  • The game ends if there is only the Mafia left, or there is only the Town left. The surviving party wins.

  • Let's assume that there are three roles: Citizen, Investigator, and Mafioso. Citizens have no powers. Mafiosi also have no abilities beyond being able to communicate with each other at night and voting for one murder victim each night. Investigators can investigate one other player in each night, finding out their exact role.

  • Assume the game starts at day, and that the role of a player is revealed upon death

Winning strategies

Given a setup $(i,c,m)$ of $i$ Investigators, $c$ Citizen, and $m$ Mafiosi, we say that the setup is winning for Town, if there is a strategy for the Town players, such that they win, no matter how the Mafia plays.

Note that we can assume that the Mafia plays with full information, since we want to account for any decision they can make.

Example: The setup $(4,1,1)$ wins for Town.

Day 1: All Town players truthfully report their role in the open chat. The Mafia player has to claim to be either Investigator or Citizen.

If he claims Citizen, then the Mafioso is one of the two alleged Citizens. Each Investigator can investigate either one, and will find out the true one. At most one Investigator can die in the night, and the other two simply hang the Mafioso.

Hence, the Mafioso must claim Investigator. There are 5 alleged Invesigators. In the open chat, the Investigators agree upon a permutation to check each other.

Night 1: The Investigators check their targets, and the Mafioso kills one.

Day 2: There are 3 Investigators left. All alleged Investigators report their findings. No matter who was killed, at least one of them is also confirmed by another alive Investigator. Since the Mafioso claimed Investigator, he also needs to say if his assigned target was Mafia or not. If he frames someone, then the Town knows that either he, or the framed one is Mafia, against the other confirmed 3 Town. If he does not frame anybody, there will also be 3 confirmed Town. Either way, not hanging anyone, and investigating the only 2 left suspects wins for Town.

Questions

  • How hard is it to decide whether a given setup admits a winning strategy for Town? Intuitively, this sounds like a $PSPACE$-complete problem. Can anybody come up with a reduction?
  • Can we find minimal winning setups? As in can we minimize the ratios $i:m$ or $(i+c):m$?

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.

Basically, it works as follows:

  • At the beginning, each of the $N$ players is secretly assigned a role, either aligned with the Mafia or with the Town. Each role may have special abilities; more about that later.

  • There are two game phases: Day and Night. At Night, the Mafia can communicate secretly with each other; and they may agree upon one target player who they murder that night. At Day, all (alive) players communicate in an open forum. The players may agree to lynch one player, an absolute majority of all players is needed.

  • The game ends if there is only the Mafia left, or there is only the Town left. The surviving party wins.

  • Let's assume that there are three roles: Citizen, Investigator, and Mafioso. Citizens have no powers. Mafiosi also have no abilities beyond being able to communicate with each other at night and voting for one murder victim each night. Investigators can investigate one other player in each night, finding out their exact role.

  • Assume the game starts at day

Winning strategies

Given a setup $(i,c,m)$ of $i$ Investigators, $c$ Citizen, and $m$ Mafiosi, we say that the setup is winning for Town, if there is a strategy for the Town players, such that they win, no matter how the Mafia plays.

Note that we can assume that the Mafia plays with full information, since we want to account for any decision they can make.

Example: The setup $(4,1,1)$ wins for Town.

Day 1: All Town players truthfully report their role in the open chat. The Mafia player has to claim to be either Investigator or Citizen.

If he claims Citizen, then the Mafioso is one of the two alleged Citizens. Each Investigator can investigate either one, and will find out the true one. At most one Investigator can die in the night, and the other two simply hang the Mafioso.

Hence, the Mafioso must claim Investigator. There are 5 alleged Invesigators. In the open chat, the Investigators agree upon a permutation to check each other.

Night 1: The Investigators check their targets, and the Mafioso kills one.

Day 2: There are 3 Investigators left. All alleged Investigators report their findings. No matter who was killed, at least one of them is also confirmed by another alive Investigator. Since the Mafioso claimed Investigator, he also needs to say if his assigned target was Mafia or not. If he frames someone, then the Town knows that either he, or the framed one is Mafia, against the other confirmed 3 Town. If he does not frame anybody, there will also be 3 confirmed Town. Either way, not hanging anyone, and investigating the only 2 left suspects wins for Town.

Questions

  • How hard is it to decide whether a given setup admits a winning strategy for Town? Intuitively, this sounds like a $PSPACE$-complete problem. Can anybody come up with a reduction?
  • Can we find minimal winning setups? As in can we minimize the ratios $i:m$ or $(i+c):m$?

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.

Basically, it works as follows:

  • At the beginning, each of the $N$ players is secretly assigned a role, either aligned with the Mafia or with the Town. Each role may have special abilities; more about that later.

  • There are two game phases: Day and Night. At Night, the Mafia can communicate secretly with each other; and they may agree upon one target player who they murder that night. At Day, all (alive) players communicate in an open forum. The players may agree to lynch one player, an absolute majority of all players is needed.

  • The game ends if there is only the Mafia left, or there is only the Town left. The surviving party wins.

  • Let's assume that there are three roles: Citizen, Investigator, and Mafioso. Citizens have no powers. Mafiosi also have no abilities beyond being able to communicate with each other at night and voting for one murder victim each night. Investigators can investigate one other player in each night, finding out their exact role.

  • Assume the game starts at day, and that the role of a player is revealed upon death

Winning strategies

Given a setup $(i,c,m)$ of $i$ Investigators, $c$ Citizen, and $m$ Mafiosi, we say that the setup is winning for Town, if there is a strategy for the Town players, such that they win, no matter how the Mafia plays.

Note that we can assume that the Mafia plays with full information, since we want to account for any decision they can make.

Example: The setup $(4,1,1)$ wins for Town.

Day 1: All Town players truthfully report their role in the open chat. The Mafia player has to claim to be either Investigator or Citizen.

If he claims Citizen, then the Mafioso is one of the two alleged Citizens. Each Investigator can investigate either one, and will find out the true one. At most one Investigator can die in the night, and the other two simply hang the Mafioso.

Hence, the Mafioso must claim Investigator. There are 5 alleged Invesigators. In the open chat, the Investigators agree upon a permutation to check each other.

Night 1: The Investigators check their targets, and the Mafioso kills one.

Day 2: There are 3 Investigators left. All alleged Investigators report their findings. No matter who was killed, at least one of them is also confirmed by another alive Investigator. Since the Mafioso claimed Investigator, he also needs to say if his assigned target was Mafia or not. If he frames someone, then the Town knows that either he, or the framed one is Mafia, against the other confirmed 3 Town. If he does not frame anybody, there will also be 3 confirmed Town. Either way, not hanging anyone, and investigating the only 2 left suspects wins for Town.

Questions

  • How hard is it to decide whether a given setup admits a winning strategy for Town? Intuitively, this sounds like a $PSPACE$-complete problem. Can anybody come up with a reduction?
  • Can we find minimal winning setups? As in can we minimize the ratios $i:m$ or $(i+c):m$?
Source Link
Syzygy
Syzygy
  • 291
  • 1
  • 5

How hard is Mafia?

Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.

Basically, it works as follows:

  • At the beginning, each of the $N$ players is secretly assigned a role, either aligned with the Mafia or with the Town. Each role may have special abilities; more about that later.

  • There are two game phases: Day and Night. At Night, the Mafia can communicate secretly with each other; and they may agree upon one target player who they murder that night. At Day, all (alive) players communicate in an open forum. The players may agree to lynch one player, an absolute majority of all players is needed.

  • The game ends if there is only the Mafia left, or there is only the Town left. The surviving party wins.

  • Let's assume that there are three roles: Citizen, Investigator, and Mafioso. Citizens have no powers. Mafiosi also have no abilities beyond being able to communicate with each other at night and voting for one murder victim each night. Investigators can investigate one other player in each night, finding out their exact role.

  • Assume the game starts at day

Winning strategies

Given a setup $(i,c,m)$ of $i$ Investigators, $c$ Citizen, and $m$ Mafiosi, we say that the setup is winning for Town, if there is a strategy for the Town players, such that they win, no matter how the Mafia plays.

Note that we can assume that the Mafia plays with full information, since we want to account for any decision they can make.

Example: The setup $(4,1,1)$ wins for Town.

Day 1: All Town players truthfully report their role in the open chat. The Mafia player has to claim to be either Investigator or Citizen.

If he claims Citizen, then the Mafioso is one of the two alleged Citizens. Each Investigator can investigate either one, and will find out the true one. At most one Investigator can die in the night, and the other two simply hang the Mafioso.

Hence, the Mafioso must claim Investigator. There are 5 alleged Invesigators. In the open chat, the Investigators agree upon a permutation to check each other.

Night 1: The Investigators check their targets, and the Mafioso kills one.

Day 2: There are 3 Investigators left. All alleged Investigators report their findings. No matter who was killed, at least one of them is also confirmed by another alive Investigator. Since the Mafioso claimed Investigator, he also needs to say if his assigned target was Mafia or not. If he frames someone, then the Town knows that either he, or the framed one is Mafia, against the other confirmed 3 Town. If he does not frame anybody, there will also be 3 confirmed Town. Either way, not hanging anyone, and investigating the only 2 left suspects wins for Town.

Questions

  • How hard is it to decide whether a given setup admits a winning strategy for Town? Intuitively, this sounds like a $PSPACE$-complete problem. Can anybody come up with a reduction?
  • Can we find minimal winning setups? As in can we minimize the ratios $i:m$ or $(i+c):m$?