[EV] Vanilla Variants

This forum is for discussion of individual Open Setups, including theoretical balance.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

[EV] Vanilla Variants

Post Post #0 (ISO) » Thu Jul 07, 2016 6:53 am

Post by mith »

Kappy
Kappy
Goon
Kappy
Goon
Goon
Posts: 294
Joined: May 1, 2016

Post Post #1 (ISO) » Thu Jul 07, 2016 8:13 am

Post by Kappy »

Don't put the quotes in the links. The wiki can't find them.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #2 (ISO) » Thu Jul 07, 2016 11:51 am

Post by mith »

Vanilla

[M] Mafia Goons
[T] Vanilla Town

Calculating EV

Let X=int((T-M+1)/2); X is the number of mislynches needed for a Mafia win.

EV[0,X] = 1; EV[M,0] = 0
EV[M,X] = ( M*EV[M-1,X] + (M+2X-1)*EV[M,X-1] ) / (2M+2X-1), for M,X>0

(If M+T is even, town should no lynch day 1 to restore parity; this does not cost them a mislynch, so the X calculated above is the same.)

For a given N=M+X-1, the denominator of EV[M,X] is found in the OEIS: A001803
For EV[1,X], the numerator is: A173384
For EV[M,1], the numerator is: A060818

Vanilla EV Identity

2^M * EV[M,1] = 1 - EV[1,M]

Exact EV up to 27 players (divide by first number):

Code: Select all

    M    0          1          2          3          4          5          6          7          8          9          10         11         12         13
 P
 1       1                                                                                                
 3       3          1                                                                                        
 5       15         7          2                                                                                
 7       35         19         8          2                                                                        
 9       315        187        94         36         8                                                                
 11      693        437        244        114        40         8                                                        
 13      3,003      1,979      1,186      624        272        88         16                                                
 15      6,435      4,387      2,768      1,578      784        320        96         16                                        
 17      109,395    76,627     50,294     30,396     16,504     7,760      2,976      832        128                                
 19      230,945    165,409    112,028    70,802     41,016     21,240     9,472      3,424      896        128                        
 21      969,969    707,825    491,870    322,104    196,096    108,984    53,904     22,848     7,808      1,920      256                
 23      2,028,117  1,503,829  1,067,720  719,790    455,840    267,472    142,752    67,536     27,264     8,832      2,048      256        
 25      16,900,975 12,706,671 9,188,406  6,346,180  4,150,600  2,542,880  1,439,040  738,304    334,592    128,896    39,680     8,704      1,024
 27      35,102,025 26,713,417 19,624,884 13,836,426 9,296,040  5,899,720  3,498,240  1,910,720  943,360    410,112    151,040    44,288     9,216      1,024


EV as percentage to 2 decimal places up to 99 players and 10 Mafia (E = T-M):

Code: Select all

   M     0         1         2         3         4         5         6         7         8         9        10
 E
 1    100%    33.33%    13.33%     5.71%     2.54%     1.15%     0.53%     0.25%     0.12%     0.06%     0.03%
 3    100%    46.67%    22.86%    11.43%     5.77%     2.93%     1.49%     0.76%     0.39%     0.20%     0.10%
 5    100%    54.29%    29.84%    16.45%     9.06%     4.97%     2.72%     1.48%     0.80%     0.44%     0.23%
 7    100%    59.37%    35.21%    20.78%    12.18%     7.09%     4.10%     2.36%     1.34%     0.76%     0.43%
 9    100%    63.06%    39.49%    24.52%    15.09%     9.20%     5.56%     3.33%     1.98%     1.17%     0.68%
11    100%    65.90%    43.01%    27.79%    17.76%    11.24%     7.04%     4.37%     2.69%     1.64%     0.99%
13    100%    68.17%    45.97%    30.66%    20.22%    13.19%     8.51%     5.44%     3.45%     2.16%     1.35%
15    100%    70.05%    48.51%    33.21%    22.48%    15.05%     9.97%     6.53%     4.24%     2.73%     1.74%
17    100%    71.62%    50.71%    35.49%    24.56%    16.81%    11.38%     7.63%     5.07%     3.33%     2.17%
19    100%    72.97%    52.65%    37.55%    26.48%    18.48%    12.75%     8.72%     5.90%     3.96%     2.63%
21    100%    74.15%    54.37%    39.42%    28.27%    20.05%    14.08%     9.79%     6.74%     4.60%     3.11%
23    100%    75.18%    55.91%    41.12%    29.93%    21.55%    15.36%    10.84%     7.58%     5.25%     3.61%
25    100%    76.10%    57.30%    42.69%    31.47%    22.97%    16.60%    11.88%     8.42%     5.92%     4.12%
27    100%    76.93%    58.57%    44.13%    32.92%    24.31%    17.78%    12.88%     9.25%     6.58%     4.65%
29    100%    77.67%    59.72%    45.47%    34.28%    25.59%    18.93%    13.87%    10.07%     7.25%     5.18%
31    100%    78.35%    60.79%    46.71%    35.55%    26.81%    20.02%    14.83%    10.88%     7.92%     5.71%
33    100%    78.97%    61.77%    47.87%    36.75%    27.96%    21.08%    15.76%    11.68%     8.58%     6.26%
35    100%    79.53%    62.68%    48.95%    37.89%    29.06%    22.10%    16.66%    12.46%     9.24%     6.80%
37    100%    80.06%    63.53%    49.97%    38.96%    30.12%    23.08%    17.55%    13.23%     9.89%     7.34%
39    100%    80.55%    64.32%    50.93%    39.98%    31.12%    24.03%    18.40%    13.98%    10.54%     7.88%
41    100%    81.00%    65.06%    51.83%    40.95%    32.09%    24.94%    19.23%    14.72%    11.18%     8.42%
43    100%    81.42%    65.76%    52.68%    41.87%    33.01%    25.82%    20.04%    15.44%    11.80%     8.96%
45    100%    81.82%    66.41%    53.49%    42.75%    33.90%    26.67%    20.83%    16.15%    12.42%     9.49%
47    100%    82.19%    67.03%    54.26%    43.58%    34.74%    27.49%    21.59%    16.84%    13.04%    10.02%
49    100%    82.54%    67.62%    54.99%    44.38%    35.56%    28.29%    22.34%    17.51%    13.64%    10.55%
51    100%    82.87%    68.17%    55.68%    45.15%    36.35%    29.05%    23.06%    18.18%    14.23%    11.06%
53    100%    83.18%    68.70%    56.34%    45.88%    37.10%    29.80%    23.76%    18.82%    14.81%    11.58%
55    100%    83.47%    69.20%    56.97%    46.59%    37.83%    30.52%    24.45%    19.46%    15.38%    12.09%
57    100%    83.75%    69.68%    57.58%    47.26%    38.54%    31.21%    25.12%    20.08%    15.95%    12.59%
59    100%    84.02%    70.13%    58.16%    47.91%    39.22%    31.89%    25.77%    20.69%    16.50%    13.08%
61    100%    84.27%    70.57%    58.71%    48.54%    39.87%    32.55%    26.40%    21.28%    17.05%    13.57%
63    100%    84.51%    70.98%    59.25%    49.14%    40.51%    33.18%    27.02%    21.86%    17.58%    14.05%
65    100%    84.75%    71.38%    59.76%    49.72%    41.12%    33.80%    27.62%    22.43%    18.11%    14.53%
67    100%    84.97%    71.76%    60.25%    50.29%    41.72%    34.40%    28.20%    22.99%    18.62%    15.00%
69    100%    85.18%    72.13%    60.73%    50.83%    42.29%    34.99%    28.78%    23.53%    19.13%    15.47%
71    100%    85.38%    72.49%    61.19%    51.35%    42.85%    35.56%    29.33%    24.06%    19.63%    15.92%
73    100%    85.58%    72.83%    61.63%    51.86%    43.40%    36.11%    29.88%    24.59%    20.12%    16.37%
75    100%    85.76%    73.15%    62.06%    52.35%    43.92%    36.65%    30.41%    25.10%    20.60%    16.82%
77    100%    85.94%    73.47%    62.47%    52.83%    44.43%    37.17%    30.93%    25.60%    21.08%    17.26%
79    100%    86.12%    73.77%    62.87%    53.29%    44.93%    37.69%    31.44%    26.09%    21.54%    17.69%
81    100%    86.28%    74.07%    63.25%    53.74%    45.42%    38.18%    31.94%    26.57%    22.00%
83    100%    86.45%    74.35%    63.63%    54.17%    45.89%    38.67%    32.42%    27.05%
85    100%    86.60%    74.63%    63.99%    54.59%    46.35%    39.15%    32.90%
87    100%    86.75%    74.89%    64.34%    55.00%    46.79%    39.61%
89    100%    86.90%    75.15%    64.68%    55.40%    47.23%
91    100%    87.04%    75.40%    65.01%    55.79%
93    100%    87.18%    75.65%    65.34%
95    100%    87.31%    75.88%
97    100%    87.44%


Python code for memory-efficient EV calculation:

Code: Select all

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Mafia EV calculator for Vanilla

f1_2 = open('output_vanilla_1_2', 'w')
max_m = 1001

# This algorithm caches the EV for each m at the previous player count
# All current player count EV can be calculated from these

# Initialize the arrays
previous = [0.0 for i in range(max_m)]
previous[0] = 1.0
current = [0.0 for i in range(max_m)]

z = 3
flag = False

while True:
  for m in range(max_m):
     if ( 0 == m ):
       # Town win
       current[m] = 1.0
     elif ( z < 2*m ):
       # Mafia win
       current[m] = 0.0
     else:
       # EV calculation for day outcome; m/z probability of lynching Mafia, etc.
       current[m] = ( m*previous[m-1] + (z-m)*previous[m] )/z
     # Find values on either side of EV = 1/2
     if ( 1.0/2.0 <= current[m] and 1.0/2.0 >= previous[m] ):
       # If both are exactly 1/2, we have reached the limit of our floating point precision
       if ( 1.0/2.0 == current[m] and 1.0/2.0 == previous[m] ):
         f1_2.write(str(m) + '\t' + str(z-2) + '\t' + str(previous[m]) + '\t' + str(previous[m]) + '\n')
         exit()
       else:
         # Interpolate estimate of z if player count were continuous
         estimate = z - 2.0 + ( 2.0*1.0/2.0 - 2*previous[m] )/( current[m] - previous[m] )
         f1_2.write(str(m) + '\t' + str(z-2) + '\t' + str(previous[m]) + '\t' + str(estimate) + '\n')
         print m
         # We have reached max value of m, we're done
         if ( ( max_m - 1 ) == m ):
           exit()
  # Cache values for z and clear values for next player count
  previous = current
  current = [0.0 for i in range(max_m)]
  # Increment by 2 - one for lynch, one for nightkill
  # Player count is always odd, even player count should always no lynch to restore parity
  z += 2
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #3 (ISO) » Thu Jul 07, 2016 12:22 pm

Post by mith »

Nightless

[M] Mafia Goons
[T] Vanilla Town
Nightless


Calculating EV

EV[M,T] = (T-M)/(T+M)

Proof by induction:

EV[M,M] = 0/2M = 0
EV[0,T] = T/T = 1

For 0<M<T:
EV[M,T] = M/(T+M) * EV[M-1,T] + T/(T+M) * EV[M,T-1]
= M/(T+M) * (T-M+1)/(T+M-1) + T/(T+M) * (T-M-1)/(T+M-1)
= (MT-MM+M + TT-TM-T)/((T+M)(T+M-1))
= (TT-T-MM+M)/((T+M)(T+M-1))
= ((T+M)(T-M)-(T-M))/((T+M)(T+M-1))
= ((T+M-1)(T-M))/((T+M)(T+M-1))
= (T-M)/(T+M)

For T = 3M, EV = 1/2.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #4 (ISO) » Mon Jul 11, 2016 10:29 am

Post by mith »

Vengescum

[M] Mafia Goons
[T] Vanilla Town
Day continues until Mafia lynch.


Calculating EV

Let X=T-M; X is the number of mislynches needed for a Mafia win. (In this setup, X is also the number of "excess" Townies, denoted E below.)

EV[0,X] = 1; EV[M,0] = 0
EV[M,X] = ( M*EV[M-1,X] + (M+X)*EV[M,X-1] ) / (2M+X), for M,X>0

EV as percentage to 2 decimal places up to 49 players and 10 Mafia (E = T-M):

Code: Select all

   M     0         1         2         3         4         5         6         7         8         9        10
 E
 1    100%    33.33%    13.33%     5.71%     2.54%     1.15%     0.53%     0.25%     0.12%     0.06%     0.03%
 2    100%    50.00%    25.56%    13.15%     6.79%     3.50%     1.80%     0.93%     0.48%     0.25%     0.13%
 3    100%    60.00%    35.40%    20.57%    11.80%     6.69%     3.76%     2.09%     1.16%     0.64%     0.35%
 4    100%    66.67%    43.21%    27.36%    16.99%    10.37%     6.24%     3.71%     2.18%     1.27%     0.73%
 5    100%    71.43%    49.48%    33.40%    22.04%    14.26%     9.07%     5.68%     3.51%     2.15%     1.30%
 6    100%    75.00%    54.59%    38.69%    26.79%    18.18%    12.10%     7.93%     5.12%     3.26%     2.05%
 7    100%    77.78%    58.80%    43.33%    31.21%    22.01%    15.23%    10.36%     6.94%     4.59%     2.99%
 8    100%    80.00%    62.34%    47.41%    35.26%    25.69%    18.37%    12.91%     8.93%     6.09%     4.10%
 9    100%    81.82%    65.33%    50.99%    38.96%    29.18%    21.46%    15.51%    11.04%     7.74%     5.35%
10    100%    83.33%    67.91%    54.16%    42.34%    32.47%    24.46%    18.12%    13.22%     9.50%     6.74%
11    100%    84.62%    70.13%    56.98%    45.42%    35.55%    27.35%    20.71%    15.44%    11.34%     8.22%
12    100%    85.71%    72.08%    59.50%    48.24%    38.44%    30.12%    23.24%    17.67%    13.24%     9.79%
13    100%    86.67%    73.80%    61.76%    50.81%    41.13%    32.76%    25.71%    19.89%    15.17%    11.42%
14    100%    87.50%    75.32%    63.79%    53.17%    43.63%    35.27%    28.10%    22.08%    17.11%    13.09%
15    100%    88.24%    76.68%    65.63%    55.34%    45.98%    37.65%    30.41%    24.23%    19.05%    14.80%
16    100%    88.89%    77.90%    67.30%    57.33%    48.16%    39.90%    32.62%    26.33%    20.98%    16.51%
17    100%    89.47%    79.00%    68.83%    59.17%    50.20%    42.03%    34.75%    28.37%    22.88%    18.23%
18    100%    90.00%    80.00%    70.23%    60.87%    52.10%    44.05%    36.78%    30.35%    24.75%    19.95%
19    100%    90.48%    80.91%    71.51%    62.45%    53.89%    45.95%    38.73%    32.26%    26.57%    21.65%
20    100%    90.91%    81.75%    72.69%    63.91%    55.56%    47.75%    40.59%    34.11%    28.36%    23.32%
21    100%    91.30%    82.51%    73.78%    65.27%    57.13%    49.46%    42.36%    35.90%    30.10%    24.98%
22    100%    91.67%    83.21%    74.79%    66.54%    58.60%    51.07%    44.05%    37.61%    31.79%    26.60%
23    100%    92.00%    83.87%    75.73%    67.73%    59.98%    52.60%    45.67%    39.27%    33.43%    28.19%
24    100%    92.31%    84.47%    76.60%    68.84%    61.28%    54.05%    47.21%    40.86%    35.02%    29.74%
25    100%    92.59%    85.03%    77.42%    69.88%    62.51%    55.42%    48.69%    42.38%    36.56%    31.26%
26    100%    92.86%    85.55%    78.18%    70.85%    63.67%    56.72%    50.09%    43.85%    38.05%    32.73%
27    100%    93.10%    86.04%    78.90%    71.77%    64.76%    57.96%    51.43%    45.26%    39.49%    34.17%
28    100%    93.33%    86.49%    79.57%    72.64%    65.80%    59.13%    52.72%    46.62%    40.89%    35.57%
29    100%    93.55%    86.92%    80.20%    73.46%    66.78%    60.25%    53.94%    47.92%    42.24%    36.93%
30    100%    93.75%    87.32%    80.79%    74.23%    67.71%    61.32%    55.12%    49.17%    43.54%
31    100%    93.94%    87.70%    81.35%    74.96%    68.60%    62.33%    56.24%    50.38%    44.79%
32    100%    94.12%    88.06%    81.88%    75.65%    69.44%    63.30%    57.32%    51.53%
33    100%    94.29%    88.39%    82.38%    76.31%    70.24%    64.23%    58.34%    52.64%
34    100%    94.44%    88.71%    82.86%    76.93%    71.00%    65.11%    59.33%
35    100%    94.59%    89.01%    83.31%    77.52%    71.72%    65.95%    60.28%
36    100%    94.74%    89.30%    83.74%    78.09%    72.41%    66.76%
37    100%    94.87%    89.57%    84.14%    78.63%    73.07%    67.53%
38    100%    95.00%    89.83%    84.53%    79.14%    73.71%
39    100%    95.12%    90.08%    84.90%    79.63%    74.31%
40    100%    95.24%    90.31%    85.25%    80.10%
41    100%    95.35%    90.54%    85.59%    80.55%
42    100%    95.45%    90.75%    85.91%
43    100%    95.56%    90.95%    86.22%
44    100%    95.65%    91.15%
45    100%    95.74%    91.34%
46    100%    95.83%
47    100%    95.92%
User avatar
LicketyQuickety
LicketyQuickety
Survivor
User avatar
User avatar
LicketyQuickety
Survivor
Survivor
Posts: 12785
Joined: May 14, 2015
Location: Where the moon and the sea meet.

Post Post #5 (ISO) » Fri Aug 12, 2016 3:48 pm

Post by LicketyQuickety »

I feel worse about myself after looking at this.
I was anything worse than you! Anything worse than you was I!

You was doided teh aposit_tisopa het dedoid saw em.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #6 (ISO) » Wed Feb 21, 2018 8:08 am

Post by mith »

Nightless with Innocent Child

[M] Mafia Goons
[T-1] Vanilla Town
1 Innocent Child
Nightless


Calculating EV

EV[M,T] = (T-M)/T

Proof by induction:

EV[M,M] = 0/M = 0
EV[0,T] = T/T = 1

For 0<M<T:
EV[M,T] = M/(T+M-1) * EV[M-1,T] + (T-1)/(T+M-1) * EV[M,T-1]
= M/(T+M-1) * (T-M+1)/T + (T-1)/(T+M-1) * (T-M-1)/(T-1)
= M(T-M+1)/(T(T+M-1)) + T(T-M-1)/(T(T+M-1))
= (MT-MM+M + TT-MT-T)/(T(T+M-1))
= (TT-MM-T+M)/(T(T+M-1))
= ((T-M)(T+M)-(T-M))/(T(T+M-1))
= ((T+M-1)(T-M))/(T(T+M-1))
= (T-M)/T

For T = 2M, EV = 1/2.

Notes:
EV for Nightless with Named Townie - that is, not Mod confirmed innocent - should be the same. Mafia can counterclaim the Named Townie with no change to EV if M = T-1, but otherwise are better off letting the Named Townie sit uncountered and thus confirmed.
This one has the nice property of having a greater Mafia ratio at 50% EV than Nightless (1/3 vs. 1/4), but at the cost of making the Innocent Child slot super important, since they cannot be killed.
A variant on this idea might be to have multiple Innocent Children but allow the Mafia a vengekill. (You can also just have multiple Innocent Children without the vengekill, effectively putting the Mafia in a White Flag situation of needing to keep at least as many members alive as Innocent Children. And yet another variant on this idea is that Mafia win at 50% *or* if there are no Vanilla Town left. Coupling this with the vengekill could actually get really interesting, but probably killing IC has a clear EV advantage.)

Nightless with 2 Innocent Children supports an even higher Mafia ratio, which converges on sqrt(2)-1. This is a wild result which deserves it's own post.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #7 (ISO) » Wed Feb 21, 2018 8:33 am

Post by mith »

Vengescum with Innocent Children

[M] Mafia Goons
[T-M] Vanilla Town
[M] Innocent Children
Day continues until Mafia lynch.


Calculating EV

EV[M,T] = (T-M)/T

Proof by induction:

(TBA)

For T = 2M, EV = 1/2.

Notes:
Ok, this was unexpected, but it makes some sense. The EV is exactly the same as Nightless with Innocent Child. Having more Innocent Children is stronger during the day, obviously, but giving the Mafia the vengekill means that the number of mislynches available never increases (whereas in Nightless or Nightless with Innocent Child, it goes up with a Mafia lynch). The M:M:M setup being perfectly balanced is quite interesting as well, and Mafia has control over which IC voices stay alive.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #8 (ISO) » Wed Feb 21, 2018 11:00 am

Post by mith »

Nightless with Innocent Children

[X] Mafia Goons
[Y-2] Vanilla Town
2 Innocent Children
Nightless, White Flag


Spoiler: Collapsed, see below
Calculating EV

EV[X,Y] = (T(Y-1)-T(X-1))/T(Y-1), where T(n) is the nth triangular number, n*(n+1)/2
(using X and Y instead of M and T to avoid confusion with T(n))

Proof by induction:

(TBA)

For Y -> sqrt(2) * X, EV -> 1/2

This would have been much more interesting to prove if the EV formula didn't have such a nice closed form, but EV = 1/2 implies T(Y-1) = 2*T(X-1) -> Y*(Y-1)/2 = X*(X-1) and in the limit this approaches Y^2 = 2X^2 -> Y/X = sqrt(2).

Perfectly balanced setups:

3:2:2
15:19:2
85:118:2
493:695:2

The OEIS gives X = A011900(n+1) and Y = A046090(n+1) for additional terms.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #9 (ISO) » Thu Feb 22, 2018 5:34 am

Post by mith »

Nightless with Innocent Children (Generalized)

[M] Mafia Goons
[T-C] Vanilla Town
[C] Innocent Children
Nightless


Calculating EV

EV[M,M] = 0
EV[C-1,T] = 1

For C-1 < M < T:
EV[M,T] = (PC(T-C+1) - PC(M-C+1))/PC(T-C+1)

where PC(n) are the figurate numbers for the C-dimensional analog of triangles (linear, triangular, tetrahedral, etc.).

Proof by induction:

EV[M,T] = M/(M+T-C) * EV[M-1,T] + (T-C)/(M+T-C) * EV[M,T-1]
= M/(M+T-C) * (PC(T-C+1)-PC(M-C))/Pc(T-C+1) + (T-C)/(M+T-C) * (PC(T-C)-PC(M-C+1))/PC(T-C)
= (M * (1-Π[M-C..M-1]/Π[T-C+1..T]) + (T-C) * (1-Π[M-C+1..M]/Π[T-C..T-1]))/(M+T-C)
= (M+T-C - Π[M-C..M]/Π[T-C+1..T] - Π[M-C+1..M]/Π[T-C+1..T-1])/(M+T-C)
= 1 - ((M-C)*Π[M-C+1..M]/Π[T-C+1..T] - T*Π[M-C+1..M]/Π[T-C+1..T])/(M+T-C)
= 1 - Π[M-C+1..M]/Π[T-C+1..T]
= (Π[T-C+1..T]-Π[M-C+1..M])/Π[T-C+1..T]
= (PC(T-C+1)-PC(M-C+1))/PC(T-C+1)

Asymptotic Behavior of Balanced Setups:

If EV = 1/2, Π[T-C+1..T] = 2*Π[M-C+1..M]; for large T and M, Π[T-C+1..T] -> T^C and Π[M-C+1..M] -> M^C, so T^C ~ 2*M^C and T ~ 21/CM
So, for T -> 21/CM, EV -> 1/2

Spoiler: Collapsed discussion of exactly balanced setups
Setups where EV = 1/2 exactly correspond with C-simplex numbers which are exactly half of another C-simplex number:

C = 1 -> T = 2M (1:1:1, 2:3:1, etc.)
C = 2 -> P2(T-1) = 2*P2(M-1), which is true for the setups listed above (3:2:2, 15:19:2, 85:118:2, 493:695:2), corresponding to triangular pairs [3,6], [105,210], [3570,7140], [121278,242556].
C = 3 -> P3(T-2) = 2*P2(M-2), which is true for 5:3:3 (tetrahedral pair [10,20]), and I haven't found a list long enough to find another.
For general C, there is a "trivial" solution at (2C-1,C,C), due to the fact that Π[C+1..2C] = 2*Π[C..2C-1].

Additionally, we can find other solutions based on the triangular pairs above, as follows:
2*(
2*3
/2) =
3*4
/2 from the [3,6] pair, which just results in 3:2:2 again, but since they overlap you also get 2*2 = 4 for 2:3:1. But for C = 6, 2*(
14*15
*16*17*18*19/6!) = 16*17*18*19*
20*21
/6!, since 14*15/2 = 105 and 20*21/2 = 210, which results in the setup 19:15:6, if anyone wants to run a balanced setup with 19 Mafia out of 40 players... You can do more but these get ridiculous in a hurry. C = 35, 2*(
84*85
*86*...*118/35!) = 86*...*118*
119*120
/35!, for a 118:85:35 setup, and you can probably see the pattern here with M:(T-2):2 generating an also balanced (T-2):M:(T-M) setup.

The same thing should be doable with tetrahedral pairs: 5:3:3 -> 3:5:1 for the trivial case (in general, the C>1 trivial setups will generate the C=1 setups, and vice versa), but the next pair should generate a new setup.

Up to the 1000th C-simplex number for C=2..7, the only non-trivial, non-tetrahedral pair I've found is the C=6 pair generated from [105,210], which is [27132,54264]. I'm now wondering if these are the only solutions (and whether someone has already proved this to be the case).

(One of these days I'm publishing a paper on all this...)
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #10 (ISO) » Mon Feb 26, 2018 6:30 am

Post by mith »

Nightless Neighborhood Mafia

[M] Mafia Goons
[T] Vanilla Town
Nightless

Pre-game, the players are split into two "neighborhoods", A and B; in addition to the neighborhood assignments being public, the split of Mafia and Town within each neighborhood is known (that is, one neighborhood has MA Mafia and TA Town, the other has MB Mafia and TB Town, with M = MA + MB, T = TA + TB).

Calculating EV

For M < T:
EV[MA,T,MB,0] = EV[Nighless: MA,T] = (T-MA)/(T+MA)
EV[M,TA,0,TB] = EV[Nightless with IC: M,TA,TB] = (Π[TA+1..T]-Π[M-TB+1..M])/Π[TA+1..T]

In between the trivial B Neighborhood cases, town should lynch from whichever neighborhood has a higher ratio of Mafia (proof left to reader), so it gets a bit messy. Still investigating whether there is a meaningful pattern here.

Note, however, that you can (trivially) get a Mafia ratio arbitrarily close to 50% with EV = 1/2 by either picking:

TB = 0, T = TA = 3*MA, and MB = 2*MA - 1. (The trivial "lynch all of neighborhood B and then get on with playing a normal Nightless game" case.)
TA = TB, MB = 0, MA = T-1. (The trivial Nightless with IC [2C-1]:C:C solution above.)

For M = 5, say, these setups are 2:6/3:0 and 5:3/0:3. What I'm curious about is the behavior of the in-between setups (that is, for A=8, B=3, either 3:5/2:1 or 4:4/1:2).

I'm not yet convinced that there is a nice closed form EV formula for non-trivial setups (with all values > 0). But... to be continued...

[edit]

3:5/2:1 has an EV of 1/4, as follows:

There are three cases for what happens in B, with equal probability:
1. Town is lynched first (EV 0)
2. Town is lynched second (reduces to 3:5, EV 1/4)
3. Town is not lynched (reduces to 3:5:1, EV 1/2)

4:4/1:2 does not reduce nicely, since town will want to lynch in A initially...
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #11 (ISO) » Mon Feb 26, 2018 12:55 pm

Post by mith »

Consider the general case for EV = 1/2 with an all-Mafia neighborhood B: MA:3MA/(2MA-1):0, where MA > 1.

The corresponding setup with 1 town in neighborhood B is then: (MA+1):(3MA-1)/(2MA-2):1. (This is why MA > 1; for MA = 1, neighborhood B is just the single townie.) For this setup there are 2MA-1 cases for the resolution of neighborhood B, with equal probability:

1. Town is lynched first (EV 0)
2. Town is lynched second (reduces to (MA+1):(3MA-1) after lynching the rest of neighborhood B, EV = (2MA-2)/4MA
3. Town is lynched third (reduces to (MA+1):(3MA-1) again after lynching the rest of neighborhood B)
...
2MA-1. Town is not lynched (reduces to (MA+1):(3MA-1):1, EV = (2MA-1)/3MA)

Thus, the total EV is (replacing MA = a for compactness):
EV = (2a-3)/(2a-1) * (2a-2)/4a + 1/(2a-1) * (2a-1)/3a
= (4a2-10a+6)/(8a2-4a) + 1/3a
= (6a2-15a+9)/(12a2-6a) + (4a-2)/(12a2-6a)
= (6a2-11a+7)/(12a2-6a)

This approaches 1/2 for large MA (which makes sense intuitively, since this is closer and closer to the EV = 1/2 Nightless setup). For the first values;

MA = 2 -> 3:5/2:1 - EV = 1/4 (25%)
MA = 3 -> 4:8/4:1 - EV = 14/45 (~31%)
MA = 4 -> 5:11/6:1 - EV = 59/168 (~35%)
etc.

This will always be less than the adjacent EV = 1/2 setup, though. And my suspicion is that as we approach the middle point (e.g. 8:8/3:4 for MA=4), we will get close to the non-neighborhood Nightless value of 1/(4MA-1), as the additional information from the neighborhoods is minimal (that is, it only matters once we have hit the point where something is 0).
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #12 (ISO) » Tue Feb 27, 2018 5:02 am

Post by callforjudgement »

I find it very interesting that a Nightless setup with 493 scum requires 1479 Vanilla Townies to balance, but only 697 townies if two of them are Innocent Children (or otherwise named/distinguished). Adding the two power roles has more than halved the number of townies required.

I suspect that what's going on here is that the exact details of a "final lylo" propagate all the way throughout a Nightless setup; after all, we can typically expect VTs and scum to die in numbers proportional to their proportions (under EV assumptions, if all kills are town-controlled). So if the town:scum ratio starts at approximately a:b, we can expect it to end up as approximately a:b when we get close to lylo. In vanilla-only nightless, this ratio is 3:1 to produce a balanced endgame (because scum will have 2 tries to find 1 scum in 4 people), so we have approximately 3:1 proportions in EV-balanced setups (and in fact, it's well known that a 3
x
:
x
vanilla nightless is EV-balanced for any positive integer
x
).

When we add in the two confirmed innocents, that basically just makes a change to endgame conditions (because they won't ever die, thus aren't in the lynchpool, and simply serve to give the town extra votes when the number of VTs has fallen to equal the scum or to be 1 lower). Just to confirm mith's numbers of 3 scum / 2 VT / 2 confirmed: there's a 40% chance that town lynch a VT and lose instantly, but the other 60% of the time, they get two tries to find scum in a pool of four players (and there are two scum there), because once scum are reduced to 1 member, the confirmed townies can endgame them. 5 out of the 6 possible pairs work, so 5÷6×60%=50% of the time, town will win. This means that balanced endgames are much more town/scum balanced, and so the asymptotic numbers in large setups will be too.

Of course, all this theory is dubious when it comes to actual play; IIRC practical vanilla Nightless games tend to be run at numbers more like 9:4, because it turns out that when scum can't kill good scumhunters, they have a major disadvantage.
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #13 (ISO) » Tue Feb 27, 2018 5:51 am

Post by mith »

That's an interesting way of looking at it. In the limit, this is what tends to happen (for a given C, the ratio between M and T-C approaches the ratio of M and T, so we would expect the large game to reduce a smaller game with the same ratio "on average"). This may just be an artifact of the balanced setups approximating (or matching exactly) a particular ratio though, rather than the other way around.

In my experience with vanilla variant EVs, the two biggest factors tend to be this endgame effect and the ratio of town kills to scum kills. I'm wondering now if you could generate some interesting balanced setups manipulating the latter in interesting ways - for example, Nightless as a ratio of 0, Vanilla has a ratio of 1, and Double Day has a ratio of 1/2. What about a 2/3 ratio? (Alternate between Vanilla and Double Day.) What do these changes do to balanced setup trend? (We know Nightless is linear while Vanilla is quadratic, for example. Does the general balanced setup tend toward T ∝ Mr+1?)
User avatar
LicketyQuickety
LicketyQuickety
Survivor
User avatar
User avatar
LicketyQuickety
Survivor
Survivor
Posts: 12785
Joined: May 14, 2015
Location: Where the moon and the sea meet.

Post Post #14 (ISO) » Thu Mar 01, 2018 8:47 pm

Post by LicketyQuickety »

Request: 15 player White Flag, 3 Scum
I was anything worse than you! Anything worse than you was I!

You was doided teh aposit_tisopa het dedoid saw em.
User avatar
Mathdino
Mathdino
Survivor
User avatar
User avatar
Mathdino
Survivor
Survivor
Posts: 14337
Joined: February 24, 2013
Location: Right Behind You

Post Post #15 (ISO) » Thu Mar 01, 2018 9:13 pm

Post by Mathdino »

In post 14, LicketyQuickety wrote:Request: 15 player White Flag, 3 Scum
:lol: :lol: :giggle: :lol: :lol:

Edit: The EV Project does most of our work for us here. Working backwards,

Mafia Lovers 13p 11 - 2:
Mafia must lynch town 5 times to win:
11/13 * 9/11 * 7/9 * 5/7 * 3/5 = 3/13 Scum win
Otherwise 10/13 Town win

White Flag 15p 12 - 3
3/15 (Scum Lynch): GOTO ~Mafia Lovers~ 13p 11 - 2 (10/13 Town win)
12/15 (Town Lynch): GOTO 13p: 10 - 3 (1436/3003 Town win)

(3/15 * 10/13 + 12/15*1436/3003) = 53.6%

Town should have a ~53.6% chance of winning 12:3 White Flag.
User avatar
LicketyQuickety
LicketyQuickety
Survivor
User avatar
User avatar
LicketyQuickety
Survivor
Survivor
Posts: 12785
Joined: May 14, 2015
Location: Where the moon and the sea meet.

Post Post #16 (ISO) » Thu Mar 01, 2018 10:53 pm

Post by LicketyQuickety »

IDK why that is funny, but thanks regardless.
I was anything worse than you! Anything worse than you was I!

You was doided teh aposit_tisopa het dedoid saw em.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #17 (ISO) » Tue Mar 13, 2018 7:31 am

Post by mith »

I really need to spend some time syncing the this thread and the EV Project with my spreadsheet. I have a ton of results for vanilla variants that are in a more readable format. (White Flag is balanced at 19:4, for example, 48%)
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #18 (ISO) » Thu Mar 15, 2018 10:29 am

Post by mith »

Hypothesis:


For a Vanilla Variant with a ratio of N night cycles to D day cycles, the number of total players needed to balance a game with M Mafia approaches 4*M1+N/D, for large M.

(We already know this is true for Nightless - not even asymptotically, it is exactly true. It appears to hold for Vanilla and Double Day, though I don't have the data points to be super confident. For Vanilla with M in [1..100], best fit is 4.088 M2 + 2.278 M - 1.223, with R2 = 0.9999999978)

Further Hypothesis: The number of total players needed for an EV of p with M Mafia approaches (2/(1-p))*M1+N/D, for large M. (Again, this is exactly true for Nightless. The behavior is somewhat undefined at p = 0, since the game is already over at this point and the N/D ratio is meaningless, but if N/D is taken as 0 in this case then the boundary condition matches, P = 2M. For p->1, P -> infinity, which again makes sense, as this is only exactly true when M = 0.)


Sadly, even the initial hypothesis does not appear to hold. I ran the numbers up to M=250 for Vanilla, calculating an additional "estimate" value (interpolating the two player counts on either side of EV=1/2 to estimate where the EV would be exactly balanced were player count continuous), and this fits a quadratic very precisely (R2 = 1 to the precision of Excel). The fit is (rounded to) 4.088 M2 + 2.299 M - 0.634, with the quadratic coefficient changing very slowly as max_M increases. If it does converge to 4, it takes a very long time to do so.

Now up to M=500. The closest balanced setup has 1023149 players, with an EV of 0.5000001061. The interpolation is 1023148.43626, while the best fit gives 1023148.43824 - a difference of less than two thousandths of a player.
And now M=1000. The closest balanced setup has 4090297 players, with an EV of 0.5000000206. The difference between interpolation and best fit is just a bit over one thousandth of a player.

I think I'll probably stop once the number of players is greater than the global population. :) (M ~ 43145) Pretty sure I would need a supercomputer to get there (the algorithm is taking O(M3) since the number of players is quadratic, and I don't see a way to improve that; at least memory is only O(M)).

I'll add the code to the Vanilla EV post above, if someone wants to play with it. The multiball code is still a big mess that needs to be re-written.
User avatar
Mathdino
Mathdino
Survivor
User avatar
User avatar
Mathdino
Survivor
Survivor
Posts: 14337
Joined: February 24, 2013
Location: Right Behind You

Post Post #19 (ISO) » Thu Apr 05, 2018 3:24 am

Post by Mathdino »

A heads up: The functools library from Python 2.5 gives us a built in memoization function, which I've been using for my own EV calculations.

Also, your code isn't updated to Python 3 :P

Vanilla EV:

Code: Select all

import functools
import timeit

def memoize(func):
  #Generalized memoization function.
  cache = func.cache = {}
  
  @functools.wraps(func)
  def memoized_func(*args, **kwargs):
    key = str(args) + str(kwargs)
    if key not in cache:
      cache[key] = func(*args, **kwargs)
    return cache[key]
    
  return memoized_func

@memoize
def ev(mg=1, vt=None):
  # Recursively defined.
  
  # Calculates LyLo EV if undefined vt
  if vt==None: vt = mg+1
  
  play = mg + vt
  
  # Win conditions:
  if mg<=0: return 1
  if mg>=vt: return 0
  
  # No Lynch on Evens
  if play%2 == 0:
    return ev(mg, vt-1)
  else:
    # Townlynch EV + Scumlynch EV
    return (vt/play * ev(mg, vt-2)) + (mg/play * ev(mg-1, vt-1))

print(ev(2, 19))


I'm not sure how to turn your code into a function to compare runtimes. If this way looks faster, I also have code sitting around for Double Day and Vengescum.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #20 (ISO) » Thu Apr 05, 2018 5:47 am

Post by mith »

Recursive functions are a bad idea if you want to go for high numbers of players. I think the default recursion depth for python is something like 1000. Caching also takes up a lot of memory eventually. I was doing something similar to this previously, but re-wrote it to run iteratively and only cache up to 2M values at a time.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #21 (ISO) » Thu Apr 12, 2018 12:56 pm

Post by mith »

Working on making my script more flexible, so quick things on asymptotic trends:

Vanilla is obviously quadratic, as discussed above.
White Flag is also quadratic, though naturally it has a smaller coefficient (~1.4M2+0.7M). Not having to lynch that last scum really propagates, and you only need about a third as many townies to balance.
Nightless EV is known, and balanced at M:3M. White Flag Nightless is of course also linear, and is close to balanced at M:2M. Except for 2:3 and 2:4 being equidistant (40% and 60% respectively), exactly twice as many townies is closest to 50% for M up to 16. (The linear coefficient is converging somewhere between 3.05 and 3.09; I'll have to go to bigger M for a better fit.)
Vengescum and White Flag Vengescum (=Grey Flag Nightless) are more interesting. They are clearly not linear, but up to M=100 I can't tell from the trendlines whether they are quadratic or not. A power function fit proportional to something like M1.2 works quite well in both. (White Flag Vengescum also has a nice 45% EV at 4:9, and 46% at 3:6. Vengescum itself is at 49.5% for 2:7; I think all the games run on mafiascum have had 3 scum and an EV <40%, IIRC.)

Anyway, I've got nice wiki tables generated for all of these, I'll get them on the wiki at some point.
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #22 (ISO) » Fri Apr 13, 2018 7:10 am

Post by mith »

Reasonably confident that they are sub-quadratic, now, though it's likely I'm over-fitting (playing with the LINEST function to give a regression of the form aM1+e + bM + c, where 0 < e << 1). For example, for White Flag Vengescum with e = .001, you get the absurd looking:

996.8105847832 M1.001 - 994.737420011 M - 0.7789307603 (R2 = 0.9999999982).

My suspicion at the moment is that for larger ranges of M, the best e to use will approach 0.

[edit]And indeed a much cleaner fit is found with the form a M ln(M) + b M + c:

1.0035646646 M ln(M) + 2.0500642642 M - 0.5509157961 (R2 = 0.9999999991)

For regular Vengescum:

1.0043292396 M ln(M) + 3.7616240109 M - 0.7131784171 (R2 = 0.9999999985)
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #23 (ISO) » Fri Apr 13, 2018 9:43 am

Post by mith »

White Flag Nightless: 3.0641830409 M - 0.5359770953 (R2 = 1) for M in [2..1000]
White Flag: 1.3950627446 M2 + 0.7249508225 M - 0.5280834592 (R2 = 1) for M in [2..1000]

Also have Double Day added, so I'll have some results on that soon.
User avatar
Mathdino
Mathdino
Survivor
User avatar
User avatar
Mathdino
Survivor
Survivor
Posts: 14337
Joined: February 24, 2013
Location: Right Behind You

Post Post #24 (ISO) » Fri Apr 13, 2018 9:48 am

Post by Mathdino »

do you think it'd be easier for coming up with exact (rather than approximate) solutions for EV

to come up with models predicting EV for a fixed M or a fixed T

and then producing a three variable equation based on that?

and then of course setting EV to 0.5 and solving for T

i'm no expert in regression but it seems like this would produce a more holistic view of EV
Post Reply

Return to “Open Setup Discussion”