On Nash equilibria and calculating EVs

This forum is for discussion related to the game.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14474
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

On Nash equilibria and calculating EVs

Post Post #0 (isolation #0) » Tue Mar 13, 2018 12:59 pm

Post by implosion »

Idk why I'm writing this.

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.
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14474
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #3 (isolation #1) » Tue Mar 13, 2018 2:03 pm

Post by implosion »

1. Does the Nash equilibrium here take into account the possibility of a situation in LyLo where there isn't a cross-vote? For example, A votes B, but B thinks C is actually scum and votes C while pleading with A to change their vote before C shows up. It may turn out that's completely sub-optimal (though I have seen it before) or has no bearing on the equilibrium but it came to mind while I was reading this.
I think anything like this can be reinterpreted as being a scenario where there is a crossvote or quickhammer. If C shows up in the thread, then they can either quickhammer if scum or confirm themself as town and force a crossvote. If b convinces A to unvote, then it's as though A had never voted B in the first place and as though B is voting C or A is voting C, depending on which of them actually votes first, with the other either hammering or waiting for a crossvote.

There is another way to think about it, though, which of course will also give an ultimate answer of 1/3: imagine playing mafia face to face. In lylo, everyone closes their eyes, points at their vote, then opens their eyes. If there's a cycle, people rediscuss things and eventually revote. Otherwise the person with two people voting at them is dead. This is impossible to do in a forum game (unless you were to make some special tool to do it that the mod sanctions) and prevents scum from gaming things by (avoiding) voting first. But they could easily game things if they can predict who each of the other players is going to vote when they open their eyes, so townies would have to somewhat obfuscate their intentions and be willing to change (because if they never change after closing/reopening their eyes a second time after a cycle, scum will just change and win).
2. Does anyone know what the numbers from past games look like w/r/t the first voter in LyLo being scum / town? It would be interesting to see where the site currently stands.
This would actually be really interesting. And probably obtainable at a low sample size with a fair amount of busywork :p
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14474
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #12 (isolation #2) » Wed Mar 14, 2018 12:35 pm

Post by implosion »

In post 11, Ircher wrote:
In post 0, implosion wrote: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.
Pretty sure this is contradictory--the person who voted first is 100% cleared 1/3 of the time followed by you stating to vote the person who voted first 1/3 of the time.
The "Another way of stating this" is referring to the previous two sentences. I.e., the following two statements are equivalent:

"2/3 of the time, act completely randomly; 1/3 of the time, invoke the Sacred Rule and vote for whoever voted second."
"1/3 of the time, vote the person who voted first; 2/3 of the time, vote the person who voted second."
User avatar
implosion
implosion
he/him
Polymath
User avatar
User avatar
implosion
he/him
Polymath
Polymath
Posts: 14474
Joined: September 9, 2010
Pronoun: he/him
Location: zoraster's wine cellar

Post Post #19 (isolation #3) » Tue Apr 10, 2018 2:08 pm

Post by implosion »

In post 17, yessiree wrote:
In post 15, GreyICE wrote:I think more towns would win if they realized that voting for the least scummy player is more likely to be the correct move in 3P LyLo.

If you're alive in 3P LyLo, scum has decided to bring you there. It wasn't a coincidence. I think I've been in like two as town, and one of them was as a replacement.

Unfortunately the sort of people who realize this on self-reflection are not the sort of people who make it to 3P LyLo. Trust me, I've been on the trigger, the thing you're thinking is "who has the self-reflection to ask why GreyICE is alive in 3P LyLo along with their strongest scumread, rather than voting the person who is 'obviously' scum"
I wonder what numbers we get after applying the Nash Equilibrium theorem

lynch the least scummy player 1/3 of the time for optimal town play?
It's hard to apply directly there, because it's all about assumptions where the town is lynching people entirely at random for the whole game with no notion of scumminess. However, you might be able to get something interesting with a lot of really terrible assumptions. For instance, imagine, like, a 7 player game with 1 scum where every player at the start of the game is assigned a ranking for how scummy they are. Every day the town always lynches the scummiest player alive, until LYLO when they use some new strategy possibly. The mafia uses some strategy to determine which player they nightkill, rather than just killing the towniest player. You could probably analyze this to some degree by assuming that the initial scumminess ranking is totally random, or you could see what happens if you bias it so that scum is more likely to look scummier.

But that would be annoying.

Return to “Mafia Discussion”