[EV] Vanilla Variants

[mith]

I am (slowly) working on updating my Vanilla Variants EV spreadsheets. This thread will serve as a repository for those results.

List of Variants

Vanilla

Nightkill Variants

Nightless, Nightless with Innocent Child
Double Day
Vengescum/Treestump, Vengescum with Innocent Children

Win Condition Variants

White Flag, White Flag Nightless
Black Flag, Black Flag Nightless
Red Flag
The Bus Stop, The Bus Stop 2

Lovers Variants

Lovers, Lovers Nightless
Paired Lovers, Poly Lovers
Simple Mafia
Blind Rage

Vengeful Variants

Vengeful
Vengevig
Vengecop (Dead Boy Detectives)
Vengewatch Revenge of the Vengeful
Revenge of the Vengeful, LyLo Variant

[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

[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.

[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%

[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.

[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.

[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.

[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] = (P_C(T-C+1) - P_C(M-C+1))/P_C(T-C+1)

where P_C(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) * (P_C(T-C+1)-P_C(M-C))/Pc(T-C+1) + (T-C)/(M+T-C) * (P_C(T-C)-P_C(M-C+1))/P_C(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]
= (P_C(T-C+1)-P_C(M-C+1))/P_C(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 ~ 2^1/CM
So, for T -> 2^1/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 -> P₂(T-1) = 2*P₂(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 -> P₃(T-2) = 2*P₂(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...)

[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 M_A Mafia and T_A Town, the other has M_B Mafia and T_B Town, with M = M_A + M_B, T = T_A + T_B).

Calculating EV

For M < T:
EV[M_A,T,M_B,0] = EV[Nighless: M_A,T] = (T-M_A)/(T+M_A)
EV[M,T_A,0,T_B] = EV[Nightless with IC: M,T_A,T_B] = (Π[T_A+1..T]-Π[M-T_B+1..M])/Π[T_A+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:

T_B = 0, T = T_A = 3*M_A, and M_B = 2*M_A - 1. (The trivial "lynch all of neighborhood B and then get on with playing a normal Nightless game" case.)
T_A = T_B, M_B = 0, M_A = 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...

[mith]

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

The corresponding setup with 1 town in neighborhood B is then: (M_A+1):(3M_A-1)/(2M_A-2):1. (This is why M_A > 1; for M_A = 1, neighborhood B is just the single townie.) For this setup there are 2M_A-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 (M_A+1):(3M_A-1) after lynching the rest of neighborhood B, EV = (2M_A-2)/4M_A
3. Town is lynched third (reduces to (M_A+1):(3M_A-1) again after lynching the rest of neighborhood B)
...
2M_A-1. Town is not lynched (reduces to (M_A+1):(3M_A-1):1, EV = (2M_A-1)/3M_A)

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

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

M_A = 2 -> 3:5/2:1 - EV = 1/4 (25%)
M_A = 3 -> 4:8/4:1 - EV = 14/45 (~31%)
M_A = 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 M_A=4), we will get close to the non-neighborhood Nightless value of 1/(4M_A-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).

[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 ∝ M^r+1?)

[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%)

[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*M^1+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 M² + 2.278 M - 1.223, with R² = 0.9999999978)

Further Hypothesis: The number of total players needed for an EV of p with M Mafia approaches (2/(1-p))*M^1+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 (R² = 1 to the precision of Excel). The fit is (rounded to) 4.088 M² + 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(M³) 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.

[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.

[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.4M²+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 M^1.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.

[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 aM^1+e + bM + c, where 0 < e << 1). For example, for White Flag Vengescum with e = .001, you get the absurd looking:

996.8105847832 M^1.001 - 994.737420011 M - 0.7789307603 (R² = 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 (R² = 0.9999999991)

For regular Vengescum:

1.0043292396 M ln(M) + 3.7616240109 M - 0.7131784171 (R² = 0.9999999985)

[mith]

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

Also have Double Day added, so I'll have some results on that soon.

[mith]

Double Day: 3.9104538193 M^1.5 + 0.0815355751 M + 6.2675689608 (R² = 0.9999999996) for M in [2..1000] (there is some tweaking to my output that needs to be done for Double Day - for instance, it is catching 1:4 as the last <= 50% setup for M=1, but that is actually a no-lynch and 1:3 is what we want; the best fit will change once I fix that issue, but it's not going to be far off)

And we're back in business with my original hypothesis... or at least a modified version where the coefficient is close to but not exactly 4. (Interesting that the Double Day leading coefficient is too small by almost the same amount as Vanilla is too large.)

For Vengescum, the ratio is not fixed; there will be at most M-1 night cycles and at most (T+M-1)/2 day cycles. The fit is not linear, since N/D > 0, but it also cannot be any exponent > 1 since that would mean 2(M-1)/(T+M-1) -> 0 (since T grows faster than M). I have an idea why it would converge to O(M lnM) rather than some other sub-quadratic, but that's for another day.

[mith]

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

I'm not entirely sure what you're getting at here.

As far as calculating exact EVs (for any setup other than Nightless)... I can't say for sure whether a closed form solution exists, but my suspicion is that the general answer is no.

If what you mean is coming up with a best fit like the ones provided and then using that fit to calculate EV at a given M:T, the issue is that these are typically least accurate when M is small (which are the setups we actually care about playing). The Double Day one in particular is terrible (if you plug in 1 you get a "balanced" setup of 1:9, which is silly), though I expect some of that is from the output issue. But even for Vengescum, my fit would spit out a 2:6 (43.21%) setup, rather than 2:7 (49.48%). It's pretty easy to calculate an exact EV for small games, recursively, these fits are only interesting asymptotically.

[mith]

So, this month's challenge prompted me to add the flag bearer mechanic to my script. Initially, I tested it on Flag Bearer Vengescum, finding that the growth is linear. I wasn't totally shocked that Flag Bearer Vanilla is

also

linear, but I was pretty surprised to find that the balance very quickly converges on Nightless balance.

Flag Bearer Vanilla

For M>=6, the closest setups to balanced are M:(3M-1) and M:(3M+1) - in fact, for larger M, the EVs are close to equidistant from 50%. (For example, 1000:2999 is 49.9875% and 1000:3001 is 50.00124%. Verified that this continues up to M=10000, and the extrapolated balance point seems to be converging on M:3M precisely.)

As far as practical setups go, 2:7 (48.25%) and 3:10 (49.10%) are both quite good - 4:13 and 5:16 are also just below 50%, before the trend above sets in. M:(3M+1) is always the closest to 50%.

Flag Bearer Nightless

Flag Bearer Nightless seems to be sub-linear in terms of excess townies (i.e. something like M:M+O(M^x), where 0 < x < 1). 1000:1028 has an EV of 49.8%, and the best fit up to M=1000 is somewhere around T=M+1.22*M^0.452.

2:4 (46.67%), 3:5 (44.05%), 4:6 (41.90%), and 5:7 (40.10%) would be reasonable to play; 3:6, 4:7, and 5:8 are closer to 50%, but on the town-sided side of things. 2:4 in particular is a better balanced version of Lovers Nightless (sort of a half-Lovers Nightless). After that 3 excess townies is below 50% (while 2 excess dips below 40%), up to 12:15.

Flag Bearer Vengescum

2:4 (42.78%) here is fine but Nightless is probably better for this count. 3:6 (47.57%) and 4:7 (42.50%) are good options.

Reasonable Micro and Mini Setups

2:4 Flag Bearer Nightless (46.67%)
2:5 Flag Bearer Vengescum (53.41%)
3:5 Flag Bearer Nightless (44.05%)
3:6 Flag Bearer Vengescum (47.57%), 2:7 Flag Bearer Vanilla (48.25%)
4:6 Flag Bearer Nightless (41.90%)
4:7 Flag Bearer Vengescum (42.50%)
5:7 Flag Bearer Nightless (40.10%)
3:10 Flag Bearer Vanilla (49.10%)

The Flag Bearer could also be combined with White Flag - which would effectively change the win condition to "lynch the Flag Bearer or lynch all the non-Flag Bearer Mafia" - but this would make very little difference to the asymptotic behavior. Which is a shame, because "White Flag Bearer" is such an obvious name.

[mith]

One thing I may look at in the future is the idea of multiple Flag Bearers - for example, town has to lynch both of the 2 Flag Bearers from however many Mafia total to win.

(In some sense, the Flag Bearer Mechanic is sort of an inverse Traitor - it effectively makes all the regular Mafia into Traitors except with full knowledge and communication between the Traitors and Mafia.)

[mith]

Double Flag Vanilla isn't that interesting; 3:16 up to 3:22 would all be fine EV-wise, but you might as well play with 2 Mafia and a Traitor (which would need even fewer Town), and probably everyone would hate it anyway. It does appear to be growing linearly for M>2 (something like M:5.5(M+1) isn't too far off; I didn't put this in the script, just eyeballing from my spreadsheet).

Double Flag Vengescum is fine at M:(2M+3) - 3:9 (48.83%), 4:11 (48.31%), 5:13 (47.86%), etc.; M:(2M+4) doesn't dip below 50% until 8:20.

Double Flag Nightless would be ok at 3:7 (47.78%) or 4:8 (45.86%)... even 8:12 is still above 40%, though 8:13 (46.19%) is better.