It turns out that extensive-form games with imperfect information give rise to subtly different classes of strategies. And in particular can make a distinction between behavioral and mixed strategies. And they're fundamentally very simple to explain. A mixed strategy is what is defined in a completely standard way. We have a notion of a pure strategy that is what each agent needs to do in all of their information sets and a that is a unique action in each of those information sets and a mixed strategy is simply a distribution over such pure-strategies. A behavioral strategy is slightly different. It says, rather than instruct with pure-strategies, it simply says, in each information set, how should you, should you randomize? It may seem very like the same thing. But it really isn't. And let's look at an example. So, take this, take, take, take this tree. And here's an example of a behavioral strategy. player one can do, take action A with probablility 0.5 and G with probability 0.3. What does that mean? That over here, the randomized 0.5, 0.5 and over here, the randomized 0.3, 0.7. That's a behavioral strategy. [COUGH] Similarly, a mix strategy here would be something like the following. It says, let's look at two pure strategies, for example, A,G will be one pure-strategy and B, H, B, H, will be another pure-strategy and let's look at some convex combinations, some mixture of the two, 0.6 of the one and 0.4 for the other. That will be a a mixed strategy. Now, although they are defined quite differently, one, looking at the example might think that well, one could really do the job of the other. And, in fact you'd be correct in this case. In a very famous result paper by Kuhn from 1953, it was shown that in, certainly, all these games of perfect information mixed strategies and behavioral strategies can emulate each other. There's no the payoff, the equilibria in mixed strategies are outcome equivalent to the equilibria in in behavioral strategies. In fact, it's not true only for games for perfect information, it's true for games with imperfect information, that is games with information sets where agents don't have full knowledge of where they are. So, long as those games have what's called perfect recall, a game of imperfect information has perfect recall if intuitively speaking, the agents have full recollection of their experience in the game. That means that wherever they are in each information set, they know all the information sets they visited previously and all the actions they've taken. To see an example of a game without perfect recall, consider the following game. So, Player 1 has here 2 nodes, this node and this node, and he can not tell them apart. And you can think of it as basically sending two agents, on your behalf, to play and neither agents know which of the two places it it landed in. and and particularly what the other agents agent did. Regardless of the interpretation it's the case that in the behavioral. so, so first of all, what are the pure-strategies in this case? Well, the pure-strategy for agent 1 is simply L and one can, in this information set, either do L or R. So, you either do L, which means you'd go here depending where you were or do R, and go here depending on where you were. This for agent 1. And for agent 2, there are, again, two pure-strategies. So what would be a mixed strategy equilibrium in this, in this game? Well, that turns out be fairly easy to analyze. And we start with the observation that player 2 has a dominant strategy. Play, play, play down. And so, no matter what the other player does, Player 2 is is no worse off. And in general, better of by playing D rather than U. And so a best response for Player 1 to Player 2 playing D, is playing R because they would get a payoff of 2 rather than a playoff of 1, if they played L. And so L, D is in fact a an equilibrium in this game. Notice the sort of the ironic or disconcerting fact that you have a very high payoff. That is actually not accessible under mixed strategies and that would be a hint about what's going to happen with pure-strategy, with behavioral strategies. So, what would an equilibrium in behavioral strategies look like here? Well, to start with, note that nothing has changed for Player 2, they still have a dominant strategy of D and let's assume they played that. What about Player 1 though? Player 1 has the opportunity to randomize a frish every time they found themselves in this information set. So, let's assume they randomize somehow going left with probability p and right with probability 1-p. What's assuming Player 2 plays D, what is their expected payoff given the parameter p? Well, with probability, with probability p times p, they will end up here and get a payoff of 1. So, that's p^2 * 1. With probability p*1-p, they'll end up here and get a path of 100. So, that's 100 times p times 1 minus p, with probability 1 minus p times 1. They will end up because this Player 1 is, Player 2 is not randomizing here. With probability 1-p, they will end up here and get a payoff of 2. That's 2*1-p. So, this is their overall payoff, assuming they randomize p. And we simplify it to this expression. And we simply look at the maximum here of this this, this equation and the and the and the maximum has arrived at this value. So, with probability slightly less than half, they go left and slightly more than half, they go right, that is Player 1. And so, we end up with this equilibrium where the the players, that Player 1 randomized in this way and Player 2 plays down the probability 1. So, we see that the equilibria with behavioral strategies is when we have imperfect recall, as we have here, can be dramatically different than equilibria with mixed strategies.
