Optimal Doctor Strategy - Please Comment!

[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

[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

[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

[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

[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

[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

[mathcam]

Hm, I have to admit I'm a little skeptical of this result. I'll see if I can work out the theoretical probability and see how it relates. If it's close, it'll serve as good verification that everything's working.

So this is bascially the case where there two mafia, 6 townies, and no night-kills, right?

Cam