There are two roads that lead from the local highschool to Adam’s home, both pass through some forest. Every day Adam has to choose which way to use. But Adam should be careful: Bill, the school bully, loves to ambush Adam at the forest and bully him. If Adam chooses the road where Bill lurks, well, poor Adam. If he chooses the other road, he gets home safely.

Up to now, all Adam can do is toss a coin when he leaves school to decide which road to choose. Indeed, if Adam uses one road more often, Bill could learn that, and wait on that road, thereby having more opportunities to bully Adam.

But not all is dark. Eve finishes school one hour before Adam, and goes home directly after school. If Bill meets her on his way, he forgets Adam and follows her. If Adam knew which way Eve took, he could take the same road and be safe. But he does not.

If Eve chooses her way randomly, all Adam could do is again toss a coin: if he happens to choose the same road as Eve, or if Bill happens to wait on the other road – he is safe. But if he happened to choose the road where Bill lurks, and Eve chose the other road, well, then unlucky Adam. So if Eve’s choices are independent, the probability that Adam will meet Bill decreases to 1/4.

We could describe the situation as the following three player game, where Bill chooses a row, Adam chooses a column, and Eve chooses a matrix.

Indeed, if Eve chooses the left road, and Bill chooses the left road, then Bill will follow Eve, and Adam will be safe (payoff 0) whichever road he chooses. But if Eve chooses the left road, and Bill chooses the right road, then Adam will be be bullied if he chooses the right road.

The situation would have been simple if Eve chose her road by a toss of a fair coin. But she does not. With probability p Eve chooses the same road she used yesterday, and with probability 1-p she chooses the other road (with p>1/2). Does this changes the strategic analysis?

Bill knows which way Eve took yesterday: either he met her, and then he knows that she took the same road he did, or he did not meet her, and then he knows that she took the other road. This means that he has probabilistic information about which road she will take today.

Adam, on the other hand, knows which road Eve took yesterday only if he met Bill: in that case he knows that Eve took the other road. If he did not meet Bill yesterday, then either Bill waited yesterday along the other road, or Bill waited along the same road that he took but Eve fortunately chose that road as well.

If Bill wants to minimize Adam’s payoff, his optimal strategy seems to be simple: he should choose each day the road that Eve did not choose on the previous day. Indeed, if he matches Eve he will not be able to bully Adam, so it is better to mismatch her. Though this strategy seems optimal it is not clear that it is indeed the case. This strategy reveals to Adam which road Eve took today, and so it increases the probability that he will choose tomorrow the same road as Eve will choose tomorrow. For some values of p it may be better for Bill to randomize.

Let’s change the assumptions on the information of Bill and Adam. Suppose that (a) Bill knows which way Eve is going to choose, and (b) when he gets home, Adam knows which way Bill chose, and he remembers his own choice, but he does not remember whether he was bullied or not. The calculation of the optimal strategy for both Adam and Bill (and the calculation of the value) is much more difficult. Why? If Bill always mismatches Eve, then because Adam knows which way Bill chose he can deduce which way Eve chose, and therefore he knows the way that she is likely to choose tomorrow. Because Bill mismatches Eve, he is better off taking the same road Eve chose yesterday, so Adam’s payoff is -(1-p), again, assuming p>1/2. If Bill ignores his information and plays randomly, then Adam’s payoff is -1/4, which is lower than -(1-p) for a range of p’s. The question is, then, what is the optimal way of Bill to use his information.

This question turns out to be not trivial, and for p close to 1 it is still open. I like games with incomplete information. I like games where the state variable changes (here the state variable is the road that Eve chooses). But they are so difficult to analyze. Anyone can give a shoulder?

## 1 comment

June 25, 2010 at 5:32 pm

Biweekly Links – 06-25-2010 « God, Your Book Is Great !![…] programming assignment. Though not related to "real" game, here is a neat post on Games with Incomplete Information […]