In everyday language we often distinguish between strategic and tactical behavior. Whereas tactical reasoning concerns what to do in a particular situation, the strategic point of view considers the whole picture, it is a long-term plan. In Game Theory, a strategy spans the longest possible time horizon, it is a recipe telling the player what to do in any possible situation. More precisely, since "situation" translates into information set in games with imperfect information, a pure strategy for a given player lists all possible information sets where the corresponding player has to move, together with a rule how to move in each of these possible information set positions. By choosing a pure strategy, the player decides on a plan how to play in all possible situations before playing. Even unlikely situations must be thought over in advance.
In real life, few people start a game prepared with a pure strategy. Rather they would start playing and then decide what to do whenever it is their term. So a pure strategy is maybe more a theoretical than a practical concept. However, since players would not reveal their strategies, even if they had one from the very beginning, but would eventually have to come to a conclusion in all situations they get in, other players or independent observers would not be able to decide whether a player plays with an a priori strategy or not. So we may as well assume that players have made all possible decisions already in advance.
Let's briefly see how you can list, count, and encode all pure strategies a player has in a given game. Since in principle every choice of a move in every possible information set is possible, the product of the numbers of choices taken over all information sets of that player is the number of that player's possible pure strategies. We encode strategies by first numbering all her information sets in an arbitrary way. We also abbreviate each choice by a single letter. Then a pure strategy for that player can be encoded as a n-letter word, where n is the number of her information sets, and the k'th letter of the word tells what alternative the player chooses at the k'th information set. If for example Ann has three information sets, the first and the last with two possible moves, say K, L and L, M, and the second with three possible moves, say M,O,P, then Ann has the 2·3·2 = 12 pure strategies encoded as "KML", "KMM", "KOL", "KOM", "KPL", "KPM", "LML", "LMM", "LOL", "LOM", "LPL", and "LPM".
In the VNMPOKER(2,4,2,3) example discussed on the previous page on the Extensive form of general games, whose extensive form is again shown below, Ann has two information sets. She either has a card of value "1" or a "2". In each case she has two choices, she can either raise ("R") or check ("C"). Therefore Ann has the 2·2=4 pure strategies "CC", "CR", "RC", and "RR". Beth has also two information sets, and also two choices in each of them, calling ("C") and folding ("F"), therefore she too has 4 pure strategies "FF", "FC", "CF", and "CC".
Example: LE HER*(2,4):
Ann has two information sets. She either has a card of value 1 or of value 2. In the first information set, she has two choices, she can either keep ("K") or swap ("S"). In the second information set she must swap. Therefore Ann has the 2 · 1=2 pure strategies "KK", and "SK". Beth has two information sets consisting of two vertices each, where Beth has a card of value 1 or 2 and Ann did keep her card, but Beth has in addition two more single-vertex information sets after Ann has swapped and Beth knows the values of both cards, Ann's and Beth's. Except in the second information set, where Beth must keep, Beth can keep or swap, so Beth has 2 · 1 · 2 · 2 = 8 pure strategies, namely "KKKK", "KKKS", "KKSK", "KKSS", "SKKK", "SKKS", "SKSK", and "SKSS".
Now remember that there were many extensive forms of the game. The smallest one,
the one to the right, was obtained by neglecting moves with only one option, and
cutting off perfect-information subgames.
Here Ann and Beth both have just one information set each,
and both have just two pure strategies.
But how could the same game have 8 pure strategies for Beth in the first extensive form, and 2 in the second one? Does the extend of choices we have depend on the description? Well, whether or not we list moves with only one option does not affect the number of pure strategies, but if we eliminate subgames we assume that the player will choose the backward induction options in this subgames, which of course limits the pure strategies available.
Some problems may arise with these pure strategies, as can be explained
in the game whose extensive form is displayed to the right. This game, a
2-round chicken, is analyzed in a different page in detail.
Adam has two information sets, which actually are single vertices. In each of them he has two
choices to stand firm ("H") or to chicken ("D"). So in principle Adam has four
pure strategies "HH", "HD", "DH", and "DD". However it doesn't seem to matter whether
Adam plays "DH" or "DD"---if he chooses "D" in the first information set,
then he will never arrive at the second information set. So no matter what he was
planning for that, it will never happen. The strategy not to go to college and later
accepting a professorship in mathematics at Harvard if offered, and the strategy not to go to college
and later not accepting that professorship if offered look different in theory,
and the second one looks rather impressive
("Look, I plan to decline a professorship at Harvard"), but in reality both are just the same.
If all players start the game armed with a pure strategy, then the outcome is already determined if all stick to their chosen strategy. And why wouldn't they---remember that the notion of a strategy already includes the notion of reacting to surprising moves of the opponents. To be more precise, nothing can surprise a player playing with a fixed strategy, since this strategy will tell what to do in any possible situations, in any possible information set of the player. Therefore, in this situation the players wouldn't even have to play their game. All they would have to do to determine the outcome, and therefore the payoffs, is to reveal their chosen strategies simultaneously. Therefore the maybe rather complex game can be reduced to a simultaneous game where all players have all their pure strategies as options. The advantage of this point of view is that simultaneous games are easier to analyze. The disadvantage is that there may be a huge numbers of strategies, as we will see later even in some simple games.
For the normal form, also called Strategic Form, we assume that we have a list of all possible pure strategies of all players. For each combination of pure strategies for the different players, the payoffs, or expected payoffs in case randomness is involved in the game, are displayed for the different players. In the case of two players, we get a bimatrix with two entries in each cell, the payoff for Ann and the payoff for Beth. For three players we would have a cube-like structure, or a bunch of bimatrices, with cells containing three entries each, and so on. Note that for simultaneous games pure strategies and moves are just the same, so the normal form is just the natural description of these games.
The reduced normal form is defined similarly, except that only reduced pure strategies (for all players) are taken. In some cases the reduced normal form may be considerably smaller than the normal form, but very often it is just the same.
Note that for simultaneous games the pure strategies coincide with the moves of the players. For purely sequential games of perfect information (with or without randomness) the solution found by backwards induction as described here yields a Nash equilibrium (in pure strategies) [Kuhn 1953]. So for these two types of games, there is no point in translating the extensive form into the normal form.
In our example LE HER*(2,4), Ann has the pure strategies "KK" and "SK", and Beth has the pure strategies "KKKK", "KKKS", "KKSK", "KKSS", "SKKK", "SKKS", "SKSK", and "SKSS" in the original extensive form. Let me show at one example, for instance "SK" versus "SKSK", how to calculate the entries of the normal form bimatrix. Actually, since the game is zero-sum, only Ann's payoffs have to be calculated. We play the game, and assume that both players stick to their chosen pure strategies. What can not be controlled are the random moves, therefore we have to consider all outcomes of the random moves. With probability 3/14, both get a value 1 card. According to her pure strategy SK, Ann swaps, therefore Beth faces her third information set. Playing SKSK, Beth has also to swap in this information set, and the expected payoff for Ann in that case is -2/3. With probability 4/14, Ann gets a value 1 card and Beth a value 2 card. Ann does swap again, but Beth, facing her fourth information set now, would keep, therefore Ann has a payoff of 1. With probability 4/14, Ann gets a value 2 card and Beth a card of value 1. Then Ann keeps her card, and Beth faces her first information set, where she has to swap. The resulting expected payoff for Ann equals 1/2. Finally, with probability 3/14 both players get a value 2 card, which means that none of them can swap and the payoff for Ann is 0. Together, the expected value for Ann when Ann plays strategy SK and Beth plays strategy SKSK is (3/14) · (-2/3) + (4/14) · 1 + (4/14) · (1/2) +(3/14) · 0 = 4/14 = 2/7.
Performing such a calculation for every pair of pure strategies, we obtain the following matrix of Ann's payoffs in this zero-sum game:
| KKKK | KKKS | KKSK | KKSS | SKKK | SKKS | SKSK | SKSS | |
| KK | 0 | 0 | 0 | 0 | -2/7 | -2/7 | -2/7 | -2/7 |
| SK | 4/7 | 3/7 | 3/7 | 2/7 | 3/7 | 2/7 | 2/7 | 1/7 |
For the smaller extensive form, we get a 2 × 2 matrix.
| K | S | |
| K | 0 | -2/7 |
| S | 2/7 | 1/7 |
To have more and larger examples, let us define more versions of Le Her:
LE HER*(S,r): is defined as LE HER*(2,4) except that we play with r cards of value 1, r cards of value 2, and so on, up to r cards of value S. Again swapping is not allowed with the highest value card, which has now the value of S.
Again allowing swapping with a highest card would not really change the game, since nobody would give away the highest card anyway. The only reason for us requiring it is to reduce complexity (if only slightly). However, the original Le Her game had another restriction: If a player decided to swap but would get a highest value card, then the swap is not executed. This classical Le Her game was played with 13 different values and four duplicates for each value. Bewersdorff [Bewersdorff, Chapter 39] discusses this game.
Let us in the following concentrate on LE HER*(3,4). Again there are some subtrees that can be analyzed separately and cut off. Then the pruned extensive form, with white diamond terminal vertices indicating the subgames, looks as follows:
Ann has two information sets---holding a card of value 1 or 2---with two options, and Beth has also only two information sets with two options in this extensive form, which has already seen considerable work. Therefore both players have four pure strategies, KK, SK, KS, and SS. The normal form is shown below:
| KK | SK | KS | SS | |
| KK | 0 | -8/33 | 0 | -8/33 |
| SK | 8/33 | 4/55 | 34/165 | 2/55 |
| KS | -2/55 | -8/55 | -2/55 | -8/55 |
| SS | 34/165 | 28/165 | 28/165 | 2/15 |
Note that in this compressed version of the extensive form of LE HER*(S,r), Ann would have S-1 information sets with two options in each. Beth has also S-1 information sets, where Ann did not swap, but in the uncompressed version there are even many more information sets. Thus both Ann and Beth have each 2S-1 pure strategies. So we get a 8 × 8 matrix for LE HER*(4,r), a 16 × 16 matrix for LE HER*(5,r), up to a 4096 × 4096 matrix for LE HER*(13,r).
MYERSON POKER: In this simple Poker variant, only one player (Ann) gets one card. Both Ann and Beth put one dollar in the pot. Ann gets a card from a stack of 4 Queens and 4 Kings and looks at it privately. Then Ann either checks, in which case Ann gets the money in the pot if Ann's card is a King, or Beth gets the pot otherwise. Ann can also raise by putting another dollar in the pot. Now Beth either folds, in which case Ann gets the pot, or Beth calls by putting also one additional dollar in the pot. If Beth calls, Ann gets the pot if she has a King, otherwise Beth gets the pot.
The extensive form of the game is shown to the right.
Ann has two information sets, being lucky and holding a King
or holding a Queen. In both cases she has the choice to raise or check,
thus she has the pure strategies "RR", "RC", "CR", and "CC". Beth on the other hand has
only one information set with the options to call ("C") or to fold ("F"), therefore
only two pure strategies "C" and "F".
The normal form of the game looks as follows. Remember that, since it is a zero-sum game, only Ann's payoffs are shown.
| C | F | |
| RR | 0 | 1 |
| RC | 1/2 | 0 |
| CR | -1/2 | 1 |
| CC | 0 | 0 |
|
Randomness is involved, all four distributions of "1s" and "2s" to Ann and Beth are possible and have the probabilities 3/14 or 4/14 as described above. Let's just give an example how the expected payoff for a certain pair of pure strategies, like RC versus FC, for instance, is computed: If Ann and Beth both get a "1", Ann raises and Beth folds, therefore Ann wins 2 units. If Ann gets a "1" and Beth a "2", Ann raises but Beth calls and therefore Ann loses 3 units. If Ann gets a "2" and Beth a "1", Ann checks and wins 2 units. Finally, if Ann and Beth both get a "2", Ann checks and it is a draw. Therefore the expected win for Ann for this combination of strategies is 3/14·2+4/14·(-3)+4/14·2+3/14·0=1/7. Doing this for all combinations of pure strategies, we get the normal form shown to the right:
|
|
All tools discussed for simultaneous games can be applied for all games given in normal form. We just replace the word "move" by "strategy". Each player simultaneously selects one pure strategy, submits it to the referee, who then can simulate the game according to the strategies and determine the outcome and the payoffs. Let us discuss some of the tools on our two examples, LE HER*(2,4) and LE HER*(3,4)
Remember that we produced several slightly different extensive forms for LE HER*(2,4), and got different normal forms. Let us discuss the larger one, this time the fractions replaced by approximate decimals.
| KKKK | KKKS | KKSK | KKSS | SKKK | SKKS | SKSK | SKSS | |
| KK | 0 | 0 | 0 | 0 | -0.29 | -0.29 | -0.29 | -0.29 |
| SK | 0.57 | 0.43 | 0.43 | 0.29 | 0.43 | 0.29 | 0.29 | 0.14 |
For LE HER*(3,4) we repeat the matrix of a simplified extensive form with rounded decimals:
| KK | SK | KS | SS | |
| KK | 0 | -0.24 | 0 | -0.24 |
| SK | 0.24 | 0.07 | 0.21 | 0.04 |
| KS | -0.04 | -0.15 | -0.04 | -0.15 |
| SS | 0.21 | 0.17 | 0.17 | 0.13 |
Remember that the maximin strategy is that that maximizes the minimum payoff.
|
Let's investigate the maximin strategy for Ann in the (sequential) VNM POKER(2,4,2,3) example discussed above. For strategy CC, all responses of Beth lead to the same expected payoff of 0. For strategy CR, the worst that could happen is Beth playing strategy FC with an expected payoff of 0 for Ann. Strategy RC would be countered by strategy CC with an expected payoff of -2/7 for Ann, an expected loss. Finally, strategy RR would have an expected payoff of 0 in the worst case, if Beth again responds with CC. So any of strategies CC, CR, and RR (but not the rather silly looking RC) could serve as maximin strategy, and the expected payoff guaranteed for Ann in all these three cases would be 0. |
|
For Beth, on the other hand, the expected payoffs are just the opposites of the numbers displayed in the matrix above---remember that VNM POKER is a two-person zero-sum game. That means that Beth would---in the worst case---expect a payoff of -2 for strategy FF, a payoff of -1/7 for strategy FC, a payoff of -13/7 for strategy CF, and a payoff of -2/7 for strategy CC. That means that Beth's maximin strategies would be FC, and Beth can guarantee a payoff of at least -1/7 in this way. Beth will lose money, but not too much.
If both players choose some of their maximin strategies, the results would either be draws or expected win for Ann of 1/7 units.
A strategy weakly dominates another one if it yields no smaller payoff than the other for each strategies played by the other players. It strictly dominates the other one, if the payoff is always larger. IEWD and IESD are defined as for simultaneous games.
|
In our VNM POKER(2,4,2,3) example, there is no strong domination among Ann's strategies, however strategy CC is weakly dominated by both the strategies CR and RR. Strategy RC is weakly dominated by strategy RR. Among Beth's strategies there is also no strong domination, but FF is weakly dominated by both FC and CC, and CF is also dominated by these two strategies FC and CC (remember that the payoffs for Beth are the opposites of the entries of the matrix). If we remove the weakly dominated strategies, we arrive at the submatrix shown to the right: |
|
Again, best responses to strategies and the best response digraph can be defined for any two-player game.
Also the notions of domination equilibria strategies, IEWD and IESD equilibria, and Nash equilibria (in pure strategies) transfer directly from simultaneous games. In the next section we will see that not all Nash equilibria derived in this way from the Normal form are relevant. Looking at the extensive form, only so-called subgame perfect equilibria" remain.
In the page on the extensive form we showed how subgames can be used to reduce the extensive form of a game, which, in turn, will also result in a smaller normal form than the normal form of the original extensive form. Since we are looking just on different representations of the same game, we should expect corresponding solutions in both normal forms.
Let us check this at the game with imperfect information shown to the right.
Ann makes a move first.
In one case the game is over, in the other case Ann and Beth move simultaneously.
Ann has two information sets with two moves in each, thus her pure strategies are
A1A3, A1A4, A2A3, and A2A4.
However, the reduced strategies are A1•, A2A3, and A2A4.
Beth has one information set and the pure strategies B1 and B2.
The reduced normal form is
| B1 | B2 | |
| A1• | 0, 2 | 0, 2 |
| A2A3 | 3, 1 | -2, -1 |
| A2A4 | 1, -2 | -3, -1 |
The extensive form has a subgame shown to the right.
This is a simultaneous game with the following bimatrix:
| B1 | B2 | |
| A3 | 3, 1 | -2, -1 |
| A4 | 1, -2 | -3, -1 |
Therefore we could cut off the subgame in the original extensive form, transforming the cut vertex
(indicated by the white diamond) into a terminal vertices with payoff 3 and 1, see the tree trunk to the right.
Of course, Ann will choose A2, with payoffs of 3 for Ann and 1 for Beth.
This is different to the normal form calculation above, where we got two possible outcomes.
The Nash equilibrium A1• versus B2 will not occur.
Now we got a problem.
This problem was resolved by Reinhard Selten, who described a way how and why one would consider only some of the Nash equilibria of games originally described in extensive form by looking at the subgames. A Nash equilibrium of the normal form is subgame perfect if it is a Nash equilibrium for every subgame. In our example, both A1• versus B2 and A2A3 versus B1 are Nash equilibria, but only A2A3 versus B1 is subgame perfect. It turns out that only the subgame perfect Nash equilibria are those that one gets by using the subgame cutting-off method described in the extensive form chapter.
Reinhard Selten was born 1930 in Breslau/Wroclaw. Grewing up in Hitler Germany as a half-jew was difficult and made Selten interested in Politics and Economics. After the war, he studied mathematics in Frankfurt, obtaining a Ph. D in 1961. He became interested in the new topic of Game Theory. In 1975 Selten introduced "trembling hand perfectness", another refinement of Nash equilibrium. He was professor in Berlin, Bielefeld, and Bonn.
| nuclear | conventional | |
| status quo | 2,2 | 2,2 |
| attack | 0,0 | 3,1 |