[SETUP] Bipartite Mafia

[mith]

I have at least convinced myself that you can't do better by holding off on the free pair until you get two successful pairings. First pair (say A-B) will lose 2/7 of the time, win 1/7 (basically force A to pair with B, and if A refuses then they are both scum and you just win by continuing to pair A with whoever), and continue 4/7. If you try to pair A (or B) again with C, you will lose 3/10 (1/2 * 3/5), and 2/7 + 4/7*3/10 is already 16/35, which is greater than 45%. If you try to pair C with D, again probability of immediate loss is 3/10 (3/5 * 2/4).

If you get the free pair after a successful A-B, you need to win 57/80 of those games to hit 55%. Mafia has two options:

1. If Mafia gives a new pairing C-D, you win 3/4. You try to pair one of A/B with one of C/D - if you succeed, then you win with the other pair (also guaranteed to have one scum).

2. However, if Mafia chooses from A-B to pair with C, town has three strategies I see: you can try pairing D with C and with B/A (the one not chosen for the free pair), and you always win if A was town but only win half if A was scum (you need to choose D scum). You can also try pairing A with D, and then one of E-G with one of B-D. If A is scum, A-D will work, and then you have a 2/3 for picking from E-G. If B+C are scum, you have a 1/4 of picking D scum, and then win if you do. And finally, you can try A-D and A-E, just assuming A is scum. You win if A is scum and lose if A is town. I doubt that town can force an equilibrium high enough, but I haven't worked out what the equilibrium is yet.

[mith]

No.

The first paragraph is just showing that you will lose more than 45% of the time if you

don't

take the free pair before trying to vote on two pairings. (EV for that strategy is even worse - Mafia can always pick a free pair such that town can't guarantee success on the third pairing.)

The other cases (free pair after one success) are broken down as follows (with some room for choosing e.g. B instead of A in some cases):

1. Pair A-B, Free Pair C-D, Pair A-C, Pair B-D.
2. Pair A-B, Free Pair A-C,
a. Pair C-D, Pair B-D
b. Pair A-D, Pair B-E
c. Pair A-D, Pair A-E

tl;dr - Asking for the free pair first is probably the way to go (but my intuition could be wrong about the equilibrium between Mafia's choice in 2 - whether they pick the scum or town from A-B - and Town strategies a-c), and I don't see any way of doing better than 55% yet.

[mith]

Yeah, looks like the best town can do there is 2/3 (picking a 2/3 of the time and c 1/3; b isn't helpful). That only gets you to an EV of 1/7 + 4/7*2/3 = 11/21 (52.38%).

[mith]

Oh, actually, b is a little better than I thought. On the A-D pairing, A could refuse to pair (if they are both scum), and town just wins here. There is a 1/2 chance of this happening, and a 2/3 chance of winning if A is scum and D is town (two of E-G are scum), so 5/6 overall for the A scum case, not 2/3. (Still doesn't improve the equilibrium though; the optimal a-b mixed strategy is 7/13 and 6/13, with an EV of 17/26, just a hair under 2/3.)

I can't improve on 55%. After Free Pair A-B and Pair A-C, town has the same three strategies a-c, with a giving 55% and the other two giving 50% (basically, you are taking the scum choice out of their hands and forcing an A 3/5 C 2/5 split, which makes strategy a. optimal). The other option is Free Pair A-B, Pair C-D, which has a 1/10 chance of winning immediately, 3/10 chance of losing immediately, and 6/10 chance of continuing with a 3/4 chance of winning from there (case 1 above), for a total of 1/10 + 9/20 = 11/20 = 55% again.