[EV] Soulbind except the mafia cant change the pairs

This forum is for discussion of individual Open Setups, including theoretical balance.
User avatar
Awoo
Awoo
Mafia Scum
User avatar
User avatar
Awoo
Mafia Scum
Mafia Scum
Posts: 1096
Joined: September 1, 2017
Location: lmao city

[EV] Soulbind except the mafia cant change the pairs

Post Post #0 (isolation #0) » Wed Jul 04, 2018 8:03 am

Post by Awoo »

Soulbind except the mafia pick what the pairings are pregame and its LYLO. I hope this will be the first EV thread / post I have made that is actually accurate.

Pregame the mafia put everyone into pairs except for one person who is alone.
If one half of a pair is lynched they both die and the next day starts without a night phase.
If the person who is alone (referred to as the loner) is lynched, the game goes to night and the mafia kill one member of a pair. The member of the pair that was not targeted remains alive as the new loner.

tl;dr: BNL's soulbind but the mafia pick pairs pregame and cant change them.

EV (2 town 1 mafia) = 1/2 - trivial

EV (3 town 2 mafia) = 1/3. Proof:

Define the probability the mafia will make each type of pairing pre-game.

P{ (MM)(TT)(T) } = a
P{ (TM)(TM)(T) } = b
P{ (TM)(TT)(M) } = 1 - a - b

where 0 <= a, b <= 1. The values of a and b are public knowledge.

Town can either choose to lynch a pair or lynch the loner.

EV (lynch a pair) = a/2 + b( X ) + ( X ) (1-b-a)/2
EV (lynch loner) = (1-b-a)/2

Let A and B be events.

A: We lynched a pair and it flipped (MT).
B: The loner is mafia.

P(A) = b + (1-a-b)/2
P(B) = 1-a-b
P(A|B) = 1/2

Where X = max(P(B|A), 1 - P(B|A))).

Since the town will just lynch the more likely of {pair, loner} to flip mafia. Which means X is has a minimum at 1/2 when the conditional probability becomes 1/2.

We want to minimize X, so let us find a formula for this.

P(B|A) = P(A|B)P(B) / P(A)
P(B|A) = ((1-a-b)/2) / (((1-a-b)/2) + b )
which simplifies to
P(B|A) = (1-a-b)/(1-a+b).
We want to have this equal to 1/2 to minimize town's EV.
1/2 = (1-a-b)/(1-a+b)
which yields the solution
b = (1-a)/3.

Let us put these results back into the original definitions:
Note that (1-a-((1-a)/3)/2 = (1-a)/3

P{ (MM)(TT)(T) } = a
P{ (TM)(TM)(T) } = (1-a)/3
P{ (TM)(TT)(M) } = 1 - a - (1-a)/3

EV (lynch a pair) = a/2 + ((1-a)/3)(1/2) + (1/2)((1-a)/ 3) = a/2 + ((1-a)/3)
EV (lynch loner) = (1-a)/3

Now the mafia have control over a, and they want to minimize town's EV. choose a = 0 has the result

EV(lynch a pair) = 1/3
EV(lynch a loner) = 1/3

and it follows that the strategy that gives this result as

P{ (MM)(TT)(T) } = 0
P{ (TM)(TM)(T) } = 1/3
P{ (TM)(TT)(M) } = 1- (1/3) = 2/3

, and it also follows that the worst play the mafia can make (short of claiming mafia) is to have a = 1, which yields a town EV of 1/2.


Hypothesis:

[1] in this setup, with N mafia and N+1 town, the town EV is 1/(N+1).
[2] As N increases, the probability that the loner is mafia approaches 1.
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 #1 (isolation #1) » Thu Jul 05, 2018 7:46 am

Post by Awoo »

EV(4-1) = 2/3. Mafia places himself as the loner 1/3 of the time to achieve this result.

Every setup of this type has an EV graph that looks kind of like this: (ignore values outside of [0, 1])
Image
EV(3-2)
Image
EV(4-1)
Where X is probability that the loner is mafia, Y is town's EV. g(x) is the conditional probability that the loner is mafia given that a TT lynch occurred yesterday. f(x) is the greater of the EV of (lynch loner, lynch pair) in 2-1 lylo. p(x) is the EV for lynching a pair d1. q(x) is the EV for lynching the loner d1.

Generally, when the loner is lynched and the game continues, the mafia can manipulate how often the new loner will be mafia using the nightkill (the value of x), which is crucial to mafia's objective of lowering town's EV. However, if mafia put themselves into pairs of (MM) pregame, they diminish their ability to do this with no other reward. Therefore I will be assuming mafia does not pair themselves into (MM) pairs going forward, even though I'm unable to come up with a general proof for it.

When a pair is lynched, the town forces a static X value going into the next day. I believe that based on the previous day's X value and the pair's flip (MT) or (TT), the town can determine a strategy for the next day (lynch pair or lynch loner) using conditional probability: the loner is mafia given that the flip was (MT) or (TT).
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 #3 (isolation #2) » Fri Jul 06, 2018 10:12 am

Post by Awoo »

I did prove that making an MM pairing is strictly suboptimal in (3-2). Do you think it would change in other situations? Because I feel like a lot of mafia's power to reduce EV in this comes from the ability to manipulate how often the loner is mafia.

Maybe if there are 3 mafia it's different because you have 1 free mafia if 2 pair up. But you can still get into some clunky endgames where the 2 are glued together and I still don't think it's worth it, though I will probably investigate that later.
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 #4 (isolation #3) » Tue Jul 10, 2018 3:53 am

Post by Awoo »

Furthermore, town is already has incentive to lynch pairs over the loner because then mafia can't manipulate the pairs overnight. I think proving this for a general case would be very hard since it would need to account for 4 different variables. Still working on a general case/recursive formula.
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 #5 (isolation #4) » Tue Jul 10, 2018 10:20 am

Post by Awoo »

Okay, I found the recursive formula. It is a bit of a monster to look at, but it always simplifies into a function that consists of 2 straight lines, starting at (0, 1), decreasing until it reaches a minimum, then increasing over the rest of the domain we are interested in.


Image

For reasons currently beyond my comprehension, that monster expression "EV for lynching a pair" ALWAYS simplifies to 1 - x for every setup I have tried. The somewhat less monstrous expression "EV for lynching a loner" always simplifies to ax + b, where a and b are between 0 and 1.

And assuming the "EV for lynching a pair" expression really does always simplify to 1 - x, then it would be true that the lowest EV mafia can achieve for town is always equal to 1 minus the probability that they make the loner mafia with optimal choice.

Here are some functions I have found already for your amusement. Maybe you can see a pattern? The EV for each is just 1 minus the minimum x value.

EV(2, 1)(x) = max(1-x, x), min @ x = 1/2
EV(4, 1)(x) = max(1-x, 1/2 x + 1/2) min @ x = 1/3
EV(6, 1)(x) = max(1-x, 1/3 x + 2/3), min @ x = 1/4
EV(3, 2)(x) = max(1-x, 1/2 x) min @ x = 2/3
EV(5, 2)(x) = max(1-x, 1/3 x + 1/3) min @ x = 1/2
EV(7, 2)(x) = max(1-x, 1/4 x + 1/2), min @ x = 2/5

Sadly, my function started producing nonsense results when I tried to evaluate EV(4, 3). I believe the cause for this is that my assumption that mafia should never make an MM pair only holds for m = 2, or at the very least does not hold for m = 3.
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 #7 (isolation #5) » Sat Aug 31, 2019 2:40 pm

Post by Awoo »

For some reason, I'm still working on this.

Turns out that when there are 3 or more mafia, this goes from a fun little activity that ends in a cute little plot of a 2D checkmark to a nightmarish higher dimensional optimization problem.

I'm trying to come up with the best possible mafia strategy for this setup when it starts at 4 vs 3. Mafia can choose between 4 different configurations, meaning there are three different probabilities to optimize.

A: Mafia choose {(MM)(MT)(TT)(T)}. P(A) = a
B: Mafia choose {{MM}(TT)(TT)(M)}. P(B) = b
C: Mafia choose {(MT)(MT)(MT)(T)}. P(C) = c
D: Mafia choose {(MT)(MT)(TT)(M)}. P(D) = 1 - a - b - c

From those values, I make some Mathematical Equations™, and then put those equations into some Optimizing Algorithms™. These optimizers don't behave very well when they get hit with the weird stuff I'm feeding them, and scipy seems to be blatantly disregarding the "max iterations" option I am providing it with. Progress is slow.

Anyways, my best attempt so far has been composed of surprisingly clean numbers:

a = 0.2
b = 0.15
c = 0.26
d = 0.39

Which yields a town EV of about 187 / 600, or ~ 31.2%. In terms of gameplay strategy, I have no idea why these numbers are the way they are, but I'm sure if you stare at them long enough, something rationalizes itself. The loner is mafia 54% of the time. There is an MM pair 35% of the time. I dunno.

If anyone thinks they're a bad enough dude to beat that number, just hit me up, and we can trade math equations.
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 #8 (isolation #6) » Sun Sep 01, 2019 2:01 am

Post by Awoo »

I found the minimum. No thanks to those useless algorithms that use dumb "jacobians" and "gradients" and don't even know how to return the smallest value they encountered.

Towns EV is exactly 30% in soulbound 4-3.

In order to achieve this, mafia uses the following setup:

A: Mafia choose {(MM)(MT)(TT)(T)}. P(A) = 0
B: Mafia choose {{MM}(TT)(TT)(M)}. P(B) = 0

C: Mafia choose {(MT)(MT)(MT)(T)}. P(C) = 0.4
D: Mafia choose {(MT)(MT)(TT)(M)}. P(D) = 0.6

Spoiler: graph
Image


Looks like it's still a bad strategy to use MM pairs! Can't say I saw this result coming.

Scoreboard:
----------------------
MT pairs | 2
MM pairs | 0
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 #10 (isolation #7) » Sun Sep 01, 2019 8:24 am

Post by Awoo »

Hey, same scumday!

Thanks for confirming that my results are supported by common sense! I personally don't have any, so I just use numbers instead.

Is there ever a situation in this setup where mafia will want to put themselves into MM pairs, by that same logic? If not, then oh man does that ever make my life easy.
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 #12 (isolation #8) » Sun Sep 01, 2019 12:08 pm

Post by Awoo »

This game is nightless btw. Only nightkills if the loner is lynched, and the pairs are only lovers by lynch. Is that what you mean? 'cause I don't think that TT thing is an instant win.
Post Reply

Return to “Open Setup Discussion”