[EV] Oracular Mafia

[mith]

It's not

perfectly

broken solely on the basis of the town generated information. There are 1287 possible solutions to the game (13 choose 5), but 8 bits is only 256 things to cover. With only one mislynch available, that may not even be enough to win.

However, town can potentially get additional information based on the Mafia result claims. I'd be surprised if you can't at least win with that. I think I'd also be surprised if you can win perfectly, though.

It'd probably be best to start with a smaller setup (3:6, for example; 84 possibilities, 64 town bits) to figure out how to force scum to give you info.

[mith]

The difference between this sort of puzzle (similar to the truth-teller/liar puzzles) and error correcting is that "errors" here also give you information (namely that the false statement is coming from scum). It's (probably?) less reliable than 13 certain bits, but should be more reliable than 8 certain bits. At least, that's my intuition about it.

[mith]

So, I ran through all the possibilities for 3:6 with a very simple scheme of "ask if the next player on the list is scum". This does indeed give enough information to guarantee a win from day 1 (without worrying about night kills giving us extra information - that part is likely more useful in 5:8).

Basically, there are 84 possible scum teams and 8 ways the scum can give results (2^3), so 672 possible scenarios. Out of these, there are a total of 366 unique sets of oracle results. No result can be reached from more than 3 possible scum teams. One scum is always guaranteed in the 3 possibility cases, so there's your day 1 lynch, and the remaining three possibilities can be sorted out with at most one mislynch. In the 2 possibility cases, there are two scum guaranteed, and a coinflip for the other two. In the 1 possibility case, obviously you've found the scum team - but in most of these, scum will just avoid that case.

The only guaranteed perfect wins are if the scum are evenly spaced in the list (that is, they are in places 147, 258, or 369). The overall probability of a perfect win should be 3/84 * 1 + 27/84 * 1/2 + 54/84 * 1/3 = 69/168, about ~41%. (There are 27 scum groups where the scum can do no better than 2 possibilities, and the remaining 54 they can pick a result pattern with 3 possibilities.)

There is almost certainly a way to improve on that 41% by asking a more complicated set of questions, and this scheme is much more problematic with 5:8 (where scum have 32 options for results and are a higher ratio of the players) - if I had to guess I would lean toward town can't guarantee a win without the benefit of nightkills eliminating possibilities.

I think the scumteam eliminating scheme will likely do better, though it's more complicated to prove.

[mith]

Well, you can do something like putting all the setups where B is scum (and A is not scum) on the same half of the split. That gives you a good advantage in scumteam elimination if A says that the other half of the split is correct (because now you know that either A is scum or B is town). It's less useful if the split goes the other way, though, and there's limits to how much you can do this for two players B and C using A's question (as they could be scum together). Perhaps you want all the scumteams where B is scum and C isn't on one side of the split, all the scumteams where C is scum and B isn't on the other side, and to split the both-scum and neither-scum cases equally.

I think this is a good idea. It reduces the number of scumteams that B or C can be on (depending on the answer to the question) to 225, meaning our next question can eliminate 333 more possibilities. Perhaps we would then proceed with that second question splitting the D/E cases similarly (and the next F/G, then H/I, then J/K, then L/M).

(Actually, it's more complicated than that, because you will already have some small additional info on the other players - e.g. you can't evenly split the 372 cases where B and C have the same alignment evenly among players D-M, and that should affect which pair of players is chosen next.)

[mith]

(Another possibility to simplify things would be to just ask about A - there are 330 possibilities with A scum B/C town, and 336 with A town B/C town, so it's not quite as efficient, but pretty close. That doesn't give you a good candidate for asking the next question though.)

[mith]

Actually actually, it's likely optimal to split the cases for A as follows:

"Is one of the following true: B is scum and C is town, or B and C have the same alignment and D is scum and E is town, or B and C have the same alignment and D and E have the same alignment and F is scum and G is town, or...?"

A yes will result in 225 cases remaining where C is scum, but also reduce the number of cases for E, G, etc. scum, so C can then ask something like "Is one of the following true: E is scum and G is town, or E and G have the same alignment and I is scum and K is town, or...?"

This gets complicated to calculate in a hurry, may put it in a spreadsheet with all the possible scum groups.

[edit]After a no answer, this is a breakdown of the number of possible scumgroups for each player:

A - 495
B - 225
C - 435
D - 281
E - 379
F - 307
G - 353
H - 319
I - 341
J - 325
K - 335
L - 325
M - 335

So the next question should probably pair D/F, H/J, L/K, M/I, G/E, C/A. (I was initially surprised that J/K and L/M are the same, but if A is town then we know there is at least one pair with 1 scum, and once we've reached those last two pairings we know there is *exactly* one pair with 1 scum, so they are on even footing.)

[edit2]Actually have to tweak the pairings a bit to get it balanced, since the first in each pair is always less likely to be scum. I found one with a 333/333 split, which is pretty disorganized because of how big a difference there is between D and F - it looks like this: D>F or D=F/M>H or D=F/M=H/C>J or D=F/M=H/C=J /G>L or D=F/M=H/C=J/G=L/E>K or D=F/M=H/C=J/G=L/E=K/A>I, where D>F means D is more scum than F (that is, D is scum and F is not).

After this point, a pair of no answers means D is only scum in 74 of the 558 remaining possibilities, while no/yes means F is only scum in 97 of them. Very different spreads overall. But it seems quite promising after only two questions.

[mith]

I'm going to put together a script for this at some point - but in the short term, I'm going to try just a fixed scheme of questions such that each each pair of players is paired in exactly one other player's question (and evenly distributed as far as priorities across all questions). Think 13 team round robin scheduling, where the team with the bye is the player asking the question.

This scheme would still ensure that each player's question individually rules out the maximum number of possibilities. It wouldn't ensure that it is an optimal way to arrange the set of questions, but it may still be enough to solve the game.

[mith]

That didn't do the job (at least, not without considering night kills); worst cases for results have 23 possibilities for the version I implemented (of course, there are many other ways to implement it). It happens that these are the 26 permutations of yynnyynnyynnn and nnyynnyynnyyy. I'll try some different implementations but I suspect they will all have a similar flaw (that is, it's probably not enough to choose a scheme beforehand; it's better to use the previous results to inform construction of the future questions).

[mith]

For the first such worst case, it looks like the breakdown by player is:

0 9
1 5
2 1
3 14
4 15
5 2
6 2
7 16
8 14
9 1
10 5
11 9
12 22

So night kills are definitely going to help us some. If we lynch player 12, we either get scum or know the group. Then scum will kill 2 or 9 and eliminate another possibility. It's not enough though - for example, if town then lynches 4 and misses, scum can kill the other of 2 or 9 (both can only be scum with both 4 and 7), town knows 3 is scum (8 if 7 isn't), but then scum has another no information kill in 6 and town is still left with seven possibilities for the remaining three scum.

[mith]

Ok, found a better version quickly as far as number of possibilities (max 16), but "scummiest" player is only 12/16 and scum has three free kills... definitely not a 100% win here (much less a forced win).

[mith]

Found a new best: 13 possibilities max. The new scheme is to split the other players into two groups of 6 and ask which group has an odd number of Mafia.

Because of the symmetry of the question scheme, each player is equally likely to be scum in the worst case. So you have a 5/13 chance of hitting scum with the first lynch, scum will have to eliminate one of the remaining possibilities, and then town has an EV of 3/4 (1/2 chance hitting scum again to narrow down to two possibilities with a mislynch still available; 1/2 chance to miss and narrow it to two without a mislynch available). If town miss day 1 (8/13), they have a 1/2 day 2, scum have to eliminate one possibility, and then a 1/3 to pick the correct remaining one for an EV of 1/6. That means a total EV of 61/156 (~39%) in the worst case. There's also only one set of results that hits this worst case (all no, for the particular set of questions I used here, with all yes impossible), so that 39% only accounts for one 99th of the possible scum groups. Probably the overall EV is over 50%? Would be a pain to calculate exactly (since you have to determine the best set of answers for scum for each scum group), and there's not much point doing that until I'm convinced it's the best we can do (both in terms of the max and in terms of the distribution; the average is just over 5, but I'm not sure yet whether it would be best EV-wise of have all of them 6 or less or to have a higher max with most other cases lower than 6).

[mith]

Well, already lowered it to 10 max just with one tweak of the groupings. The EV of each of the 10 possibility cases is already above 50% (19/30 = ~63%). I'm not sure that it's guaranteed that a case with fewer possibilities will have a higher EV (I explored a 9 possibility case with two players having 5/9 chance of being scum - you have to start with the right one to get your EV up to 70%; lynching the other one has an EV of 59%). But I'd guess you can get above 70% with this scheme.

Going to add more loops to my script to get the max for all schemes.

[mith]

Found a 9 (well, found six distinct 9s after accounting for symmetries); that's the lowest worst case. (For the cyclical schemes - that is, everyone groups the players the same way relative to themselves. The "simplest" is: if I'm player i, I'll group players i-3, i-2, i+1, i+2, i+3, i+4 mod 13)

At least in the first one I looked at, the best you can do appears to be an EV of 2/3 (5/9 for the first lynch and if it's right town can always win because scum has to eliminate a possibility; but for the 4/9 miss, scum has a free kill and will continue to do so no matter how town lynches). There's a lot of 9 possibility cases though, no idea if all of them are like this or only some (and if only some, whether scum can always force the 2/3 EV by steering the results).

[mith]

I realized I should go back and try the simplest version of this (just ask about the next player), and was surprised to find the max is 11 even for that. (Not a great EV for those 11 possibility cases though - 5/11, at least for the ones I've looked at.)

I still think we can do better by asking the questions sequentially and trying to eliminate the most cases. It's just a pain to actually prove.

[mith]

So, I ran an experiment of sorts with the following scheme:

1. Ask questions of the form: A asks B>C or B=C/D>E or ...
2. After each question is asked, if the number of remaining cases for no and yes are equal, choose a random answer. Otherwise, choose the one with the extra case (this may not be the worst case, but probably is?).
3. Set up the next question so that the first pairing is between the players least likely to be scum who have not asked a question yet (to maximally eliminate cases), and the second pairing to be between the players with the highest likelihood to to scum (to maximize one of those players and thus reduce everyone else a bit); otherwise, randomize the remaining players in the question until the no/yes split is equal.
4. Set up the questions so that if the questioner is not scum, the no/yes cases are equal (or as equal as possible).

Since I picked a random answer, there's no guarantee that my result is representative (but at least I am avoiding steering toward a best case). Anyway, for this test, I went through 10 questions, and ended up with 9 cases remaining. That's quite good as far as the information goes - on average, each stage left us with <61% of cases remaining (the first is worst, around 69%; the best was near the end, with player 10 only having two scumgroups remaining and cutting the possibilities from 23 to 13, ~56%).

The bottleneck with this approach is that the last few players are likely to be relatively scummy. The remaining players in this test are scum in 7, 6, and 6 cases respectively. That means if I were to continue picking the answer with more cases, we'll only be able to eliminate 1 from each question, leaving 6.

6 may be good enough if the cases line up perfectly (one player is scum in 5, one is scum in 4 of those, one is scum in 3 of those, and one is scum in 2 of those; a mislynch will immediately narrow it to one case, otherwise you're down to two with two chances). But if 6 is a typical result, it's not likely that it will *always* line up like that.

In this particular case, it didn't:

3 0 1 2 12
3 1 2 6 8
3 1 6 8 12
3 4 5 7 8
3 4 5 6 9
0 1 6 8 12

(Though we do have an EV of 5/6 here, so that's something.)

It's not obvious how to continue approaching this. We can't show a particular scheme like this works without going through all the yes/no possibilities (8192 in total, for 13 players), and we can't show no scheme works on the basis of one failure like above (maybe I choose the wrong question at some point).

The only way I see to prove a 100% win solution is to find some sort of symmetrical scheme that evenly distributes the cases (average is 5.02 or something like that, so mostly 5s with a few 6s) and does so in such a way that the likelihoods line up nicely.

[mith]

One thing I got curious about while doing this:

What if rather than each player having one question, the town as a whole got some number of questions (fewer than 13) and could vote to determine who would ask each (allowing repeats)? How many questions would they need to force a win?

(I suspect it can always be done with 11 questions.)

[mith]

In my experiment I reached that point after 7 questions, with 32 possibilities remaining - 3 more might have been enough if you could engineer the remaining 4 the right way, 4 definitely was.

I wasn't trying to optimize for that, though.