On Nash equilibria and calculating EVs

[ Originally posted to Mafia Discussion 13/03/2018 by implosion: link ]

The simple formulation: what is an EV?

Here's the simplest possible EV calculation: suppose a game is in 3-player LYLO with no clears, and three vanilla townie claims. What is the probability that the town will win?

Now, the classical answer to this is 1/3. And that's what the EV system is supposed to calculate: the Expected Value of X, where X is a random variable that is 1 in the case that the town wins and 0 in the case where the town loses. But this system makes a critical simplifying assumption: that lynches are random. This is classically a bad assumption, for many reasons:

-Reads. In theory, we'd like to think that our reads are better than random. In practice, this is a difficult thing to actually pin down, since reads are often fluid and have different strengths, etc. -Scum behavior. Scum are probably less likely to vote for their scumbuddies. Alternatively, in certain metas they could even be more likely, if they want to bus for credit. -Kills. Scum will tend to kill people who have more accurate reads, leaving those with worse reads alive, so if peoples' reads are truly random and we don't reconsider them often enough, we'll probably perform worse than random in practice. ...Alternatively, of course, in certain metas, scum might be more likely to kill townies with *bad* reads, for pure wifom value so that they or others can invoke the adage: "But X thought Y, and they got killed!"

All of these effects could have positive or negative impact on the actual percentage of the time that town will win a game. All of these effects combine to form a sort of wibbly wobbly mass of probability that has no clear expected value, hence the lovely simplifying assumption: "All lynches are selected uniformly at random." This lets mountainous setups have very straightforward EV calculations. But an even simpler element is missed by this assumption, simpler than reads, scum behavior or the effect of kills. How does a day actually happen?

Practical matters

Let's go back to our simplest possible example. How does a 3-player LYLO day play out, in practice? Well, eventually, some vote must be made; after this, there is presumably a crossvote as the third player clears themself by not immediately hammering, and the third player then decides between the crossvoters. So, let's examine this a bit more closely. X is one of the townies, and X makes their choice, and confidently declares: Z is scum. X votes for Z. It turns out Z was scum, and now Y must decide between X and Z. Had it turned out that Y was scum, the game would end on the spot as Z hammers. Ergo, in this situation, the probability that the town would win was equal to the probability that both X and then sequentially Y make the correct decisions; thus, the EV for this setup is (1/2) * (1/2) or 1/4 for 3-player LYLO.

Depending on how well you're following the argument, how much you like math, or how much sense I'm making at all in the first place, you might have objections ranging from "But implosion, what about Confounding Factor Q?" to "But 1/4 isn't 1/3!!!". But this is a pretty sensible result. One in four: to win 3-player lylo, the townies both have to be correct! Otherwise, one of them will vote for the other, and the scum will gleefully hammer. The missing factor in the argument is that I assumed a town member made the first vote; if we go back to our lovely world of everything-is-completely-random, then there's a 2/3 chance that this happens and a 1/3 chance that the lone scum will make the first vote, in which case town will win half the time as only the hammerer must actually think about their vote. This gives a total EV of (2/3) * (1/4) + (1/3) * (1/2) which magically comes out to be 1/3 again!

There is, however, an important if subtle lesson in this calculation: you never want to vote first in 3-player lylo, right? Especially as scum. If you vote first as scum, you are, from this perspective, strictly sacrificing a pre-existing 50% chance to win the game outright from having one of the two townies vote the other! So imagine this. Imagine this theoretical world. Scum realize that it's just bad to vote first in 3p lylo, and so they stop doing it. It works! Towns start to lose 3/4 of their 3p lylo scenarios instead of 2/3. But eventually towns start to catch on, and realize: scum are never voting first in 3-player lylo, so the first person to vote in 3p lylo is town! And so they consecrate that rule, and frame it with whatever it is that people frame things with these days, speaking unto the masses: thou shall not vote the first person to vote in 3-player lylo. And suddenly, the town starts winning 50% of their games, instead of the 25% that they were getting before by randomly deciding between people based on their "reads".

But the Cult of Scum figures this out, and retaliates by realizing that under the town's new logic, they will win every single game that they vote first in lylo. And so they do. But they realize a subtlety; if they start voting first 100% of the time, they will play into the town's hands: the town will realize that mafia are always voting first, and will go back to voting randomly, therefore negating any advantage the scum had been gaining by voting first. Worse yet, towns might realize that scum are always voting first, and might counteract this by always voting for whoever votes first! And so scum don't start always voting first; rather, they slowly shift in the direction of voting first more and more often. Meanwhile the towns notice this happening and shift toward autoclearing the first voter less and less often... and this back and forth eventually leads to a Nash equilibrium, a game theoretical concept, which represents the point at which it is not advantageous for either side to budge from their strategy. At this point, it's not advantageous for the town to lynch the first voter more or less frequently than they are, and it's not advantageous for the scum to be the first voter any more or less frequently than they are. Not only this, but if either side were to deviate from their strategy, the other side would be able to easily capitalize.

This Nash equilibrium is unique, which is to be expected for such a zero-sum game. Through mathematical symmetry pure magic, this Nash equilibrium winds up with the town winning 1/3 of the time! What's more, in this equilibrium, the optimal strategy for scum is... vote first exactly 1/3 of the time!!! Both of these are just as we had predicted with our incredibly simplified "everything happens completely at random" assumption. There is one surprising element, however, and that's the town strategy. The optimal town strategy turns out to be: 2/3 of the time, vote completely at random. But 1/3 of the time, invoke the sacred Rule of First Voter Impunity: that whoever votes first is 100% cleared. Another way of stating this is that 1/3 of the time, the hammerer should vote for the person who voted first; but 2/3 of the time, the hammerer should vote for the person who crossvoted.

Making sense

Isn't that odd? Isn't that unintuitive? If I'm holding the hammer in 3-player lylo, you can sure as hell bet that my instinct is telling me to say "to hell with this!" and vote for whoever I think is scummier. But it doesn't need to be so cut and dry. This gives us actual actionable advice that we can use in mafia games! The advice can be stated a bit more precisely, but at its core it boils down to this: if you are hammering between two players in 3-player LYLO, you should bias yourself toward assuming that whoever voted first is more likely to be town. In a metagame where towns refuse to do this slight biasing, it turns out, savvy mafia will win 3-player lylo 3/4 of the time by simply refusing to vote first. Of course there's all of the nuance of how good their reads are, what's been said and done in the game so far, and so on, but from a probabilistic standpoint, it is 3/4.

This idea of a nash equilibrium can be applied to a lot of other ideas in mafia, as well. I actually alluded to two of them above. One is the probability with which scum busses, vs the probability with which town will avoid lynching someone who was on a scum wagon. Another is the probability with which scum will kill a townie with "good reads" (whatever that means, and assuming that at least SOME townie has good reads) vs the probability that the town will put a lot of stock into the reads of players that have been nightkilled.

But my intent here is just to show that there is a lot of subtlety that goes into the math behind something like EV calculation, and that subtlety is worth considering, and IMO it's pretty neat how things here magically work out to 1/3.