[EV] Oracular Mafia

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:

Post Post #25 (ISO) » Thu May 31, 2018 8:04 am

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

Post Post #26 (ISO) » Thu May 31, 2018 8:37 am

Post by 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).
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #27 (ISO) » Thu May 31, 2018 8:48 am

Post by callforjudgement »

Huh, that's actually much lower than I expected, even on the condition that the groups have to be symmetrical.

I imagine in an actual game you'd use scumhunting to help aim the questions, so maybe this setup is less broken / more interesting than I thought.
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 #28 (ISO) » Thu May 31, 2018 12:28 pm

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

Post Post #29 (ISO) » Fri Jun 01, 2018 11:49 am

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

Post Post #30 (ISO) » Fri Jun 01, 2018 12:41 pm

Post by 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.)
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #31 (ISO) » Fri Jun 01, 2018 1:39 pm

Post by callforjudgement »

I think you'd have to start by figuring out how many questions (asked by different players) you need to confirm one player as town (which is also an interesting question in its own right). That seems like the first step in your strategy there.

The answer can't possibly be less than 5 (the number of scum), as if 4 scum asked questions and just lied about the results you'd have no way to know which of the remaining 9 players was the fifth scum. My guess is that it's probably 6, although I'm far from certain on this.
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 #32 (ISO) » Fri Jun 01, 2018 3:53 pm

Post by 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.
User avatar
mutantdevle
mutantdevle
Mafia Scum
User avatar
User avatar
mutantdevle
Mafia Scum
Mafia Scum
Posts: 3731
Joined: October 21, 2017
Location: Hell

Post Post #33 (ISO) » Sun Jun 03, 2018 5:54 am

Post by mutantdevle »

In post 0, callforjudgement wrote: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)
"Does player X know the alignment of a mafia member?"
"Does player X know my alignment?"
"Has player X used their ability yet?"

Of course, this is only useful if town doesn't out their information.
- Which on second thought I don't see why they wouldn't.
I mostly just lurk now.
User avatar
callforjudgement
callforjudgement
Microprocessor
User avatar
User avatar
callforjudgement
Microprocessor
Microprocessor
Posts: 3972
Joined: September 1, 2011

Post Post #34 (ISO) » Sun Jun 03, 2018 8:24 am

Post by callforjudgement »

Right, you can use it as an anti-gambit mechanism but I don't see why town would be gambitting in this setup anyway.
scum
· scam · seam · team · term · tern · torn ·
town
Post Reply

Return to “Open Setup Discussion”