[EV] Oracular Mafia

This forum is for discussion of individual Open Setups, including theoretical balance.
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

[EV] Oracular Mafia

Post Post #0 (ISO) » Wed May 23, 2018 8:34 am

Post by callforjudgement »

Oracular Mafia
  • 8 Town 1-shot Day Oracles (can ask the moderator a true-or-false question about which players have which roles, will get a truthful answer)
  • 5 Mafia 1-shot Day Oracles (note: the action isn't useful as scum know the whole setup already, it just lets them figure out when the moderator's reply would arrive)


This is almost certainly broken, but I'm interested in how.

Can town get a 100% win rate?
What's town's best strategy in trying to get a
perfect
win (i.e. no mislynches)?
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
BBmolla
BBmolla
Open Book
User avatar
User avatar
BBmolla
Open Book
Open Book
Posts: 24301
Joined: May 29, 2011

Post Post #1 (ISO) » Wed May 23, 2018 11:18 am

Post by BBmolla »

I don’t understand, isn’t everyone’s role an Oracle? What true/false questions are being asked?
Come see me in the Great American Melodrama in Oceano
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #2 (ISO) » Wed May 23, 2018 11:26 am

Post by callforjudgement »

They can choose what questions they ask. Mostly about who's scum.

There's surely got to be some set of 13 questions you can assign the 13 players, and win based on the answers even if scum lie about what some of the answers were.
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
BBmolla
BBmolla
Open Book
User avatar
User avatar
BBmolla
Open Book
Open Book
Posts: 24301
Joined: May 29, 2011

Post Post #3 (ISO) » Wed May 23, 2018 11:42 am

Post by BBmolla »

So like “Is there 2 scum in Bob, Tom, and Sarah?”
Or even like “is Mikey scum?”
Come see me in the Great American Melodrama in Oceano
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #4 (ISO) » Wed May 23, 2018 11:44 am

Post by callforjudgement »

Right.
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
Invisibility
Invisibility
he or she
Jack of All Trades
User avatar
User avatar
Invisibility
he or she
Jack of All Trades
Jack of All Trades
Posts: 5911
Joined: April 17, 2018
Pronoun: he or she

Post Post #5 (ISO) » Thu May 24, 2018 6:50 am

Post by Invisibility »

can't it just be that everyone is assigned to ask if the person below them on the playerlist is scum? (with the person on the very bottom asking about the top player)

So town could have a 100% winrate
Invisibility is actually AWESOME!
Sukima
Sukima
Watcher
Sukima
Watcher
Watcher
Posts: 0
Joined: October 2, 2014

Post Post #6 (ISO) » Thu May 24, 2018 7:07 am

Post by Sukima »

Do Mafia have a nightkill or is this nightless?

Also the answers aren't public so the mafia can just lie or tell the truth with 50% odds obviously.
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) » Thu May 24, 2018 8:33 am

Post by 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.
Sukima
Sukima
Watcher
Sukima
Watcher
Watcher
Posts: 0
Joined: October 2, 2014

Post Post #8 (ISO) » Thu May 24, 2018 9:34 am

Post by Sukima »

Wouldn't you figure it's less reliable information than just going 8 bits because mafia can muddle the signals with 5 fake answers? Kinda like how you need more bits to be able to parity correct something than to just say that someone messed with the string?
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 May 24, 2018 11:03 am

Post by 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.
User avatar
Mathdino
Mathdino
Survivor
User avatar
User avatar
Mathdino
Survivor
Survivor
Posts: 14337
Joined: February 24, 2013
Location: Right Behind You

Post Post #10 (ISO) » Thu May 24, 2018 3:37 pm

Post by Mathdino »

It's pretty funny but like dethy, it's more of a logic game than a mafia game

I don't think it'd be super fun to play
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #11 (ISO) » Fri May 25, 2018 1:34 am

Post by callforjudgement »

In post 10, Mathdino wrote:It's pretty funny but like dethy, it's more of a logic game than a mafia game

I don't think it'd be super fun to play
Right, which is why I marked this as an EV thread ("solve the puzzle"), not as a setup thread ("I'm planning to run this").

As mith points out, you have to try to rely on the information coming from scum somehow (I used similar reasoning to pick the numbers in the first place). It's also a test of my theory that "WIFOM tends to cancel out", i.e. that scum normally do about as well going along with a breaking strategy pretending that they're town, and intentionally violating it and likely getting caught as a result; it's not necessarily shedding doubt on the theory (as I have no idea whether scum should lie or not), but rather pointing out something that I missed (that because town have to allow for both strategies, they get less useful information than if everyone was town
even if
scum tell the truth).

For what it's worth, the solution to this sort of puzzle is often to catch one scum at a time (because this allows you both to disregard their result, and to gain information from the scum nightkill after you've lynched the one caught scum). I can't see an obvious way to apply that principle here, though, especially as you effectively have to use all the Oracle shots Day 1 (to stop scum killing a player with an unused shot).
scum
· scam · seam · team · term · tern · torn ·
town
User avatar
Mathdino
Mathdino
Survivor
User avatar
User avatar
Mathdino
Survivor
Survivor
Posts: 14337
Joined: February 24, 2013
Location: Right Behind You

Post Post #12 (ISO) » Fri May 25, 2018 5:30 am

Post by Mathdino »

My bad, didn't see the tag!

Yeah finding equilibria for something as open ended as this is hell
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #13 (ISO) » Fri May 25, 2018 5:54 am

Post by callforjudgement »

OK, I think I've figured out how to analyse this sort of setup.

The trick is to look at how many scumteams are
ruled out
by each answer. If a player claims a particular Oracle result, then we know that either a) the claimer is scum, or b) the result is correct; so all the scumteams where the claimer is not scum and the result would be wrong are impossible. For example, suppose player A goes first in terms of asking a question; there are 792 scumteams that don't include player A, so with an optimal question, half of them (396) will be ruled out. So there are now only (1287-396 = 891) possibilities left for the scumteam.

You then take the player on the fewest of the remaining scumteams, and ask them to go next (as their information will have the most potential use); this won't be player A, who is on as many scumteams as possible. Each of the 891 remaining scumteams contains 5 scum, each player is on (891*5/13) = ~347.2 scumteams on average. That means that there must be some player who's on at most 347 possible scumteams (regardless of what question was asked, assuming it splits the scumteams into two equal halves). Call this player B. There are at least 544 possible scumteams which do not contain player B, and player B's question will eliminate 272 of them. That brings us down to (891-272 = 619) possible scumteams.

Unfortunately I'm not sure if the same sort of analysis can be continued, as I see no reason why it's necessarily possible to keep crafting questions such that the player on the fewest possible scumteams is necessarily a player who hasn't asked yet. If the same rate of scumteam reduction continues, though (which is far from certain!), we'd end up eliminating about 30% of the possible scumteams at each stage. That'd leave us with approximately 12 potential scumteams after all the questions have been asked. That's a large enough number that I'd now be surprised if a 100% perfect win strategy existed, unless it could somehow leave everyone as potential scum (so that the scum's nightkills necessarily eliminated some possible teams without the need to ask any more questions). It might also be possible to design the questions such that no matter the answer, some specific player's odds of being scum were drastically reduced (thus making that player's question more valuable), but that seems somewhat at odds with trying to split the remaining possibilities in half.
scum
· scam · seam · team · term · tern · torn ·
town
Sukima
Sukima
Watcher
Sukima
Watcher
Watcher
Posts: 0
Joined: October 2, 2014

Post Post #14 (ISO) » Fri May 25, 2018 7:21 am

Post by Sukima »

Isn't the average skewed because of A, and everyone else has the same probability of being on scum, assuming an even split of an optimal question? IE for the first iteration, aside from A, nobody else should have a better chance of being on a scumteam than anyone else?
Though, that just brought up a thought, where an optimal question can still have a nonuniform distribution of who is more clear or more scum in it. Something like where the optimal question from A removes most of the scumteams that involve B, so B is more trustworthy. The one question I have is how to be able to tell when someone is, in fact, scum, and thus you need to use the pool of people where A is in the scumteam.
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #15 (ISO) » Fri May 25, 2018 7:28 am

Post by callforjudgement »

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.
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 #16 (ISO) » Fri May 25, 2018 7:52 am

Post by 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. :)
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) » Fri May 25, 2018 8:31 am

Post by mith »

In post 15, callforjudgement wrote: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.)
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) » Fri May 25, 2018 8:40 am

Post by 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.)
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #19 (ISO) » Fri May 25, 2018 9:33 am

Post by 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.
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) » Tue May 29, 2018 6:15 am

Post by 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.
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) » Tue May 29, 2018 12:31 pm

Post by 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).
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) » Tue May 29, 2018 12:41 pm

Post by 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.
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) » Tue May 29, 2018 12:49 pm

Post by 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).
User avatar
mith
mith
Godfather
User avatar
User avatar
mith
Godfather
Godfather
Posts: 9267
Joined: March 27, 2002
Location: McKinney, TX
Contact:

Post Post #24 (ISO) » Thu May 31, 2018 7:25 am

Post by 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).
Post Reply

Return to “Open Setup Discussion”