0:00

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,

Â 2:49

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.

Â