Noncooperative games in extensive form and public policy
In Chapters 4 and 5, our focus was on noncooperative games in strategic normal form. While (as von Neumann and Morgenstern showed) all games in extensive form can be represented in strategic normal form, to do so in general we may have to be careful to specify strategies as contingency plans. Thus, the strategic normal form will apply most naturally and with the best intuition to games in which simultaneous choices of behavior strategies must be made, such as the Prisoner’s Dilemma. Conversely, when some decisions must in fact be made before other decisions are made, so that subsequent decisions are made with knowledge of the earlier decisions, the game represented in extensive form may be more natural and intuitive. In this chapter we focus on the game represented in extensive form.
SUBGAME PERFECTION AND TREMBLING HANDS
Recall Game 2.2, Figure 2.1 in Chapter 2. We should notice that the decision by Firm A, to accommodate or retaliate, is a subgame in this game. Accordingly, we can define a behavior strategy locally at this decision point. The behavior strategy is just to accommodate or to retaliate, without specifying any conditions as to what previous decisions might be made. (Such conditions would be trivial in this case anyway.) In the spirit of Nash equilibrium theory, we might suppose that Firm A will choose the behavior strategy that leaves it with the larger payoff. This is “accommodate” for a payoff of 2 rather than 1. Moreover, the potential entrant, Firm B, can anticipate this. Therefore, Firm B expects that the payoff from the behavior strategy “enter” pays 1 while the behavior strategy “don’t” pays 0, and accordingly Firm B chooses “enter.” Thus the noncooperative solution to this game would seem to be “enter, accommodate.”
Four comments should be made on this reasoning.
First, it is an example of subgame perfect Nash equilibrium, a concept that is now central to the analysis of games in extensive form. A subgame perfect Nash equilibrium is a sequence of behavior strategies that (1) is a Nash equilibrium in behavior strategies in the game as a whole, and (2) is also a Nash equilibrium in every subgame. In this case, we have just one proper subgame, and that is Firm A’s decision whether to retaliate or accommodate. The fact that Firm A chooses the behavior strategy that maximizes its payoffs at that point means that we do indeed have a Nash equilibrium in this subgame. That Firm B maximizes its own payoff based on anticipation of that decision means that each firm is choosing its best response to the other’s strategy (sequence of behavior strategies); we have a Nash equilibrium in the game as a whole.
Second, the example illustrates an algorithm for finding subgame perfect Nash equilibria. The algorithm is called “backward induction.” In this case, notice, the first step is the last decision to be made, resolved by determining a Nash equilibrial behavior strategy as if the subgame stood alone. We then treated the first decision as a “reduced game” in which the payoffs were 0 for “don’t” and 2 - the equilibrial payoff in the first step - for “enter.” The Nash equilibrial decision for the “reduced game,” “enter,” then completes the subgame perfect Nash equilibrium. For more complex games and in general, the algorithm would be as follows: (1) Among all subgames, determine those that are basic. A basic subgame is one that has no proper subgames within it; in Game 2.2, Firm A’s decision is the only basic subgame. (2) Determine the behavior strategies that constitute a Nash equilibrium for the basic subgames. (3) If the Nash equilibrium is unique, form the reduced game by eliminating the basic proper subgames, replacing the basic proper subgames by their equilibrial payoffs. If the Nash equilibrium for a particular subgame is not unique, replace the subgame by one or another set of equilibrial payoffs. (4) Repeat until the reduced game is the first decision to be made, and determine the Nash equilibrial behavior strategies and payoffs for that decision. (5) The sequence of behavior strategies are then the subgame perfect Nash equilibrial behavior strategies, and the payoffs yielded by this sequence are the subgame perfect equilibrium payoffs.1 If one or more of the equilibria determined at stage 3 are non-unique, then the subgame perfect Nash equilibrium is non-unique.
Third, another way to express the result in this analysis is to say that the threat of a price war in this case is incredible. This recalls, yet again, Nash’s comment that a threat is often something that a person would not want to do for themself, and that is the case with respect to the price war in Game 2.2. In general, in noncooperative game theory, a threat is credible only if it is subgame perfect. If the threat is part of a subgame perfect equilibrium sequence of behavior strategies, then it is Nash equilibrial in the subgames of which it is a part, and if so then it is an exception to Nash’s comment - it is something the person would want to do for itself.
Fourth, the application in this case is itself very important for public policy and economics. It supports the argument that market entry is irrepressible in a market economy without government restrictions. Since entry tends to increase price competition and price competition in turn tends to induce efficient pricing and resource allocation, this would be an element of an argument for free market policies. On the other hand, if in a special case market entry were to have negative consequences, it could be an element of an argument for public policies that would restrict entry. Patent rights would be an instance of the special case.
Although we are concerned with the representation of the game in extensive form, it will be helpful here to digress on the strategic normal form. Recall the normal form of this game, Table 2.2 in Chapter 2. Notice that this game has four Nash equilibria: “don’t” with strategies 1 and 4, and “enter” with strategies 2 and 3. The latter two correspond to the subgame perfect Nash equilibrium, since both require Firm A to choose the behavior strategy “accommodate.” But the other two formally are Nash equilibria as well.
Is there any basis to exclude these equilibria? We do notice that strategies 1 and 4 are weakly dominated for Firm A. A strategy is weakly dominated if there is another strategy the payoff to which is never less, and is greater for at least one strategy that the other player might choose. Since behavior strategy “accommodate” pays 2 if Firm B enters, and 5 if Firm B does not, the contingent strategies leading to “accommodate” weakly dominate those leading to “retaliate.” Indeed, we see that this game has only three distinct outcomes: price war, accommodated entry, and continued monopoly. Behavior strategy “don’t enter” always leads to the same outcome, therefore to the same payoffs. In general, when we translate a game in extensive form into a game in strategic normal form, we will find that there are many fewer outcomes than strategy combinations, since many different combinations of contingent strategies will lead to the same basic subgames, and therefore to the same outcomes. Thus, weakly dominated strategies are likely to be quite common in games in extensive form. The question thus becomes: is there any basis to exclude equilibria that are based on weakly dominated contingent strategies?
In 1975, Selten (CGT, pp. 317-54) introduced a refinement of Nash equilibrium called the trembling hand equilibrium: suppose there is some small positive probability that a player will fail to choose his best-response strategy, so that the player will choose any other specific behavior strategy instead. This is a perturbed game. We can define equilibrium for the perturbed game in the usual way, with the expected values of payoffs determining the best responses. The equilibria of a perturbed game may differ from those of the original game. Now define a sequence of perturbed games in which the probability of errors approaches zero in the limit. Selten shows that the limit of the equilibria of such an (appropriately constructed) sequence of perturbed games is an equilibrium of the original game, but not all equilibria are the limits of such sequences. Those equilibria that are the limits of such sequences are perfect equilibria. This means that equilibria are excluded if they depend on behavior that is rational only on the assumption that other players are themselves perfectly rational.
In a perfect equilibrium, a Nash equilibrium is realized in every subgame of the original game, including of course the game itself. Thus a perfect equilibrium is, in particular, subgame perfect. In Game 2.2 revised, for example, suppose that the probability that Firm B chooses the “wrong” strategy is p. In such a case the payoff of contingent strategies 1 and 4 is 2p + 1(1 - p). The payoff to strategies 2 and 3 is 5p + 2(1 - p). Clearly the second is larger for any positive p, so strategies 1 and 4 are not best responses in any perturbed game. Consequently, the subgame perfect equilibrium of Game 2.2 is the only perfect equilibrium of Game 2.2 revised.
But the perfect equilibrium can also be applied to games that do not have subgames. As an example, Selten discusses the Horse game (Figure 2.3, Game 2.3, Chapter 2). As in Chapter 2 we will encode the behavior strategies as follows: for Firm A, “License” is R1, “Don’t” is L1, for Firm B, “Don’t” is R2, “Enter” is L2, and for Firm C, “License” is R3 and “Don’t” is L3. Notice that for this game, L1R2R3 is an equilibrium: but it is so only because Firm B does not get an opportunity to play at all. If Firm B were to get an opportunity to play, he would know that Firm A had not played L1 but R1 and, on an expectation that Firm C would play R3, Firm B’s best response is not R2 but L2. This is unreasonable, Selten argues, writing (p. 328) “Player 2’s choices should not be guided by his payoff expectations in the whole game but by his conditional payoff expectations” at decision node B. In fact, L1R2R3 is not a perfect equilibrium. In Game 2.2 revised, the Nash equilibria with contingent strategies 1 and 4 can be excluded because they are not perfect equilibria. As we noted, they are formally Nash equilibria, but their exclusion is very much in the spirit of Nash’s noncooperative game theory. Retaliation is a threat strategy, and would not be “something A would want to do, just of itself.” The term “perfect Nash equilibrium” is quite apposite: rather than restricting, Selten has perfected Nash’s reasoning.