  In this paper, we study a game called ``Mafia,'' in which different players
have different types of information, communication and functionality. The
players communicate and function in a way that resembles some real-life
situations. We consider two types of operations. First, there are operations
that follow an open democratic discussion. Second, some subgroups of players
who may have different interests make decisions based on their own group
interest. A key ingredient here is that the identity of each subgroup is known
only to the members of that group. In this paper, we are interested in the best
strategies for the different groups in such scenarios and in evaluating their
relative power. The main focus of the paper is the question: How large and
strong should a subgroup be in order to dominate the game? The concrete model
studied here is based on the popular game ``Mafia.'' In this game, there are
three groups of players: Mafia, detectives and ordinary citizens. Initially,
each player is given only his/her own identity, except the mafia, who are given
the identities of all mafia members. At each ``open'' round, a vote is made to
determine which player to eliminate. Additionally, there are collective
decisions made by the mafia where they decide to eliminate a citizen. Finally,
each detective accumulates data on the mafia/citizen status of players. The
citizens win if they eliminate all mafia members. Otherwise, the mafia wins. We
first find a randomized strategy that is optimal in the absence of detectives.
This leads to a stochastic asymptotic analysis where it is shown that the two
groups have comparable probabilities of winning exactly when the total
population size is $R$ and the mafia size is of order $\sqrt{R}$. We then show
that even a single detective changes the qualitative behavior of the game
dramatically. Here, the mafia and citizens have comparable winning
probabilities only for a mafia size linear in $R$. Finally, we provide a
summary of simulations complementing the theoretical results obtained in the
paper.
