A pure strategy is something like advice, written in a notebook, a overprotective father gives his child for the first day of middle school in the big city. In order to be a pure strategy, this advice has to cover every possible situation the child could get in, and describe clearly and precisely what to do in each of these situations. Many of these situation will never occur, maybe by chance, or maybe since the other players don't play the corresponding moves leading to that situation, or maybe since the child plays some moves preventing the situation to occur---some situations can be avoided by the child, others cannot. Still the strategy prepares the child for every possible situation.
A mixed strategy means that the father gives his child a set of such notebooks, and advises to shuffle them and choose one randomly, according to a given probability distribution before leaving for school. In one play (day), the child would still take only one notebook to school, but would still be unpredictable. Note that one single random choice suffices to show different behavior in a variety of different situations.
A behavior strategy works still differently. Again the advise is written in a notebook and covers every possible situation. But in every situation, instead of giving clear advise, the notebook would list all possibilities and assign probabilities to them. This is not done to encourage personal choice of the child. The same as mixed strategies, the purpose of it is to let the other players in the dark about what the player will play. Hence, in each such situation the child would use a random device, like a pair of dice, the father has put into the child's bag to determine what option to choose., Thus for every one of the child's moves, there would be a random process required.
If you think that behavior strategies are closer to the way humans would play a game, be careful! Don't confuse behavior strategies with a player waiting what happens, and then deciding on the spot, using information locally available. There is nothing "local" about behavior strategies. Each of these decisions the child makes is, although random, depending on the probabilities given in the notebook, and these probabilities, although referring each to a single situation, all are computed with the whole game in mind. They are computed globally and in advance. Also there is nothing spontaneous in a behavior strategy. No matter whether a player has decided on a pure or mixed or behavior strategy---from that moment on there is no room left for an own will.
Whereas mixed strategies refer to the strategic/normal form of the game, behavior strategies refer to the description in extensive form. A behavior strategy for a given player describes for each of her information sets a probability distribution---probabilities for the different options at that information set adding up to 1.
Take (VNMPOKER(2,4,3,2), analyzed in the previous chapter,
as an example. The extensive form of the game is displayed again.
Ann has two information sets---the red dashed curves, and Beth has also two information
sets. Ann's information sets depend on Ann's card, whether Ann holds a "1" or a "2",
and Beth's information sets depend on Beth's card.
An example for a behavior strategy for Ann
would be to raise in 30% of the cases and therefore to check in the remaining 30% of the cases
when holding a "1", and to raise in 80% of the cases and bet in 20% of the cases when holding
a "2".
Of course it seems natural to use mixed strategies when the game is given in normal form, and behavior strategies when it is given in extensive form. However, as we have seen in the page on Normal Forms and Strategies, extensive form games can be translated into normal form, so which one should we use then? Very often, behavior strategies are easier to describe, since there are usually much more mixed strategies than behavior strategies. This is an advantage, but couldn't it also be a disadvantage? If there are more mixed strategies, isn't it possible that there are very good mixed strategies that have no counterpart in behavior strategies? We will see below that this not the case.
But before that, let me justify the claim on the numbers. Assume a player has n information sets, each with 2 options. If there are more options, the numbers are even more tilted towards mixed strategies. Then the player has more than 2n pure strategies. A mixed strategy is described by a assigning a probability for each of these 2n pure strategies, so it is described by 2n numbers. A behavior strategy, on the other hand, is described by only 2·n probabilities: The two probabilities for the two moves in each of the n information sets. Note that 2n is much larger than 2·n. Although the picture could differ, since there may be much fewer reduced pure strategies than pure strategies, in general games have fewer behavior strategies than mixed strategies.
Ann has three information sets. The first is the starting positions, where she chooses between the options A1 and A2. The second consists of two vertices, where she has the options A3 and A4, and the third also has two vertices with options A5 and A6. Beth has also three information sets. The first one consists of two vertices and has options B1 and B2, the second one is a single vertex set with options B3 and B4, and the third one again has two vertices and options B5 and B6. There are also two random moves of "Nature".
The reduced strategies for Ann are A1A3•, A1A4A5, A1A4A6, and A2••. Remember that the symbol "•" is a placeholder meaning that any option available at the corresponding information set could be used (since in practice this information set will not occur when playing this strategy). Beth's reduced strategies are B1•B5, B1•B6, B2B3B5, B2B3B6, B2B4B5, and B2B4B6.Every behavior strategy can be modeled by a mixed strategy: What we need is to define the probabilities of the pure reduced strategies for each player. Recall that such a pure reduced strategy is a sequence of move choices for each of that player's information sets. Each of these selected move choices has a certain probability in the given behavior strategy. Then the probability that the player will decide as in the pure reduced strategy in all situations is just the product of these probabilities. In case of an unreachable information set, indicated by the symbol "•", we multiply by 1. The reason why we have to take the product of these probabilities is that the decisions about the different moves in the different information sets are independent choices.
As mentioned already, there are more mixed strategies than behavior ones. So mixed strategies can be distinguished in a finer way than behavior strategies. Mixed strategy allow coordination between the choices in different information sets.
Let me illustrate this at the above VNMPOLKER(2,4,2,3) example. As noted already repeatedly, Ann has four pure strategies: "RR" to raise in every case, "RC" to raise with a card of value 1 and check with a "2", "CR" to check with a card of value 1 and to raise with a "2", and "CC" to check in any case. Look at two different mixed strategies. Now consider two mixed strategies. The first one uses 50% of "RR" and 50% "CC". The second mixed strategy uses 50% of "RC" and 50% of "CR". A bystander would observe that Ann would pass in 50% of the cases when she has "1" and in 50% of the cases when she has a "2" in both mixed strategies. That would also be her observed behavior strategy in both cases. Actually the observer would not be able to distinguish both mixed strategies, their difference is the different kind of coordination, which cannot be observed but only revealed when allowed to ask questions. Ann, when playing the first mixed strategy and having raised, would answer the question "What would you have done if you would have had the other card" by an "I would also have raised", and an Ann, playing the second mixed strategy and having just raised would answer by "I would have checked".
Now we want to translate mixed strategies into equivalent behavior strategies. Note that this is only possible in games with complete recall, which means the rather reasonable condition that every player completely remembers everything she may have learned in the past of the game including her own moves.
Now assume a mixed strategy for Ann is given. We want to find an equivalent behavior strategy for Ann. Look at a fixed information set I of Ann. We look at the different vertices of that information set. Ann doesn't know which one of these vertices she actually faces---after all, this is the definition of an information set. Although the moves of the other players and of Nature so far may not be known to her, she recalls all her own information sets she did face---let's call this her information sets history---and she recalls all her options she did choose in these information sets---the options history. Therefore she can exclude all vertices with different information sets history or different options history. Note that we are considering only game trees here, therefore both these histories are unique for every vertex. That means that all vertices of the information set we focus on are reached by the same sequence of Ann's decisions---like "first choose option A3 in information set 2, then choose option "A7 in information set 6, and then choose option A13 in information set 5." In this case the information set history would consist of information sets 2, 5, and 6.
In order to define the probabilities for the different options in this information set I, we look at all pure strategies that agree with I's options history on I's information set history. All their probabilities are added to form a number M. Then, for every option Aj of our information set I, we add the probabilities of those pure strategies agreeing with I's option history on I's information set history, and choosing Aj in information set I. This sum is abbreviated by Nj. Then p(Aj)=Nj/M.
In the second example considered, let us conversely translate Ann's mixed strategy P(A1A3•)=0, P(A1A4A5)= 3/10, P(A1A4A6)= 3/10, and P(A2••) = 2/5, which is another Nash equilibrium mixed strategy for Ann, into a behavior strategy. Note that Ann's first information set has no history, the second one has the first information set with move A1 as history, and the third one has both other information sets with moves A1 (in information set 1) and A4(in information set 2) as history.
What would Ann do in the first information set? We consider all pure reduced strategies. We add the three probabilities P(A1A3•), P(A1A4A5), and P(A1A4A6) for pure reduced strategies choosing A1 to get the probability 0+3/10+3/10=3/5 for A1. In the same way P(A2) = P(A2••) = 2/5.
The second information set can only be reached when Ann chooses A1 in the first information set, thus in only 3/5 of all of Ann's reduced strategies. Then
The third information set could only be reached when Ann plays first A1 and then A4, therefore in only 3/5·1 = 3/5 of Ann's reduced strategies. In the same way we get
This correspondence between mixed and behavior strategies can be summarized as follows:
Theorem [Kuhn 1953]: In every game with perfect recall, every behavior strategy is equivalent to one or infinitely many mixed strategies, and every mixed strategy is equivalent to exactly one behavior strategy.