“On the Interpretation of Decision Problems with Imperfect Recall,” M. Piccione & A. Rubinstein (1997)

Kuhn proved in 1953 that optimal strategies at each node of a game (a behavioral strategy) is equivalent to optimal play mixing over all possible strategies at the start of a game (a mixed strategy), if there is perfect recall on the part of each agent. If perfect recall does not hold, then the two are not equivalent and Nash equilibria will not necessarily exist in behavioral strategies. Piccione and Rubinstein give a great example of a problem where imperfect recall seems reasonable, and show that determining what the player should do, normatively, is not at all trivial.

Consider an absentminded driver heading home a highway with 2 stops. If he gets off at the first exit, he is in a bad neighborhood with payoff 0. If he gets off at the second exit, he gets home with payoff 4. If he gets off at neither, he receives payoff 1 from staying at a motel for the night. The driver is so absentminded that he does not remember how many exits he has already passed when he comes upon an exit. Note that there is only one information set when an intersection is seen. If he chooses “get off when I see an intersection”, he will get payoff 0 for sure, because he will end up getting off at the first exit. If he chooses “don’t get off when I see an intersection”, he will get payoff 1. But consider what happens when he actually gets to an intersection. With probability .5, he is at either the first or the second intersection (note that this assumption relies on a statistical Principle of Ignorance which you need not accept…), and therefore will get expected payoff 2 from exiting, hence he should exit. So the ex ante and interim optimal actions are not equivalent with imperfect recall. Mixed strategies do not solve this problem. The optimal mixed strategy is to exist with p=1/3, which gives 1/3*0+2/9*4+4/9*1=4/3. But the optimal behavioral strategy when an intersection is actually reached, assuming that the driver is playing the above mixed strategy and has a prior of .5/.5 on first and second intersection, is to exit once an intersection is seen. This is because, given a .5 prior and actions above, 3/5 of the time when he sees an intersection, it will be the first, and 2/5 of the time it will be the second. The payoff from exiting is .6*0+.4*4>4/3, so again the optimal mixed strategy is not optimal in behavioral strategies. It turns out that a way to restrict agents to actions that are optimal in behavioral strategies is to require a form of consistency of beliefs among “multiple selves” who are playing a game with each other at each potential intersection. It is not obvious that this is a sensible thing to do.

http://arielrubinstein.tau.ac.il/papers/53.pdf (There are also a series of responses to this article in GEB 20 (1997))

Advertisement