3
$\begingroup$

This question was closed due to lack of own effort shown. Because I like the game of werewolf (a.k.a. Mafia) and thought it was a nice idea to pose a simplified version of it as a game-theoretic problem, I'm posting the question (rephrased) and answering it (which I think should count as sufficient own effort shown :-).

There are two werewolves and two townsfolk. The werewolves know who everyone else is, but the townsfolk only know their own identity. A voting order is uniformly randomly determined and announced, and then each player votes against one of the other three players, in the determined order and for everyone to hear. The townsfolk win if at least one of the players with the most votes is a werewolf; otherwise the werewolves win.

The other question wasn't specific about coordination of strategies. I found the problem interesting when I assumed that the strategies can be fully coordinated, so that's what I'm going to assume here, but feel free to also comment on solutions for the case where either or both teams don't know their teammate's strategy.

So let's assume that there's a reliable town magazine, known not to be infiltrated by werewolves, and the very smart editors have worked out the very best strategy to adopt when faced with this predicament, and published it. So though the townspeople don't know their identities, they know that whoever is on their team is playing according to the published strategy. The werewolves, of course, don't need a magazine; they just sneak off at night to secretly strategize. But they can read, so they know the townspeoples' strategy. (I believe the result doesn't depend on whether the townspeople know the werewolves' strategy, but for definiteness, you can assume that they don't.)

What is the probability for the townspeople to win, assuming optimal play of both teams?

$\endgroup$
0
$\begingroup$

I'll first prove that the probability can't be greater than $2/3$, then exhibit a strategy for the townspeople to attain $2/3$.

The werewolves can mimick what the townspeople would have done in their place. This precludes the townspeople from gaining any information from the voting. Thus, for obtaining an upper bound we can assume that the first three votes are fixed beforehand by the townpeople's strategy (mimicked by the werewolves).

If the first three votes all go against the same (namely the last) player, that player gets the most votes and is a townsperson with probability $1/2$, so in this case the winning probability is $1/2$.

If the first three votes are divided among three players, at least two of those are not the last player. Then the probability that the last player is a werewolf, and hence at least one of those other two is a townsperson, and the werewolf can cast a second vote against her, is again $1/2$.

If the first three votes are one against one player and two against another, then the probability that the player with two votes is a townsperson and that the last player is a werewolf who can vote for someone else is $1/3$, so in this case the winning probability is at most $2/3$.

That establishes the upper bound; now to the strategy that attains it.

If a werewolf goes first, it has to mimick what a townsperson would have done; otherwise the townspeople will both vote against it and win. So by voting against the second player on the first vote, the townspeople can ensure that the first vote goes against the second player.

Now if a werewolf goes second, it again has to mimick what a townsperson would have done; otherwise the at least one townsperson left to vote will cast a second vote against it. So the townspeople can also determine the second vote.

If the first vote is cast against the second player and the second vote against the first, that leaves the following possibilities: If the townspeople went first, they lose. If the werewolves went first, they lose (because the remaining two townspeople can't both vote against the same townsperson). Otherwise, the first two voters were a werewolf and a townsperson, and they now both have one vote on their heads, with one werewolf and one townsperson left to vote.

If the werewolf goes third, if it votes against the townsperson going last, the townsperson returns the favour, and the townspeople win; whereas if it votes against one of the first two, the townsperson votes against the other, and again the townspeople win.

If the townsperson goes third, she has a $1/2$ chance to cast a second vote against the werewolf among the first two. In total, that yields a chance of $\frac16+\frac12\cdot\frac13=\frac13$ of the townspeople losing, and we saw above that this is optimal.

$\endgroup$
  • $\begingroup$ I don't understand. If the werewolves each know who everyone is, the first werewolf to vote can vote for a townie, and the other werewolf will know this and can vote for the same townie,making it impossible for the tonies to win.Also.does a voter know who voted for whom among voters preceding him, odoes he know just the vote totals up to that point? $\endgroup$ – DanielWainfleet Aug 2 '15 at 22:55
  • $\begingroup$ @user254665: "The townsfolk win if at least one of the players with the most votes is a werewolf; otherwise the werewolves win." So both werewolves voting for the same townsperson doesn't make it impossible for the townspeople to win. About your second question: Yes, they know who voted for whom; I'll add that to the question; thanks for asking. $\endgroup$ – joriki Aug 2 '15 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.