Optimal Doctor Strategy - Please Comment!

[Telamon]

Hey there!

I'm a mafia enthusiast and I have just discovered this wonderful forum! I'm an undergraduate student and I'm looking to do an independent research project this quarter on the application of game theory to Mafia. To this end, I have written a Mafia Simulator and AI testbed to generate empiracle statistics from thousands of games (since for large games with many different roles, determining the expected citizen win percent or game length seems impractical if not impossible).

Anyways, on to my question. Right now my mafia simulator plays vanilla games of mafia with only citizens and mafia (no special roles). I thought I would add a doctor role next, since it seems like a simple step. I am having trouble, though, determining the optimal doctor strategy in a game where the doctor is the only special role.

For the sake of argument, let's assume a game of 10 players, with 2 mafia and 8 citizens (1 of whom is the doctor). The obvious doctor strategy is to always save yourself - no other citizen is more worth saving (they have no special roles) and you might save a mafia by accident otherwise. Is this the optimum strategy? I thought so at first, but now I am not so sure.

Argument: Assume both citizens and mafia are rational and the doctor is always saving themselves. If during the night the mafia try to kill someone who doesn't die - that person must be the doctor. Being rational, the mafia will never try to kill that person again. Net citizen gain: 1 save.

Counter Argument: What if after a night when no one dies, the doctor realizes that the mafia is never going to try to kill him again? Then it makes more sense for him to randomly select another person to save, resulting in an average saving rate of 1+ saves. But if the mafia is rational, they would realize the doctor will do this, and try to kill him on a subsequent round.

It seems to me that the best strategy in the light of this counter argument is for the doctor to always save himself - until no one dies at night, then decide to either save someone else at random or save himself - having a K percent chance of doing either. What is K? It seems like this should be solvable.

Further complication: What happens in a game where the mafia is not required to kill at night? Could they not kill on purpose, so that the doctor starts randomly saving other people, thus making the doctor more vulerable? I suspect this is not an optimal strategy for the mafia, since it effectively nets the citizens 1 save.

Please comment. I've never actually dealt with game theory before and I'm unsure to how find critical points like K except by simulation.

[Malaprop]

A nice writeup on the "he knows that I know that he knows that..." problem is here.

Best strategy for doc on an early nights is to protect the most experienced and best mafia-finding players first, then whoever is doing a good job at finding scum. Yes, I know this isn't really modelable. This is, in a nutshell, why I like mafia so much -- very little numerical analysis possible, different from most all games I've played.

[SaberKitty]

here

(the fixed link from above)

usually, doctors are not allowed to protect themselves

[Yoko Kurama]

"usually, doctors are not allowed to protect themselves"

That or they are limited to the number of times they can protect themselves.

[jeep]

I have written an analysis program that includes cop revealing information when it is the "right" play to do so and has what I believe to be a good doctor simulator. It does not adequately handle multiple killing groups yet.

Currently it handles:
arbitrary number of mafia (one will claim cop and suffer an anti-Lepton's lynch, if it's the best play)
arbitrary number of townies
arbitrary number of masons in an arbitrary number of groups
one doc well or multiple docs playing identical strategies
one cop that reveals if odds for town win is greater if he does

It assumes perfect play. We are no where near to having perfect play in any game, yet.

Optimal play, assuming you cannot target yourself, depends on the situation. In game with only townies, mafia, and a doc (which I played in), I feel that I played the optimal night strategy, but screwed up the day towards the end. I protected IS (a high probability kill target) every night. Towards the end, I knew he had never been targetted, so knew he was mafia. However, I didn't not come out strongly enough, early enough. I waited until it was 3 alive and then came out as doc (but no one else knew there was a doc in the game...). I had the most information other than IS and messed up.

The situation above would be trivial to simulate... I might do so tomorrow if I get some time.

-JEEP

[mathcam]

I think this could be done theoretically as well. For different strategies, compute the expected number of saves the doctor will get (really, this should then be correlated to the expected probability of the town winning). Then it's just a matter of enumerating all possible strategies, which is easy as well. But it sounds like just getting the answer isn't really what you're looking for...you want to apply game theory to it.

My hunch is that you are partially correct above: The doc should protect himself until the first night with no kill, and after this there's some kind of a mixed strategy (70% chance protect yourself, 30% protect someone else at random) that turns out to be optimal.

But as others have pointed out, in most formulations of the doctor role, he or she can't target themselves. But that's a less interesting question, so take what you want from that.

Cam

[Quiller]

And of course all these strategies lead to meta-strategies. Is it the best for doctors to protect the best player? Then the mafia will eliminate the others. In addition, about 20-35% of the time (depending on set-up), the best player will actually be mafia or SK.

[shadyforce]

In my experience, mafia kill one of, but not the, best player in the game. Thus, the doctor should calculate himself who (in his/her opinion) the top 4 players are in the game, and assign each a percentage, such as this:
#1: 10%
#2: 40%
#3: 30%
#4: 20%
And randomly protect one of the above weighted on their %. Knowing this fact won't really change much unless it is obvious that this doc-protecting strategy becomes commonplace.

[mathcam]

DP certainly raises a valid point for in-practice determination of who to protect, but this also doesn't really weigh in to the calculation of the town's optimal strategy. The mafia can always choose to kill randomly. Plus, if you're just running simulations, there is not best player.

I had a relatively boring seminar yesterday, and think I made pretty good progress on figuring out optimal doc strategy when the doc is allowed to self-protect. I'll post my thoughts when I finish.

I wonder if Telamon is ever going to come back and look at this....

Cam

[cuban smoker]

Grr, this is nagging at me. In the situation described above with 1 doctor who can protect themselves, I think its pretty clear that protecting himself until there is no kill is the best strategy, if you cannot identify players that are more likely to die. However, if you can identify more likely targets ala shadyforce, then it would almost invariably change the doctor strategy.

Until a clean night. Now the Mafia knows who the doctor is, and we've been thinking about what the doctor should do now. But now the mafia know who the doctor is! So if we assume the doctor may start protecting other people, that means the Mafia have a non-zero chance of killing the doctor, if they attack him again. This takes us back to the original doctor strategy. By randomly protecting other people, he may trick the mafia into thinking the wrong person is the doctor. Also, anyone he protects at night who doesn't die that night is cleared... he's a pseudo-cop!

Does that toss a monkey wrench in this pure game theory approach? I thinkers it might.

[Telamon]

Thanks for your thoughts everyone. I have three comments...

1. On the subject of protecting the best player. I'm not sure this is a good strategy. I have played mafia with the same group of 10-ish people for the past year, so you can get a feel for the kind of things different people tend to do in the game, but it's really hard to say who the "best" player is. In my experience it's hard to say that someone is quantitatively better at mafia than someone else. I consider myself to be a good player, but I've definitely lead the citizens to ruin my fair share of times as well. If you play in games where people tend to follow the best player, then the mafia focuses more energy leading him astray. So it seems like there is an equilibrium. Anyways, when my group plays online these days, we use pseudonyms so that, at least for the first couple of rounds, metagaming on the basis of who a person is doesn't happen (we hold that it is lame).

2. Mathcam: I agree with your assessment that after the first night with no kill, the optimal doctor strategy is mixed between self-saves and other saves (probably something like 9:1). My suspicion is that the mafia strategy of abstaining from killing to make the doctor change his strategy is not optimal - but I can't prove it. Any ideas?

3. Jeep: That sounds like an interesting program - do you have a webpage someplace that showcases the results of some of your experiments? It would be handy to compare results to make sure mine is working 100% correctly. Also, I would be interested in how you designed it. One issue I have run into that I'm not sure yet how to solve is knowledge representation. Right now my simulation doesn't involve any conversation between players other than lynch votes and accusations, but I would eventually like to add some.

[Telamon]

Additional Thought:

cuban smoker brings up an interesting point.

If the doctor saves someone in this setup, he knows they are not mafia. If he comes out with this information to the citizens, and they believe him, this is to their advantage. However, revealing himself is a disadvantage, especially since he now has the burden of protecting himself and the known citizen. This probably greatly reduces the doctor's effectiveness, if the mafia then begin to kill randomly.

Further complicating this mess - in this case I believe the optimal strategy is heavily dependent on the number of players left. In a game where the citizens could be about to lose, the doctor should obviously speak up. In a game with 12 people that just started, the best thing to do might be to stay quiet unless the guy he knows is a citizen comes up for lynching.

Further complicating the mess - in any strategy where the doctor comes out, it may be in the mafia's best interest to counter-claim the doctor role. Then what?

[Wacky]

"For the sake of argument, let's assume a game of 10 players, with 2 mafia and 8 citizens"

Whether this setup is publicly known to all players is also a factor.

Whether the strategy of the doctor is known to the mafia is also a factor. (e.g. the tricking mafia, the realising someone is a doctor...)

EDIT: This applies to most of your other queries as well. Many strategies might not work as well if the other side knows you are using that specific strategy, so a more optimal strategy would be to pick a good strategy at random..?

Oh, BTW, in your simulations is no-lynch allowed? That also has an influence on things.

[mathcam]

I think all of these concerns are addressed by my approach. Let me outline the approach now, even if I haven't finished computing all the results:

We inductively calculate the probability of the town winning a game with t townies, d docs, and m mafia left, depending on when we start: either day (D) or night (N). Let

E[t,d,m,D]=denote the probability that the townies will win the game using optimal strategy if there are t townies left, d docs left, m mafia left, and the game starts in day.

and

E[t,d,m,N]=denote the probability that the townies will win the game using optimal strategy if there are t townies left, d docs left, m mafia left, and the game starts in day.

Then we're going to build up some solutions. The first non-trivial examples are

E[2,0,1,D]=1/3 (the town wins only when they lynch the mafia, which occurs 1 out of 3 times)

E[1,1,1,D]=1/2 (the town can guarantee themselves a 50/50 shot by having the doc claim, and the mafia can choose between counter-claiming and remaining silent, each of which leave the odds at 50/50).

Now we have to work backwards through all possibilities: To compute E[1,1,1,N], for example, we do a conditional probability argument based on who the doc and mafia randomly choose to protect.

E[1,1,1,N]=(1/3)E[1,1,1,D]+(1/3)E[1,0,1,D]+(1/3)E[0,1,1,D],

which since the last two terms on the right are 0, give us E[1,1,1,N]=1/6.

And so on. For these small cases it doesn't matter, and just makes the notation in confusing, but in general, you need another term in your probability: E[t,d,m,D/N,r/h] for whether or not the doc is revealed or hidden. I think it becomes pretty clear that for E[n,1,1,N/D], the doc's optimal strategy is to come out, and then constantly protect himself. And this becomes more and more true as n approaches infinity. Even if they lynch wrong

every

time until it's down to 3 people, they've still guaranateed themselves a 50/50 shot.

Thus, to determine optimal doc strategy at a particular state, you just need to see what the possible outcomes of that strategy are, and give them weights according to the probability that the town wins if the doc chooses that strategy. Do this for all possible strategies, and the one with the highest value wins. Then you assume that the doc

does

perform this strategy, and this allow you to assign an expected value of the town winning to the current day, which allows you to proceed with the calculation, moving backwards one day.

I've done the next few calculations, encompassing all 4-player possibilities, and made some progress on the 5-player case, and if I have to go to another boring seminar, maybe I'll finish offf the 5-player case. It's pretty clear that the results could be generalized. My hope is that there's some kind of inductive relationship, something like

E[n,d,m,N,r]=n/(n+d+m)E[n-1,d,m,D,r]+d/(n+d+m)E[n,d-1,m,D,r]+....

though slightly more complicated.

As a final note, it's interesting and disappointing to find out that I haven't yet discovered any cases where a mixed strategy becomes optimal. Hopefully this happens as the number of players increaes, as that would be really cool.

Cam

[mathcam]

And at least in my setup, no lynch is allowed, the game setup is known (this is definitely a requirement), and once the optimal doc strategy is known, the mafia will anticipate it. So the optimal doc strategy has to be optimal even if the mafia knows he is going to do it...this is the classical definition of minimax optimal play from game theory.

Cam

[cuban smoker]

Hoo hoo... I love how math has wiggled its way even further into Mafia. First we had statistics, now we're working on inductively proving an optimal strategy. I like it.

Somehow you need to work in the... oy, I need to work on this myself before I can add to much more to this discussion. Are you doing this by hand, cam, or are you working on a simulation?

[korais666]

In response to your "1" comment, I have to disagree. If you are playing with the same group for years, it would make sense that you would all be roughly equal skill level. However, that is definately not the case here. Generally, the better players are the ones who have played the most games are the best, but even that is not entirely true.

The players who are most likely to catch the mafia are the players with the best ability to read between the lines and analyze character. There are definately more skilled and less skilled people. Of course, it's hard to tell how good newbies are, so I tend to kill one of the most experienced players first, or someone who did a lot to catch the mafia in other games.

[mathcam]

I was doing it by hand for now. I was hoping that a pattern would be clear (the inductive step I mentioned above) and then letting the computer generate the numbers for me for larger number of players. I wouldn't say I'm simulating anything, though.

Cam

[Telamon]

Mathcam:

I agree with your analysis of the base cases, but I'm having trouble convincing myself of some of your conclusions (not that they are necessarily, wrong - but at the very least some are counter-intuitive).

In particular, I take issue with the statement:

"I think it becomes pretty clear that for E[n,1,1,N/D], the doc's optimal strategy is to come out, and then constantly protect himself."

Which, if I understand what you are saying, means that in a game of 20 players, with 1 mafia, and 1 doctor - the best thing for the doctor to do on the first day is reveal himself. This flies in the face of general doctor-playing wisdom. It's often considered best not to reveal your role unless you must. Maybe for this setup, though this wisdom doesn't apply. However, my intuition screams that there is a superior strategy in this case - the one I originally outlined. The doctor saves himself until no one dies at night, and then switches to a mixed strategy strongly baised towards self-preservation. In the case of accusation, the doctor reveals himself and in the case of mafia impersonating the doctor, the doctor reveals himself. In an (n+3,1,1) game, this is a citizen win (they lynch both claimants).

Maybe the way to think of this is in terms of citizen saves that the doctor makes, since the chances of the citizens winning is directly correlated to this value (with the complication of the citizen odds changing on the basis of whether the number of players is odd or even - see the mafiacum theory article). In any case, every doctor save prolongs the game, and my simulations of vanilla mafia show that citizen chances of winning increases with with game length (I'm sure this can be demonstrated analytically as well).

My point is, that instead of attempting a complicated inductive approach, it is probably possible to adjust the odds for a vanilla mafia game by adding the expected number of citizen saves to the citizen's initial numbers to determine how the presence of a doctor effects the win percentage.

So for example, using pseudo-hypothetical numbers:
If the citizen win percentage for a game with 3 citizens and 1 mafia is 25% (game starting with Day), and if we then consider the case where one of those citizens is a doctor, who with a given strategy acheives E

citizen saves during the course of the game, the odds of the citizens winning the game with a doctor is equal to that of a game with 3 + E

citizens, 1 mafia and no doctor.

No one has mentioned the complication that when the number of players in a mafia game (call it n) is even, the citizens always have a better chance of winning with one fewer (n-1) players. So it seems like the optimal doctor strategy for the rounds when the number of players is even is the strategy that HAS THE LOWEST E

. On odd rounds, the highest possible E

is desired.

Open question: can E

> 1? Mathcam's argument indicates not. I argue that it can. If the doctor saves himself 100% of the time, once the mafia determines who the doctor is (by trying to kill him), E

= 1, and they will not try to kill him again, since they know he is always saving himself (note: if the doctor comes out before the mafia try to kill him, E

= 0, which seems to contradict Mathcam's conclusion above that the doctor coming out is always best). If the doctor switches to a mixed strategy after the mafia have tried to kill him and fail, the number of citizen saves acheived can certainly be greater than 1. However, this does not necessarily mean that E

> 1 in this case, because s can only be greater than 1 here in the case that the mafia has chosen to kill the doctor, which will not always happen in a game.

I'll admit I'm a little confused about the key issues at this point. Mathcam, you may be completely correct - your inductive approach does look like it could solve some of these problems (particularly the odd/even problem). I'm not sure about most of my claims in this point - I'm thinking about hunting down a computer science professor at office hours to help settle the issue in my mind.

[mathcam]

Well, you've certainly hit the key points. Let me respond point-by-point:

1) I too originally thought that measuring the expected number of doc saves for each given strategy would be a good way to do it. But this is clearly inferior to the measurement of how each strategy effects the probability of the town winning, for exactly reasons you mention: the even/odd is a problem with the "number of saves" appraoch, and

then

you have to find the exact correlation between number of saves and probability of winning, which could get pretty messy.

2) Certainly it is possible that some strategies have E

>1. I suppose that my argument is that E

=1 for the optimal strategy. I'll discuss this below.

3) I'm by no means positive of my claim of the fact that the doc revealing and then self-protecting every night is optimal. But let's do the computation: In your case, we have 20 players, one of which is a doc, and one of which is a mafia, and we'll start in the day. Suppose the doc reveals himself. Obviously, the mafia does not counter-claim. Also obvious is the fact that the mafia will never target the doc. Thus, for the mafia to win, he has to survive 8 lynches just to get it down to a 50/50 shot. For the first lynch, he has an 18/19 chance of doing so. Assuming he does do, and kills over night, the next day he has a 16/17 chance. All together he has a

(18/19) * (16/17) * (14/15) * (12/13) * (10/11) * (8/9) * (6/7) * (4/5) * (1/2) = %21.9

chance of winning. Although I'm too lazy to compute the expected chance of the mafia winning under the "keep self-protecting until there's no night kill, I suspect it's higher than this. Why? The mafia still has to dodge all those kills, and if the doc ever dies, then the last factor is going to be a 2/3 instead of a 1/2. I feel like the doc performing saves is pretty common and not even that useful.

4) But your argument has made a good point. In fact, my proposed strategy is clearly inferior to:

The doc still always self-protects, but doesn't reveal unless: a) He is on the lynching block, or b) He wakes up and finds there have been no night kills. He reveals himself in either of these cases, and continues to self-protect.

This strategy has the slight benefit overy my original one if the number of starting players is odd, I think...there's a slight chance that the doc can stop one mafia kill.

Cam

[Telamon]

Mathcam:

Your last argument makes it pretty clear that self-protect is always the best strategy, because the last term goes to 50% from 66%. I really appreciate your input on this.

Now that the basic doctor strategy has been nailed down, it makes figuring out the strategies for doctor variants rather easy.

My mafia group got tired of lame doctors saving themselves, so we made up an "Agnostic Priest" role. It's basically a doctor that can save anyone except for themselves . I'm sure other people have come up with this idea as well, and I'm not claiming to be the first. But I did invent the clever name

[Caveman]

Actually, your "Agnostic Priest"

is

the standard mafia doctor role.

[mathcam]

Yeah, as was mentioned several times in the top part of this thread, the standard doc role we play with on this site (and, as far as I know, the most common doc role played in real-life games) is one that cannot self-protect.

This just turned out to be a more interesting question...if a doc can't target himself, I'm pretty sure his theoretically best play is to target at random each night.

Cam

[Telamon]

Well, if the doctor can't self-protect - his only option is to save other people. In the abscence of any other information, all his saves are essentially random. There is only one strategy. I don't see how that is very interesting, unless you bring other information in.

In my simulation I am building suspicion networks, which tracks the extent to which each player is suspicious of each other player. In addition I am writing a probabalistic proposition evaluator that will assess how likely a particular statement is (like "Joe is the doctor" or "Bill is not the sheriff and not mafia"). Maybe with resources like these the question of who to save at random becomes less random and more interesting - at least that is my working assumption.

[Telamon]

Additional Interesting Fact:

I've been doing some more simulations. Here's a quick mafia quiz - What are the citizens' odds of winning in an 8 player game, with 2 mafia, and 6 doctors? (the doctors are allowed to self-save).

Scroll down for answer....








































































The results of a 1000 trials says it's only 43%.


Isn't the unbelievable? In a game where the mafia cannot successfully kill anyone, the citizens still lose more often than not by lynching all of themselves.

Before doing this simulation, I myself has guessed the citizens would have had at least a 90% chance of winning.