Optimal Sheriff Strategy - Please Comment!

[Telamon]

As I explained in my "optimal doctor strategy" post, I'm working on a mafia simulation program. I would like to ask people's thoughts on the optimal strategy for the sheriff in a game with only normal mafia, regular citizens, and one sheriff.

Assume that all the players in the game are using pseudonyms, so that you cannot simply check the players who are known to be good as mafia first.

The crux of the issue: If there is no other special roles in the game, as soon as the sheriff reveals himself and is accepted by the citizens, he is dead meat, as the mafia will obviously kill him ASAP.

I suspect that the optimal strategy changes with the number of people left in the game. In a large game, (say 20 players, with 3 mafia) if the sheriff finds someone, he might be able to afford to sit on his information. As long as he is not drawing attention to himself otherwise, the mafia only have a 1/17 chance of killing him at night. In a medium sized game with only two mafia, however, it seems like trading the sheriff for a mafia memeber is a good trade (based on some simulations of vanilla mafia it looks like it increases the citizen's chances by about 30%). In the extreme case of a very small game, where lynching the wrong person results in instant doom for the citizens, the sheriff's best strategy is to come out with all of his info, reducing the chances the citizens will err in their lynching.

There's one more thing I think might need to be considered (I'm sure I'm missing some other cases, as well). What happens in a large game after five rounds of a sheriff only finding citizens? If he comes out with who he knows is a citizen, the citizens will be able to lynch much more accurately. Also, there will be too many validated citizens for the mafia to kill them all very quickly - so this is a long term citizen advantage. At what point should the sheriff come out in this case?

I am most interested in an analytical solution to this problem, but would also be interested in hearing about how these situations tend to play out for people in practice.

Thanks for your thoughts!

[Flying Dutchman]

Antrax has written an article on this site about numbers, this is mentioned there:

Which is better, being on the Town’s side, or on the Mafia’s?

Ah. That is a truly interesting question. I’ve written a simulation. First of all, of a game of 20 players (3 Mafia). Every day, the program lynched someone at random. Every night, it killed someone at random. The Mafia won with this setup 68% of the time. Then I added a “Cop”, which was more like a suicide bomber. My “Cop” would each night check someone. If that someone was Mafia, he got them lynched the following day, and then got killed at night by the Mafia. With this simplistic setup, the Mafia won only 32% of the time!
The next step was adding the Mafia members “not voting for each other”. To do that, I gave the Mafia a chance of 1 in (Town_alive-Mafia_alive) of having someone else lynched, every round. That brought the Mafia win percentage up to 74%, even with my suicide bomber Cop. The conclusion I drew from all that is that (as expected) there is no definite answer to this question. Too much relies on the setup of the game, as well as on the performance of single players. Otherwise, it would be pretty boring, wouldn’t it?

[Norinel]

I think jeep said something like this in the doc strategy thread, but if it's publicly known that the cop is the only non-townie role in the game, he can calculate the probability of the town winning given random lynches and kills (After a cop claim, going for the cop, then confirmed innocents). If the probability if he claims would be higher than the probability given no claim, claim.

The cop role allows for more interesting strategy on the part of the mafia as far as claiming it and causing doubt by leaving the real cop alive and such.

[mathcam]

It would be amusing in a 8-player endgame with 1 cop and 3 mafia left, if the 3 mafia and the cop all claimed cop (say the game had been going for some time and the mafia know that the cop must have pegged at least a couple of them). The town would have to be pretty lucky to win....nailing all 3 mafia in a row would have probability 3/4 * 2/3 * 1/2=1/4. Whereas if the cop were not counter-claimed, and the cop came out pegging 2 evil, the town has better odds.

Cam

[cuban smoker]

The simple idea behind optimal cop play is to come out when the town gains from the information immediately more so than they stand to gain by waiting, just as Norinel put it. The cop should definetely come out once half the town is on his list, that's a guaranteed win. Also, with a smaller amount of mafia, after finding one mafia the advantage of coming out early is much greater.

However, a mafia counter claiming cop toughs this up a bit to an extent I think we all understand.

I aslo like to take this one step further. Imagine a mafia claims cop first. Then the cop should seriously consider coming out to denounce the claim, in order to catch the mafia. Lynch the first one, mafia, and we have a confirmed cop, right? What if the second person who comes out is ALSO Mafia. Now we have a mafia who's confirmed cop and a cop hiding in the shadows. When does he come out? Immediately? Probably.

So which one is the cop? You can't confirm one of two or more cop claims is the cop until they are dead.

Now, the indcutive solution that mathcam suggested in the other thread would have to include all the 3 people cases where each person had been "cleared" by various cops, and whether any of the mafia had claimed. This could get ridiculously confusing, even in the smallest games.

[mathcam]

Yeah, I agree. I think the right way to think about the middle chunk of your post is to realize that either it's going to be optimal strategy for the cops and mafia to claim or it's not (or some mixed strategy)...in either case, it will all be done simultaneously. The one exception is that the real cop might not come out unless the fake cop claims it.

But yeah, lots of complications. That's why I was happy to work on the doc case...much nicer.

Cam

[jeep]

Cop is actually easier to program.

-JEEP

[the silent speaker]

The town would have to be pretty lucky to win....nailing all 3 mafia in a row would have probability 3/4 * 2/3 * 1/2=1/4.

I don't think this is right. All four people are not only claiming cop but announcing their results, right? So the second lynch is no longer purely random and the third lynch is still less so. Having hit a maf the first time, anyone who claimed him innocent is a known liar, and the odds are higher for people who claimed him guilty that the real cop is one of them. (I assume we are assuming all cops to be sane? Allowing for four possible alignments could

really

tangle up the math.)

[Sauron]

The town would have to be pretty lucky to win....nailing all 3 mafia in a row would have probability 3/4 * 2/3 * 1/2=1/4.

I don't think this is right. All four people are not only claiming cop but announcing their results, right? So the second lynch is no longer purely random and the third lynch is still less so. Having hit a maf the first time, anyone who claimed him innocent is a known liar, and the odds are higher for people who claimed him guilty that the real cop is one of them. (I assume we are assuming all cops to be sane? Allowing for four possible alignments could

really

tangle up the math.)

Super thread necro! Anyway, presumably the scum would know this one, and would also be aware and just call each other, or some subset of each other, guilty. It seems to me, in this hypothetical, the point is no longer to hide so much as to make sure the cop is every bit as much as viable a lynch. I think it'd work.

[Netopalis]

You pulled off a 6 year necro for that?

[Battousai]

Cop should always claim if the next day will be lylo if the current day's lynch is a mislynch, but only if at least one of the players investigated is still alive.

[Glork]

And here I thought all these old-timey folks were back in action.


Jerks.

[Sauron]

You pulled off a 6 year necro for that?

It stood as the last post of the thread, as if it was authoritative in some way. Besides, I thought a 6 year necro would be humorous.