[EV] Unequal probabilities for being scum

This forum is for discussion of individual Open Setups, including theoretical balance.
User avatar
BNL
BNL
Micro Madness
User avatar
User avatar
BNL
Micro Madness
Micro Madness
Posts: 3338
Joined: September 15, 2015
Location: EDT+12

[EV] Unequal probabilities for being scum

Post Post #0 (ISO) » Mon Oct 29, 2018 4:45 pm

Post by BNL »

1 Mafia, 3 Town, Night Start, compulsive kill.

Except, the four people who are playing this have different preferences for being scum, and hence as an internal rule, are playing such that the probabilities for A, B, C and D being scum are 10%, 20%, 30% and 40% respectively. (This can be simulated by having 1 Mafia and 9 Town cards, shuffling them randomly, and giving A, B, C and D 1, 2, 3 and 4 cards respectively, dictating whoever gets the Mafia card is the Mafia Goon)

1. With what probability distribution should each player, if scum, kill each other player?

2. How should the players act in LyLo?

3. a) What is the town EV?
b) What is the probability for each player winning?
GTKAS - BNL

Busy, on indefinite V/LA. May return April 2020
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #1 (ISO) » Tue Oct 30, 2018 4:54 pm

Post by callforjudgement »

This problem is one of those that's complex enough to be hard to solve for a human, but small enough to be easy to entirely solve out for a computer.

1. According to the computer analysis I ran, scum's optimal strategy is:
  • If you're A: always nightkill C
  • If you're B: nightkill A or C, with equal probability
  • If you're C: nightkill A ⅓ of the time, B ⅔ of the time
  • If you're D: nightkill B half the time, otherwise randomize between A and C
2. If scum follow this strategy, town can't do any better than to lynch the player who's most likely to have rolled scum (i.e. D if they're alive, otherwise C). This is equivalent to always lynching D, because scum will never kill D.

3. a) With these strategies, town will gain a 40% chance to win (the chance that D rolled scum; note that D will
always
be alive if scum follow the strategy).
b) D will always lose; thus players A, B, and C have a 60% chance to win, and D has no chance to win.


The scum strategy is pretty strange and complex, so I'm curious as to why it works. (EDIT: I tried out some other tools within Gambit; it seems that the details of the scum strategy aren't too important, scum just have to make sure that D is never nightkilled and that the kill never gives town enough information to make the actual scum more likely to be scum than D is.)

Here's the file I used (this can be read by the program Gambit):

Code: Select all

<?xml version="1.0" encoding="UTF-8"?>
<gambit:document xmlns:gambit="http://gambit.sourceforge.net/" version="0.1">
<colors>
<player id="-1" red="0" green="0" blue="0" />
<player id="0" red="154" green="205" blue="50" />
<player id="1" red="255" green="0" blue="0" />
<player id="2" red="0" green="0" blue="255" />
</colors>
<font size="10" family="74" face="Sans" style="90" weight="92" />
<autolayout>
<nodes size="10" spacing="50" chance="dot" player="dot" terminal="dot"/>
<branches size="60" tine="20" branch="forktine" labels="horizontal"/>
<infosets connect="all" style="circles"/>
</autolayout>
<labels abovenode="label" belownode="isetid" abovebranch="label" belowbranch="probs" />
<numbers decimals="4"/>
<game>
<efgfile>
EFG 2 R "Untitled Extensive Game" { "Mafia" "Town" }
""

c "" 1 "" { "A" 0.1 "B" 0.2 "C" 0.3 "D" 0.4 } 0
p "" 1 1 "" { "B" "C" "D" } 0
p "" 2 1 "B" { "A" "C" "D" } 0
t "" 1 "" { 0, 1 }
t "" 2 "" { 1, 0 }
t "" 3 "" { 1, 0 }
p "" 2 2 "C" { "A" "B" "D" } 0
t "" 10 "" { 0, 1 }
t "" 11 "" { 1, 0 }
t "" 12 "" { 1, 0 }
p "" 2 3 "D" { "A" "B" "C" } 0
t "" 19 "" { 0, 1 }
t "" 20 "" { 1, 0 }
t "" 21 "" { 1, 0 }
p "" 1 2 "" { "A" "C" "D" } 0
p "" 2 4 "A" { "B" "C" "D" } 0
t "" 28 "" { 0, 1 }
t "" 29 "" { 1, 0 }
t "" 30 "" { 1, 0 }
p "" 2 2 "C" { "A" "B" "D" } 0
t "" 13 "" { 1, 0 }
t "" 14 "" { 0, 1 }
t "" 15 "" { 1, 0 }
p "" 2 3 "D" { "A" "B" "C" } 0
t "" 22 "" { 1, 0 }
t "" 23 "" { 0, 1 }
t "" 24 "" { 1, 0 }
p "" 1 3 "" { "A" "B" "D" } 0
p "" 2 4 "A" { "B" "C" "D" } 0
t "" 31 "" { 1, 0 }
t "" 32 "" { 0, 1 }
t "" 33 "" { 1, 0 }
p "" 2 1 "B" { "A" "C" "D" } 0
t "" 4 "" { 1, 0 }
t "" 5 "" { 0, 1 }
t "" 6 "" { 1, 0 }
p "" 2 3 "D" { "A" "B" "C" } 0
t "" 25 "" { 1, 0 }
t "" 26 "" { 1, 0 }
t "" 27 "" { 0, 1 }
p "" 1 4 "" { "A" "B" "C" } 0
p "" 2 4 "A" { "B" "C" "D" } 0
t "" 34 "" { 1, 0 }
t "" 35 "" { 1, 0 }
t "" 36 "" { 0, 1 }
p "" 2 1 "B" { "A" "C" "D" } 0
t "" 7 "" { 1, 0 }
t "" 8 "" { 1, 0 }
t "" 9 "" { 0, 1 }
p "" 2 2 "C" { "A" "B" "D" } 0
t "" 16 "" { 1, 0 }
t "" 17 "" { 1, 0 }
t "" 18 "" { 0, 1 }
</efgfile>
<analysis type="list">
<description>
Some equilibria by solving a linear complementarity program in extensive game
</description>
<profile type="behav">
0,1,0,1/2,1/2,0,1/3,2/3,0,1/4,1/2,1/4,0,0,1,0,0,1,0,0,1,0,0,1
</profile>
</analysis>
</game>
</gambit:document>

The output of the analysis appears to have ended up in the file too (so if you want to verify these results for yourself, you might want to delete that bit).
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #2 (ISO) » Tue Oct 30, 2018 6:22 pm

Post by callforjudgement »

After more computer experimentation, the "correct" probabilities for a setup of this nature appear to be 3/18, 4/18, 5/18, 6/18 (i.e. 1/6, 2/9, 5/18, 1/3).

Scum now have exactly one optimal strategy, which is to assign the probabilities to nightkill player A, B, or C in the ratio 3:2:1 (thus, e.g., if scum is player B, the kill is 3/4 on A and 1/4 on C, as they won't kill themself). Regardless of the N1 kill, each of the remaining three possibilities for scum is then equally likely going into Day, meaning that town's strategy doesn't matter; they have a 1/3 EV whatever they do.

The reason this is interesting is that scum can't possibly get better than a 1/3 EV because town could use the universal strategy of "always lynch player D" (which in turn means that scum can't ever nightkill player D, because a strategy that could so would allow town's EV to improve above 1/3; lynch player D whenever they're alive, randomize otherwise). So the setup's at a point where any adjustment from the odds in one direction will make lynching player D always correct, and any adjustment in the other direction means that scum will always be able to create a symmetrical situation going into day 1; it's a crossing point between two degenerate forms of the setup. (This also means that player D isn't necessarily screwed, like they would be in the original version of the setup; town's dayplay will presumably be based on scumhunting, and scum have a chance to WIFOM them via tinkering with the probabilities.)
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #3 (ISO) » Wed Oct 31, 2018 2:20 am

Post by yessiree »

In post 0, BNL wrote:3. a) What is the town EV?
town ev should still be the expected value of randomly lynching just with unequal probabilities of each player being scum

ie. EV = sum_over_all_players( P(win|player=scum) * P(player=scum) )
You can see why this makes sense because in a normal scenario (equal probabilities)
P(player=scum) is 1/4 for every player
P(win|player=scum) is just the probability of random lynching in 3p given the night start, 1/3
P(win|player=scum) * P(player=scum) = 1/3 * 1/4 = 1/12
sum_over_all_players( P(win|player=scum) * P(player=scum) ) = 1/12 * 4 = 1/3

so EV of 4p with night start = EV of 3p, which is what we expect

Now for unequal probability, the only difference is that P(player=scum) is different for each player
P(win|A=scum) * P(A=scum) = P(lynching A in 3p) * P(A=scum) = 1/3 * 1/10 = 1/30
B: = 1/3 * 1/5 = 1/15
C: = 1/3 * 1/3 = 1/9
D: = 1/3 * 2/5 = 2/15

EV ~= 34.44%

which is slightly higher than the normal scenario
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #4 (ISO) » Wed Oct 31, 2018 4:03 am

Post by callforjudgement »

No, town EV assume that town breaks the setup as well as possible but has no reads.

In the original 10%/20%/30%/40% setup, always lynching player D gives a win rate of 40%, and there's nothing scum can do to affect that. Meanwhile, any other strategy gives a worse win rate. So the EV is 40%.

Your calculation, with town using the inferior strategy of random lynching (thus not correctly breaking the setup), should give an EV of 33⅓%, just as in the balanced-scum-probabilities version. The only reason it doesn't is that you counted the probabilities of the various players being scum as 10%+20%+33⅓%+40%, which is more than 100%.
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #5 (ISO) » Wed Oct 31, 2018 5:18 am

Post by yessiree »

ah yes thanks for spotting my mistake, i somehow thought 30% = 1/3 :facepalm: :facepalm: :facepalm:

at any rate, isn't it generally bad practice to not assume every action is taken at random?
in this case it is true town's optimal strategy is to always lynch D if D is alive, thus a 40% EV
however, wouldn't scum always kill D to remove town's 40% win rate?
now town's best strategy is to always lynch C which is 30% which is now worse than lynching at random

i dunno
Sukima
Sukima
Watcher
Sukima
Watcher
Watcher
Posts: 0
Joined: October 2, 2014

Post Post #6 (ISO) » Wed Oct 31, 2018 10:33 am

Post by Sukima »

I don't think that's right either... You're forgetting about the 40% scenario that D cannot be NK'd. If D is alive, you lynch it for the 40%, but if you NK'd D (IE D is most definitely not scum), then lynching C gives you 50% winrate of the 60% remaining, which is much better than the 0% that happens when you shoot anywhere else and D gets lynched for a loss.
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #7 (ISO) » Wed Oct 31, 2018 6:25 pm

Post by yessiree »

Your phrasing is confusing
Is this what you are trying to say?
Town has a 0% winrate if D != scum because the optimal strategy is to always lynch D no matter what => 60% of the time town EV is 0.
Town has a 100% winrate if D = scum for the same reasoning => 40% of the time town EV is 1
so the final EV is 60% * 0 + 40% * 1 = 40%
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #8 (ISO) » Wed Oct 31, 2018 6:55 pm

Post by yessiree »

I dont think this is correct, because the probability of each player being scum is
not conditionally independent
.
ie. Always lynching D does not give town a 40% EV, because someone else must have died the night before, and thus is proven not scum, so you have to calculate the conditional probability of D = scum with this new information

ie. if A is killed, then the conditional probability of D being scum given A is not scum
=> P(D=scum|A!=scum)
= P(A!=scum|D=scum) * P(D=scum) / P(A!=scum) by Bayes theorem, and if D=scum then A is guaranteed not scum so P(A!=scum|D=scum) = 1
= 1 * 40% / (1 - 10%)
= 4/9 ~= 44.44%
Sukima
Sukima
Watcher
Sukima
Watcher
Watcher
Posts: 0
Joined: October 2, 2014

Post Post #9 (ISO) » Thu Nov 01, 2018 6:58 am

Post by Sukima »

The thing that you're missing is that even when disregarding the information the kill gives, always lynching D is 40% because D has 40% of being scum. The NK strat above is attempting to minimize the amount of information that A B or C as mafia gives. Basically, if you killed D any % of the time that isn't 0, the information you get from the kill goes up, namely that D is not scum.
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #10 (ISO) » Thu Nov 01, 2018 7:11 am

Post by callforjudgement »

If town decides at the start of the game to always lynch D, without even looking at who died overnight, they have a 40% chance of winning, because that's the chance that D is scum. Note that in the event that scum kill D, town will end up trying to lynch D anyway, and even if you count that as an automatic town loss, town
still
win 40% of the time.

It cannot possibly be correct for scum to kill D any percentage of the time, because if they did, town would have a strategy that has more than a 40% chance of winning: lynching D if they're still alive, and randomizing a lynch if D is dead.

Incidentally, the Bayes' theorem result doesn't work because you can't gain any information from who dies N1 except that the dead player isn't scum; the reason is that the kill is scum-directed, and they can choose an NK strategy to screw with your statistics. (That's what's up with the NK plans found by Gambit: they're designed so that the scum nightkill gives no useful information beyond the fact that the dead player is town.) In particular, because D is the most likely player to be scum in the priors, the kill is designed to increase the probability that A/B/C are scum, but not by enough to make it any more likely that one of those players is scum, than that D is scum. So what you need to check is not the probability that D is scum given that A isn't scum, but the probability that D is scum given that A was nightkilled, and that depends on the scum strategy. (The scum strategy also depends on the town strategy, which is why I used a computer to find the strategies rather than trying to work it out myself; the problem's too complex for humans to solve the whole thing from scratch, but simple enough for computers to be able to brute-force it.)
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
Awoo
Awoo
Mafia Scum
User avatar
User avatar
Awoo
Mafia Scum
Mafia Scum
Posts: 1096
Joined: September 1, 2017
Location: lmao city

Post Post #11 (ISO) » Thu Nov 01, 2018 7:40 am

Post by Awoo »

I really like it when problems are in the sweet spot where they would normally be just outside our reach but we are able to reach them using computers :)
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #12 (ISO) » Thu Nov 01, 2018 6:05 pm

Post by yessiree »

In post 10, callforjudgement wrote:Incidentally, the Bayes' theorem result doesn't work because you can't gain any information from who dies N1 except that the dead player isn't scum
"dead player isn't scum" IS new information
Like i said before, the probability of each player being scum is NOT conditionally independent - the probability distribution being scum for ABCD is a
normal probability distribution
because they add up to 1
eg. If I revealed that player B is scum. Players A,C,D now have a 0% probability of being scum. They do NOT still have 10%, 30%, and 40% probabilities respectively.
Similarly If I revealed that player B is town. The rest of the probabilities also CHANGES accordingly.

Whoever dies on night 1 WILL have an effect on the probability distribution of being mafia on the remaining players
If you lynch D when ALL 4 players are alive then yes you have a 40% chance of catching scum.
However, if I now tell you that A is not scum. Lynching D does not give you a 40% of catching scum anymore. You must calculate the posterior probability with your prior knowledge (40%), and new evidence (A is not scum)
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #13 (ISO) » Thu Nov 01, 2018 6:08 pm

Post by yessiree »

seriously guys please read up on the Monty Hall Problem
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #14 (ISO) » Fri Nov 02, 2018 1:52 am

Post by callforjudgement »

The Monty Hall problem is relevant here, but maybe not for the reason you think: it talks about how it's relevant who chose the information to reveal, and what they knew.

The prior probabilities of A, B, C, D being scum are 10%, 20%, 30%, 40% respectively.

Now, suppose scum are using the strategy found by computer, and player A is the nightkill. That kill had a 50% chance of being made if B were scum, 33⅓% if C were scum, 25% if D were scum, i.e. a 30% probability overall. So the conditional probabilities now are:

- A as scum: 0%
- B as scum: P(B=scum|A killed) = P(A killed|B=scum) × P(B=scum) ÷ P(A killed) = 50% × 20% ÷ 30% = 33⅓%
- C as scum: P(C=scum|A killed) = P(A killed|C=scum) × P(C=scum) ÷ P(A killed) = 33⅓ × 30% ÷ 30% = 33⅓%
- D as scum: P(D=scum|A killed) = P(A killed|D=scum) × P(D=scum) ÷ P(A killed) = 25% × 40% ÷ 30% = 33⅓%

The scum strategy has made it so that the kill doesn't give you any information about who's scum (which is presumably the reason why Gambit chose that strategy in the first place).

Likewise, suppose B is the nightkill. That kill would only be made by C or D as scum; C would make it ⅔ of the time, D half the time, so 40% probability overall. That gives us these probabilities:

- A as scum: 0%
- B as scum: 0%
- C as scum: P(C=scum|B killed) = P(B killed|C=scum) × P(C=scum) ÷ P(B killed) = 66⅔% × 30% ÷ 40% = 50%
- D as scum: P(D=scum|B killed) = P(B killed|D=scum) × P(D=scum) ÷ P(B killed) = 50% × 40% ÷ 40% = 50%

OK, so you know that neither A nor B is scum, but C and D are equally attractive kill options.

Finally, suppose C is the nightkill (scum never kill D). A would always make that kill, B would make that kill half the time, D one quarter of the time, so the kill has a 30% chance of being made. Now the probabilities look like this:

- A as scum: P(A=scum|C killed) = P(C killed|A=scum) × P(A=scum) ÷ P(C killed) = 100% × 10% ÷ 30% = 33⅓%
- B as scum: P(B=scum|C killed) = P(C killed|B=scum) × P(B=scum) ÷ P(C killed) = 50% × 20% ÷ 30% = 33⅓%
- C as scum: 0%
- D as scum: P(D=scum|C killed) = P(C killed|D=scum) × P(D=scum) ÷ P(C killed) = 25% × 40% ÷ 30% = 33⅓%

Again, you have three possible scum, and they're all equally likely to be scum.

So what's town's EV here? It's clear that no town strategy (other than avoiding the impossible scum if there is one) can have any influence on town win rate, because scum have made the situation symmetrical between two or three players in each case. There's a 60% chance that town have an equal choice between three lynches (EV in this case is 33⅓%), and a 40% chance that town have an equal choice between two lynches (EV in this case is 50%). So town's overall EV is (60%×33½%)+(40%×50%)=20%+20%=40%.

We can trivially check this by observing that for any given scum kill, with this scum strategy, lynching player D is at least as good as lynching any other player, thus the EV should come out the same as the "always lynch player D" strategy, i.e. 40%. What the scum strategy has done, therefore, is to make it so that the kill gives town no extra information that's helpful in selecting their kill; the information's used entirely to make A/B/C more competitive lynches over D, but never to make A, B, or C look like a
better
lynch than D. Scum's influence over the kill means that, despite the fact that the kill must give town information, they can choose what information is given and can ensure it isn't useful. So town are held to their minimum possible win rate of 40%.

In situations where the initial probabilities were more equal (e.g. if all the players were equally likely to be scum), there'd be no strategy that avoided giving town useful information, and thus the kill genuinely would increase town EV. (Compare 3:1 vanilla going into night, or the original Monty Hall problem which is effectively 2:1 with a dead townie choosing the lynches, and another dead townie publicly protecting someone overnight. Those cases are each symmetrical enough that when scum kill someone, the other players become more likely to be scum by enough that town gets a notable advantage.)
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #15 (ISO) » Fri Nov 02, 2018 6:10 pm

Post by yessiree »

Your assumption of mafia choosing random target to kill does not hold. Mafia will always choose to kill A to minimize the town ev in the resulting 3p because it will provide the least gain of the conditional probability of lynching D, or, if mafia happened to be A, then he will always target B.

Secondly, to make sure we are on the same page, lets consider a simple mental exercise where everyone has equal probability of being scum, then we know the following to be true:
EV of a 4p is 25%
EV of a 3p is 1/3
EV of a 4p with night start? It is the same EV as 3p
=> 1/3
Note it is not 25% which would the highest probability of someone being mafia in the original 4p, but rather the highest conditional probability of someone being mafia in a 4p given 1 of the 4 people is revealed to not be mafia.
Since everyone has equal probability
P(one player = scum|another player != scum)
Applying Bayes rule
= 1 * 25% / (1 - 25%)
= 1/3

Following the same principle, we can clearly see in our case the EV should not be the highest probability in the original distribution
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #16 (ISO) » Sat Nov 03, 2018 5:20 am

Post by callforjudgement »

No, Mafia will
not
always choose to kill A. Doing so would raise town's win probability above 40%: they could lynch D if A was nightkilled, or A if B was nightkilled, for a 50% win rate, if they knew what the scum strategy was.

EV isn't necessarily going to equal the highest probability in the input distribution; however, it will
if
scum can make a kill that doesn't give away useful information. Killing purely at random does give away information (especially if you kill D), as does killing player A uncondtionally. However, if the distribution of scum is sufficiently unbalanced, it's possible to choose a probability distribution of kills such that town don't gain any useful information as a result of the kill; in that case, town can't do any better than to lynch the most likely scum.

25%, 25%, 25%, 25% is sufficiently balanced that scum have no kill that doesn't give away information. 10%, 20%, 30%, 40% is sufficiently unbalanced that scum
do
have such a strategy (e.g. the "A nightkills C, B randomizes between A and C, C nightkills B twice as often as A, D nightkills B twice as often as A or C" strategy found by computer search). The scum strategy works by creating a situation that has more balanced probabilities than the original setup (as shown by the reasoning above).

Here's a simple argument that could help you to understand that there's a cut-off point: suppose the probability of each player being scum is respectively 6%, 6%, 6%, and 82%. Scum use the strategy of "nightkill a non-scum player at random from A, B, and C". It should be clear that, due to symmetry, the kill gives absolutely no information that would affect the probability of whether D is scum; you see a death in A/B/C whether D is scum or not, the kills are as likely as each other if D is scum, and the kills are as likely as each other if D is not scum. The best town strategy is clearly to lynch D, and it gives an EV of 82%, the chance that D is scum. What happened to the information that town gained from the scum kill? Well, all it did was to increase the scum chance of both of the surviving A/B/C players from 6% to 9%, and reduce the scum chance of the dead A/B/C player from 6% to 0%. Town have gained information, but it's not
useful
information, as all it did was to shuffle round the probabilities on the players who were unlikely to be scum anyway, and the resulting 9% chance is still small compared to the 82% chance of the likely scum still being scum.

The 10%/20%/30%/40% situation is more complex but is still using the same general principle; scum are using the information they're forced to give to drive one probability in the A/B/C set to 0% and equalise some of the others, without making D more likely than 40% on average to be scum. All you have to do to avoid changing the probability of D as scum is to promise to never kill D.

Actually, this gives a pretty easy explanation as to why the EV for the 25%, 25%, 25%, 25% case isn't 25%; in order to ensure that, scum would have to ensure that they never killed any of the four players (as if there's any circumstance under which scum would kill a particular player, and they don't die, that gives town useful information that increases the chance that that player is scum). In the alternative case of 0%, 33⅓%, 33⅓%, 33⅓%, scum could kill the 0% player and not give town any useful information. Now consider the case of 10%, 10%, 40%, 40%; scum can randomize between the two 10% players (or just kill the one that isn't scum, when one is scum), leading to a probability distribution of 0%, 20%, 40%, 40%. A low probability (10%) has been increased (to 20%), but it's
still
less than the most likely probability, so town can't make any use of the information they were given. Now consider the very similar case of 20%, 20%, 30%, 30%. Scum's nightkill of a player drives one probability to 0, and now it's not possible to keep all the remaining probabilities below 30%; the best scum can do is to equalise them to 0%, 33⅓%, 33⅓%, 33⅓%.

All this analysis leads to a very simple rule for determining the EV of an unbalanced-scum-chance 4p setup: the EV will be either the highest scum probability out of the original four players, or else 33⅓%, whichever is higher.
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
yessiree
yessiree
he
Mafia Scum
User avatar
User avatar
yessiree
he
Mafia Scum
Mafia Scum
Posts: 4389
Joined: June 6, 2013
Pronoun: he

Post Post #17 (ISO) » Sat Nov 03, 2018 5:50 am

Post by yessiree »

In post 16, callforjudgement wrote:No, Mafia will
not
always choose to kill A. Doing so would raise town's win probability above 40%: they could lynch D if A was nightkilled, or A if B was nightkilled, for a 50% win rate, if they knew what the scum strategy was.
Killing
any
player
will
raise town's winrate above 40% for the reasons I just listed in my last post... it's just a matter of by how much
In post 16, callforjudgement wrote:EV isn't necessarily going to equal the highest probability in the input distribution; however, it will
if
scum can make a kill that doesn't give away useful information. Killing purely at random does give away information (especially if you kill D), as does killing player A uncondtionally. However, if the distribution of scum is sufficiently unbalanced, it's possible to choose a probability distribution of kills such that town don't gain any useful information as a result of the kill; in that case, town can't do any better than to lynch the most likely scum.
scum killing any player other than A (given scum is not A) will NOT minimize town's winrate from mafia's perspective, just as lynching any player other than D will not maximize town's winrate from town's perspective.
To demonstrate this I'm going to use a simplified scenario where we are lynching from all 4 players ABCD:
let W be a vector that contains the probabilities distribution that town should lynch in ABCD
=> town EV = w1 * P(A=m) + w2 * P(B=m) + w3 * P(C=m) + w4 * P(D=m)
I assert that the weights w1...w4 that maximize town's EV is 0,0,0,1. ie. always lynch D for a town EV of 40%
You are asserting that there exists one other combination of weights that will produce a value > 40% when you say "it's possible to choose a probability distribution of kills such that town don't gain any useful information as a result of the kill". That is not possible.

When scum is not A, killing anyone other than A will raise town's EV higher than if A is killed because town will not lynch anyone other than D for the reason I mentioned above.


Town's EV should be
P(D=scum|A=dead) * P(A!=scum) + P(D=scum|B=dead) * P(A=scum)
= 4/9 * 90% + 1/2 * 10%
= 45%
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #18 (ISO) » Sat Nov 03, 2018 10:59 am

Post by callforjudgement »

Please, if you think town can get a win rate above 40% in the original setup, prove it.

Here's the scum strategy for minimizing town win rate:
  • If you're A: always nightkill C
  • If you're B: nightkill A or C, with equal probability
  • If you're C: nightkill A ⅓ of the time, B ⅔ of the time
  • If you're D: nightkill B half the time, otherwise randomize between A and C
This gives the following probabilities for the state at the start of D1:
  • 10%: C was nightkilled, A is scum
  • 10%: A was nightkilled, B is scum
  • 10%: C was nightkilled, B is scum
  • 10%: A was nightkilled, C is scum
  • 20%: B was nightkilled, C is scum
  • 10%: A was nightkilled, D is scum
  • 20%: B was nightkilled, D is scum
  • 10%: C was nightkilled, D is scum
Please give a town counterstrategy (i.e. who town lynches, given who was nightkilled) that wins more than 40% of the time. No "maths says scum should do this" or "town's EV is", just a counterstrategy. We can then evaluate the strategy against each of the eight cases above to determine how often town is actually scum.

Note that nothing that town can do can possibly affect the probability distribution above, as all that will be determined during pregame and N0, when town have no opportunity to act. So you can't change this table, all you can change is who is lynched.
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
BNL
BNL
Micro Madness
User avatar
User avatar
BNL
Micro Madness
Micro Madness
Posts: 3338
Joined: September 15, 2015
Location: EDT+12

Post Post #19 (ISO) » Wed Nov 07, 2018 1:25 am

Post by BNL »

There’s something I’m thinking about

Is it even accurate to talk about a Nash equilibrium between ‘Town’ and ‘Scum’?

I feel it should be a Nash Equilibrium between A, B, C and D, whatever it is.
GTKAS - BNL

Busy, on indefinite V/LA. May return April 2020
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #20 (ISO) » Wed Nov 07, 2018 5:35 am

Post by callforjudgement »

It's not accurate in general, because it doesn't model the effects of public communication (and private but alignment-unconfirmed communication, for setups using that) correctly. It is accurate for this setup.

In this particular setup, Nash equilibrium calculation should work because a) town's only decision is the lynch vote (which happens during the day), b) once town have lynched someone, the game's over and scum can't get any advantage from what the town talked about. That means that all the townies have the same information (there's no reason not to share it openly) and the same motivation, so they act like a single player for the purpose of a game-theoretic calculation.

There are more complicated setups for which there's no obvious way to apply a simple town vs. scum Nash equilibrium calculation; imagine a setup with two Town Roleblockers. They don't want to both block the same player, but they can't coordinate their blocks because then scum would discover who was being blocked, and perform the kill with a different member of the scumteam. So from a game-theory point of view that game effectively has at least three players (I haven't figured out whether the VTs are a separate side or not; it's hard to even define a Nash equilibrium in a three-player game because you need to specify precisely what the rules for collusion are).
scum
· scam · seam · team · term · tern · torn ·
town
Post Reply

Return to “Open Setup Discussion”