An article with a proof on optimal mafia play.

[LicketyQuickety]

OK so for all you nerds out there who are both genius and like math I have something you might want to look at:

http://projecteuclid.org/euclid.aoap/1211819786

[Ellibereth]

LOL THAT GUY WAS MY ADVISOR.

[Ellibereth]

I talked to Mark about this freshman year and I remember him saying that they actually had 0 to very little real mafia experience hehe.

[LicketyQuickety]

Wow that's pretty crazy. I don't get it tho. You joined MS in late 2009 and the Proof was written in 2008 I believe. Why was it a topic of discussion for you and him?

[Ellibereth]

Uhhh, I looked him up when he was assigned as my freshman advisor dude and then I asked him about it.

[LicketyQuickety]

Good I'm glad someone is familiar with this proof. Is there any chance you could explain it to some of us who are not all that into reading proofs in layman's terms?

[Kagami]

It's a very simple idea, the point of the paper isn't optimal mafia play, but rather the number of mafia necessary to have a "balanced" game with and without cops.

The paper assumes that any strategy the town could use can be perfectly emulated by the scum, and thus the optimal town play is to make a scheme whereby the lynch is decided randomly, since that ensures that scum can't use their own votes to manipulate the lynch, possibly giving them an advantage. Optimal scum play under this scheme is straightforward and also essentially random.

So the result isn't terribly interesting for us. Aside from the obvious criticism that real scum players are unlikely to be able to perfectly emulate town play, it ignores superior strategies that arise when the players play more than one game.

The best take-away is that the presence of investigative roles results in a massive shift in town power, which could be relevant to those mods/players who underestimate the importance of investigation.

[Psyche]

You got me all excited for a moment.

[Ellibereth]

Also the assumption is made that simultaneous statements are possible which isn't in any realistic setting zzz.

They wrote the paper as just some fun from playing around with the "mafia" model with no intent for any use in the actual game.

[Kagami]

Also the assumption is made that simultaneous statements are possible which isn't in any realistic setting zzz.

It's not really necessary for their scheme, you can generate sufficiently random numbers by devising an algorithm that is computationally difficult enough that it can't be computed fast enough for the scum to be able to manipulate it given that players make statements within some reasonable time period.

[chamber]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

[LicketyQuickety]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

The alternative to this is that Town suck on average.

[chamber]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

The alternative to this is that Town suck on average.

By what metric?

[chamber]

Looking in more detail, their first assumption for all vanilla games is something we explicitly don't allow.

[LicketyQuickety]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

The alternative to this is that Town suck on average.

By what metric?

Ok, so is it or is it not a proof? If it is then based on that we can say that what they say is optimal play. We can also conclude that games with more scum are actually more balanced. This all assumes of course that everyone in the game is an intelligent rational individual who is playing to their win con.

[chamber]

See my post 13. It's possible it's a valid proof given that assumption (I haven't read it all, I just read the brief initially, then started to read closer and found the bas assumption), but its meaningless for us, which matches my intuition for that number being junk.

[LicketyQuickety]

See my post 13. It's possible it's a valid proof given that assumption (I haven't read it all, I just read the brief initially, then started to read closer and found the bas assumption), but its meaningless for us, which matches my intuition for that number being junk.

OK so state exactly why it is no applicable here and please explain.

[chamber]

Their method requires a simultaneous reveal of a random choice. There is no means to accomplish that in the way that we play. They themselves admit that the strategy is wrong if the mafia can react to the results the town are giving.

(they also allow for private communication between residents in their proof)

[Psyche]

only because of pedit

[Kagami]

chamber, order root R does not mean root R.

[Kagami]

Their method requires a simultaneous reveal of a random choice. There is no means to accomplish that in the way that we play. They themselves admit that the strategy is wrong if the mafia can react to the results the town are giving.

(they also allow for private communication between residents in their proof)

It is very possible to generate provably random numbers without using 3rd party sources or /dice on our forums to achieve identical results as theirs.

As an example, a town with M mafia sets up the following scheme: once it's decided to lynch randomly, you ask the next M+1 players to post a number and declare that the those numbers will be used as the seed to some algorithm that is publicly available and takes significantly longer to compute than you'd expect it would take for M+1 players to post. You might choose something like the 10^12th number generated by the merseinne twister seeded with sum of the M+1 numbers. It would be entirely impossible for the mafia to fix the results, and the results would be publicly verifiable without breaking any rules regarding verifiable random numbers.

[Tere]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

Has that been proven?

Offsite we use root as a standard idea for what mafia is present as a vague guess (although in fairness it never ends up vanilla).

Curious as to if ever the root's been tested? (the question is not just for this poster, genuinely curious )

[LicketyQuickety]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

Has that been proven?

Offsite we use root as a standard idea for what mafia is present as a vague guess (although in fairness it never ends up vanilla).

Curious as to if ever the root's been tested? (the question is not just for this poster, genuinely curious )

I would love to play where you do off site. If you could PM me where you play that would be awesome. I'd love to shake things up there.

[LicketyQuickety]

root(R) Mafia where R = size of total population seems insane. That's 3.6 mafia in a 13 player game with no power roles. That's absolutely unwinnable.

It doesn't seem that off to me, but I just graduated from being a newb so what do I know.

[Kagami]

The balanced number of mafia for a mountainous game is very close to sqrt(num_players)/2