纳什均衡

Draft chapter from An introduction to game theory by Martin J. Osborne Osborne@chass.utoronto.ca; www.chass.utoronto.ca/~osborne Version: 99/11/19. Copyright c© 1995–1999 by Martin J. Osborne. All rights reserved. No part of this book may be reproduced by any electronic or mechanical means (including photocopying, recording, or infor- mation storage and retrieval) without permission in writing from Oxford University Press, except that one copy of up to six chapters may be made by any individual for private study. 2 Nash Equilibrium: Theory Strategic games · Nash equilibrium · Best response functions · Dominated actions · Symmetric games. Prerequisite: Chapter 1. 2.1 Strategic games Astrategic game is a model of interacting decision-makers. In recognition ofthe interaction, we refer to the decision-makers as players. Each player has a set of possible actions. The model captures interaction between the players by allowing each player to be affected by the actions of all players, not only her own action. Specifically, each player has preferences about the action profile—the list of all the players’ actions. (See Section 17.5, in the mathematical appendix, for a discussion of profiles.) More precisely, a strategic game is defined as follows. (The qualification “with ordinal preferences” distinguishes this notion of a strategic game from a more general notion studied in Chapter 4.) � Definition 11.1 (Strategic game with ordinal preferences) A strategic game (with ordinal preferences) consists of • a set of players • for each player, a set of actions • for each player, preferences over the set of action profiles. A very wide range of situations may be modeled as strategic games. For exam- ple, the players may be firms, the actions prices, and the preferences a reflection of the firms’ profits. Or the players may be candidates for political office, the actions campaign expenditures, and the preferences a reflection of the candidates’ prob- abilities of winning. Or the players may be animals fighting over some prey, the actions concession times, and the preferences a reflection of whether an animal wins or loses. In this chapter I describe some simple games designed to capture funda- mental conflicts present in a variety of situations. The next chapter is devoted to more detailed applications to specific phenomena. As in the model of rational choice by a single decision-maker (Section 1.2), it is frequently convenient to specify the players’ preferences by giving payoff functions that represent them. Bear in mind that these payoffs have only ordinal significance. 11 12 Chapter 2. Nash Equilibrium: Theory If a player’s payoffs to the action profiles a, b, and c are 1, 2, and 10, for example, the only conclusion we can draw is that the player prefers c to b and b to a; the numbers do not imply that the player’s preference between c and b is stronger than her preference between a and b. Time is absent from the model. The idea is that each player chooses her action once and for all, and the players choose their actions “simultaneously” in the sense that no player is informed, when she chooses her action, of the action chosen by any other player. (For this reason, a strategic game is sometimes referred to as a “simultaneous move game”.) Nevertheless, an action may involve activities that extend over time, and may take into account an unlimited number of contingencies. An action might specify, for example, “if company X ’s stock falls below $10, buy 100 shares; otherwise, do not buy any shares”. (For this reason, an action is some- times called a “strategy”.) However, the fact that time is absent from the model means that when analyzing a situation as a strategic game, we abstract from the complications that may arise if a player is allowed to change her plan as events unfold: we assume that actions are chosen once and for all. 2.2 Example: the Prisoner’s Dilemma One of the most well-known strategic games is the Prisoner’s Dilemma. Its name comes from a story involving suspects in a crime; its importance comes from the huge variety of situations in which the participants face incentives similar to those faced by the suspects in the story. Example 12.1 (Prisoner’s Dilemma) Two suspects in a major crime are held in separate cells. There is enough evidence to convict each of them of a minor offense, but not enough evidence to convict either of them of the major crime unless one of them acts as an informer against the other (finks). If they both stay quiet, each will be convicted of the minor offense and spend one year in prison. If one and only one of them finks, she will be freed and used as a witness against the other, who will spend four years in prison. If they both fink, each will spend three years in prison. This situation may be modeled as a strategic game: Players The two suspects. Actions Each player’s set of actions is {Quiet,Fink}. Preferences Suspect 1’s ordering of the action profiles, from best to worst, is (Fink,Quiet) (she finks and suspect 2 remains quiet, so she is freed), (Quiet, Quiet) (she gets one year in prison), (Fink,Fink) (she gets three years in prison), (Quiet,Fink ) (she gets four years in prison). Suspect 2’s ordering is (Quiet,Fink ), (Quiet,Quiet), (Fink,Fink), (Fink,Quiet). We can represent the game compactly in a table. First choose payoff functions that represent the suspects’ preference orderings. For suspect 1 we need a function u1 for which u1(Fink ,Quiet) > u1(Quiet ,Quiet) > u1(Fink ,Fink ) > u1(Quiet ,Fink). 2.2 Example: the Prisoner’s Dilemma 13 A simple specification is u1(Fink,Quiet) = 3, u1(Quiet,Quiet) = 2, u1(Fink,Fink) = 1, and u1(Quiet,Fink) = 0. For suspect 2 we can similarly choose the function u2 for which u2(Quiet,Fink) = 3, u2(Quiet,Quiet) = 2, u2(Fink,Fink) = 1, and u2(Fink,Quiet) = 0. Using these representations, the game is illustrated in Fig- ure 13.1. In this figure the two rows correspond to the two possible actions of player 1, the two columns correspond to the two possible actions of player 2, and the numbers in each box are the players’ payoffs to the action profile to which the box corresponds, with player 1’s payoff listed first. Suspect 1 Suspect 2 Quiet Fink Quiet 2, 2 0, 3 Fink 3, 0 1, 1 Figure 13.1 The Prisoner’s Dilemma (Example 12.1). The Prisoner’s Dilemma models a situation in which there are gains from coop- eration (each player prefers that both players choose Quiet than they both choose Fink) but each player has an incentive to “free ride” (choose Fink) whatever the other player does. The game is important not because we are interested in under- standing the incentives for prisoners to confess, but because many other situations have similar structures. Whenever each of two players has two actions, say C (corre- sponding to Quiet) andD (corresponding to Fink), player 1 prefers (D,C) to (C,C) to (D,D) to (C,D), and player 2 prefers (C,D) to (C,C) to (D,D) to (D,C), the Prisoner’s Dilemma models the situation that the players face. Some examples follow. 2.2.1 Working on a joint project You are working with a friend on a joint project. Each of you can either work hard or goof off. If your friend works hard then you prefer to goof off (the outcome of the project would be better if you worked hard too, but the increment in its value to you is not worth the extra effort). You prefer the outcome of your both working hard to the outcome of your both goofing off (in which case nothing gets accomplished), and the worst outcome for you is that you work hard and your friend goofs off (you hate to be “exploited”). If your friend has the same preferences then the game that models the situation you face is given in Figure 13.2, which, as you can see, differs from the Prisoner’s Dilemma only in the names of the actions. Work hard Goof off Work hard 2, 2 0, 3 Goof off 3, 0 1, 1 Figure 13.2 Working on a joint project. 14 Chapter 2. Nash Equilibrium: Theory I am not claiming that a situation in which two people pursue a joint project necessarily has the structure of the Prisoner’s Dilemma, only that the players’ preferences in such a situation may be the same as in the Prisoner’s Dilemma! If, for example, each person prefers to work hard than to goof off when the other person works hard, then the Prisoner’s Dilemma does not model the situation: the players’ preferences are different from those given in Figure 13.2. ? Exercise 14.1 (Working on a joint project) Formulate a strategic game that models a situation in which two people work on a joint project in the case that their preferences are the same as those in the game in Figure 13.2 except that each person prefers to work hard than to goof off when the other person works hard. 2.2.2 Duopoly In a simple model of a duopoly, two firms produce the same good, for which each firm charges either a low price or a high price. Each firm wants to achieve the highest possible profit. If both firms choose High then each earns a profit of $1000. If one firm chooses High and the other chooses Low then the firm choosing High obtains no customers and makes a loss of $200, while the firm choosing Low earns a profit of $1200 (its unit profit is low, but its volume is high). If both firms choose Low then each earns a profit of $600. Each firm cares only about its profit, so we can represent its preferences by the profit it obtains, yielding the game in Figure 14.1. High Low High 1000, 1000 −200, 1200 Low 1200,−200 600, 600 Figure 14.1 A simple model of a price-setting duopoly. Bearing in mind that what matters are the players’ preferences, not the partic- ular payoff functions that we use to represent them, we see that this game, like the previous one, differs from the Prisoner’s Dilemma only in the names of the actions. The action High plays the role of Quiet, and the action Low plays the role of Fink ; firm 1 prefers (Low,High) to (High,High) to (Low,Low) to (High,Low), and firm 2 prefers (High,Low) to (High,High) to (Low,Low) to (Low,High). As in the previous example, I do not claim that the incentives in a duopoly are necessarily those in the Prisoner’s Dilemma; different assumptions about the relative sizes of the profits in the four cases generate a different game. Further, in this case one of the abstractions incorporated into the model—that each firm has only two prices to choose between—may not be harmless; if there are many prices among which the firms may choose, the structure of the interaction may change. (A richer model is studied in Section 3.2.) 2.2 Example: the Prisoner’s Dilemma 15 2.2.3 The arms race Under some assumptions about the countries’ preferences, an arms race can be modeled as the Prisoner’s Dilemma. (Because the Prisoner’s Dilemma was first studied in the early 1950s, when the usa and ussr were involved in a nuclear arms race, you might suspect that us nuclear strategy was influenced by game theory; the evidence suggests that it was not.) Assume that each country can build an arsenal of nuclear bombs, or can refrain from doing so. Assume also that each country’s favorite outcome is that it has bombs and the other country does not; the next best outcome is that neither country has any bombs; the next best outcome is that both countries have bombs (what matters is relative strength, and bombs are costly to build); and the worst outcome is that only the other country has bombs. In this case the situation is modeled by the Prisoner’s Dilemma, in which the action Don’t build bombs corresponds to Quiet in Figure 13.1 and the action Build bombs corresponds to Fink. However, once again the assumptions about preferences necessary for the Prisoner’s Dilemma to model the situation may not be satisfied: a country may prefer not to build bombs if the other country does not, for example (bomb-building may be very costly), in which case the situation is modeled by a different game. 2.2.4 Common property Two farmers are deciding how much to allow their sheep to graze on the village common. Each farmer prefers that her sheep graze a lot than a little, regardless of the other farmer’s action, but prefers that both farmers’ sheep graze a little than both farmers’ sheep graze a lot (in which case the common is ruined for future use). Under these assumptions the game is the Prisoner’s Dilemma. 2.2.5 Other situations modeled as the Prisoner’s Dilemma A huge number of other situations have been modeled as the Prisoner’s Dilemma, from mating hermaphroditic fish to tariff wars between countries. ? Exercise 15.1 (Hermaphroditic fish) Members of some species of hermaphroditic fish choose, in each mating encounter, whether to play the role of a male or a female. Each fish has a preferred role, which uses up fewer resources and hence allows more future mating. A fish obtains a payoff of H if it mates in its preferred role and L if it mates in the other role, where H > L. (Payoffs are measured in terms of number of offspring, which fish are evolved to maximize.) Consider an encounter between two fish whose preferred roles are the same. Each fish has two possible actions: mate in either role, and insist on its preferred role. If both fish offer to mate in either role, the roles are assigned randomly, and each fish’s payoff is 12 (H +L) (the average of H and L). If each fish insists on its preferred role, the fish do not mate; each goes off in search of another partner, and obtains the payoff S. The higher the chance of meeting another partner, the larger is S. Formulate this situation as a strategic game and determine the range of values of S, for any given values of H and L, for which the game is the Prisoner’s Dilemma. 16 Chapter 2. Nash Equilibrium: Theory 2.3 Example: Bach or Stravinsky? In the Prisoner’s Dilemma the main issue is whether or not the players will coop- erate (choose Quiet). In the following game the players agree that it is better to cooperate than not to cooperate, but disagree about the best outcome. Example 16.1 (Bach or Stravinsky?) Two people wish to go out together. Two concerts are available: one of music by Bach, and one of music by Stravinsky. One person prefers Bach and the other prefers Stravinsky. If they go to different concerts, each of them is equally unhappy listening to the music of either composer. We can model this situation as the two-player strategic game in Figure 16.1, in which the person who prefers Bach chooses a row and the person who prefers Stravinsky chooses a column. Bach Stravinsky Bach 2, 1 0, 0 Stravinsky 0, 0 1, 2 Figure 16.1 Bach or Stravinsky? (BoS) (Example 16.1). This game is also referred to as the “Battle of the Sexes” (though the conflict it models surely occurs no more frequently between people of the opposite sex than it does between people of the same sex). I refer to the games as BoS, an acronym that fits both names. (I assume that each player is indifferent between listening to Bach and listening to Stravinsky when she is alone only for consistency with the standard specification of the game. As we shall see, the analysis of the game remains the same in the absence of this assumption.) Like the Prisoner’s Dilemma, BoS models a wide variety of situations. Consider, for example, two officials of a political party deciding the stand to take on an issue. Suppose that they disagree about the best stand, but are both better off if they take the same stand than if they take different stands; both cases in which they take different stands, in which case voters do not know what to think, are equally bad. Then BoS captures the situation they face. Or consider two merging firms that currently use different computer technologies. As two divisions of a single firm they will both be better off if they both use the same technology; each firm prefers that the common technology be the one it used in the past. BoS models the choices the firms face. 2.4 Example: Matching Pennies Aspects of both conflict and cooperation are present in both the Prisoner’s Dilemma and BoS . The next game is purely conflictual. Example 16.2 (Matching Pennies) Two people choose, simultaneously, whether to show the Head or the Tail of a coin. If they show the same side, person 2 pays 2.5 Example: The Stag Hunt 17 person 1 a dollar; if they show different sides, person 1 pays person 2 a dollar. Each person cares only about the amount of money she receives, and (naturally!) prefers to receive more than less. A strategic game that models this situation is shown in Figure 17.1. (In this representation of the players’ preferences, the payoffs are equal to the amounts of money involved. We could equally well work with another representation—for example, 2 could replace each 1, and 1 could replace each −1.) Head Tail Head 1,−1 −1, 1 Tail −1, 1 1,−1 Figure 17.1 Matching Pennies (Example 16.2). In this game the players’ interests are diametrically opposed (such a game is called “strictly competitive”): player 1 wants to take the same action as the other player, while player 2 wants to take the opposite action. This game may, for example, model the choices of appearances for new products by an established producer and a new firm in a market of fixed size. Suppose that each firm can choose one of two different appearances for the product. The established producer prefers the newcomer’s product to look different from its own (so that its customers will not be tempted to buy the newcomer’s product) while the newcomer prefers that the products look alike. Or the game could model a relationship between two people in which one person wants to be like the other, while the other wants to be different. ? Exercise 17.1 (Games without conflict) Give some examples of two-player strate- gic games in which each player has two actions and the players have the same preferences, so that there is no conflict between their interests. 2.5 Example: The Stag Hunt A sentence in Discourse on the origin and foundations of inequality among men (1755) by the philosopher Jean-Jacques Rousseau discusses a group of hunters who wish to catch a stag. They will succeed if they all remain sufficiently attentive, but each is tempted to desert her post and catch a hare. One interpretation of the sentence is that the interaction between the hunters may be modeled as the following strategic game. Example 17.2 (Stag Hunt) Each of a group of hunters has two options: she may remain attentive to the pursuit of a stag, or catch a hare. If all hunters pursue the stag, they catch it and share it equally; if any hunter devotes her energy to catching a hare, the stag escapes, and the hare belongs to the defecting hunter alone. Each hunter prefers a share of the stag to a hare. The strategic game that corresponds to this specification is: 18 Chapter 2. Nash Equilibrium: Theory Players The hunters. Actions Each player’s set of actions is {Stag,Hare}. Preferences For each player, the action profile in which all players choose Stag (resulting in her obtaining a share of the stag) is ranked highest, followed by any profile in which she chooses Hare (resulting in her obtaining a hare), followed by any profile in which she chooses Stag and one or more of the other players chooses Hare (resulting in her leaving empty-handed). Like other games with many players, this game cannot easily be presented in a table like that in Figure 17.1. For the case in which there are two hunters, the game is shown in Figure 18.1. Stag Hare Stag 2, 2 0, 1 Hare 1, 0 1, 1 Figure 18.1 The Stag Hunt (Example 17.2) for the case of two hunters. The variant of the two-player Stag Hunt shown in Figure 18.2 has been suggested as an alternative to the Prisoner’s Dilemma as a model of an arms race, or, more generally, of the “security dilemma” faced by a pair of countries. The game differs from the Prisoner’s Dilemma in that a country prefers the outcome in which both countries refrain from arming themselves to the one in which it alone arms itself: the cost of arming outweighs the benefit if the other country does not arm itself. Refrain Arm Refrain