  In this paper, we study the class of games known as hidden-role games in
which players are assigned privately to teams and are faced with the challenge
of recognizing and cooperating with teammates. This model includes both popular
recreational games such as the Mafia/Werewolf family and The Resistance
(Avalon) and many real-world settings, such as distributed systems where nodes
need to work together to accomplish a goal in the face of possible corruptions.
There has been little to no formal mathematical grounding of such settings in
the literature, and it was previously not even clear what the right solution
concepts (notions of equilibria) should be. A suitable notion of equilibrium
should take into account the communication channels available to the players
(e.g., can they communicate? Can they communicate in private?). Defining such
suitable notions turns out to be a nontrivial task with several surprising
consequences. In this paper, we provide the first rigorous definition of
equilibrium for hidden-role games, which overcomes serious limitations of other
solution concepts not designed for hidden-role games. We then show that in
certain cases, including the above recreational games, optimal equilibria can
be computed efficiently. In most other cases, we show that computing an optimal
equilibrium is at least NP-hard or coNP-hard. Lastly, we experimentally
validate our approach by computing exact equilibria for complete 5- and
6-player Avalon instances whose size in terms of number of information sets is
larger than $10^{56}$.
