static complete games

This version: 8. March 2021 University of St. Gallen Dennis Gärtner Course Nr.: 4,200 | 4,202 Microeconomics III Supplementary Notes for: 2.1 Static Games, Complete Information This part deals with static games. These are easiest to think of as games in which players choose their actions simultaneously. As we will more formally see later on, what is crucial for our purpose is that no player has a chance to react to anything that some other player does. Examples of static (bimatrix) games (slides 4-9). These slides give you some examples of games be-tween two players where players simultaneously pick one of two actions – some of which will surely be familiar (such as the timeless classic, the prisoners’ dilemma). The examples are meant to give you an idea of the many flavors that games might have even in this small class (2 players, 2 actions each), specifically regarding elements of “conflict”, “coordination” and “efficiency”. Beyond that, a crucial point to realize here is that, as relates back to our previous discussions of players’ preferences (under certainty and uncertainty): payoffs in these (bi-) matrix games simply represent preferences over outcomes. The distinctive new thing being that outcomes now depend on own and others’ choices! Definition: games in strategic form (slide 10). This is important in order to understand concepts and notation which follows! I recommend that, until it becomes second nature to you, with every (static, complete info) game you encounter, you return to this slide and ask yourself: who are the players? What are players’ available strategies? And what are players’ preferences/payoffs? In many later ap-plications/exercises, this will take you a big (if not the biggest) step toward solving the problem! To connect to concept which you might already know: notice that the concept of a game (and game theory itself) is closely related to the concept of “externalities”. Externalities refer to the idea that one player’s choice/action affects the wellbeing/utility of some other player. And this is key to any mean-ingful game: a game with no externalities, i.e. where players’ payoffs are entirely independent of oth-ers’ actions, in fact again boils down to entirely separable rational choice problems for each “player”! Equilibrium concepts (slide 11). This is an overview of what we intend to achieve under the heading “equilibrium concepts”. Realizing that you will have seen some (or all) of these concepts in action al-ready, the explicit aim here (and on the following slides) will be: 1. to alert you to the fact that (in contrast to optimization theory/rational choice theory), there are *different* concepts for prediction (positive) or advice (normative); 2. to make clear that there is no right or wrong concept, to understand their strengths and weak-nesses (assumptions concerning rationality vs. precision of prediction) and how their predic-tions relate; 3. to define and understand these concepts in a way which lets you apply them to quite generic games, e.g. beyond just 2-player bimatrix games. Strict dominance, graphical depiction (slide 13). A useful way to graphically depict (and sharpen intu-ition for) what “strict dominance” is all about is: imagine listing all possible strategy profiles for other players, 𝑠𝑠−𝑖𝑖, on the horizontal axis, and then plotting player 𝑖𝑖′𝑠𝑠 payoff for her two strategies 𝑠𝑠𝑖𝑖′ and 𝑠𝑠𝑖𝑖′′, as a function of other players’ strategies 𝑠𝑠𝑖𝑖′. If 𝑠𝑠𝑖𝑖′ strictly dominates 𝑠𝑠𝑖𝑖′′, this will look something like this: Note: These notes were written in Spring 2020 to help make up for cancelled lectures. I am shar-ing them this year because you might find them useful. However, please note that they are not kept up to date, so some references (to slides, events, etc.) may well be outdated. 2 Reinterpretations of the prisoners’ dilemma (slide 16). This is always a fun slide because it makes clear just how widely applicable (and timeless) the insights of the prisoners’ dilemma are, whether it’s concert crowds, certain politicians “putting their country first”, or people claiming that the fight against global warming can be won “if we all just do our share”, i.e. without coordination at the national and international level. And there are always new examples popping up: if you’re intrigued by the prison-ers’ dilemma which routing apps à la Waze, Google Maps supposedly induce, check out the study for Los Angeles in: J. Thai, N. Laurent-Brouty and A. M. Bayen, "Negative externalities of GPS-enabled routing ap-plications: A game theoretical approach," 2016 IEEE 19th International Conference on Intelli-gent Transportation Systems (ITSC), Rio de Janeiro, 2016, pp. 595-601. doi: 10.1109/ITSC.2016.7795614 (https://ieeexplore.ieee.org/document/7795614). In all of these examples, a great exercise is for you to identify the structure of preferences which is required in the specific context to get the prisoners’ dilemma argument to unfold. For instance, what would concertgoers’ preferences have to look like to have them wind up in a prisoners’-dilemma type situation?1 As you work through these examples, you might start to wonder about ways in which players might avoid these different dilemmas. In some cases, a (benevolent) third party might be able to simply elim-inate “problematic” options: the state could prohibit sales or ownership of SUVs, concert organizers might forbid standing, and routing apps might change the code of their app. When such an outright elimination of options is not available, you might hope that players themselves could somehow nego-tiate an agreement to choose certain dominated actions: states might negotiate trade agreements, disarmament treaties, climate treaties etc. And while these are perfectly valid ideas, it is important to bear in mind that this would immediately imply a larger and dynamic game, namely one in which the above game is preceded by some form of negotiations, and followed by some sort of implicit or explicit sanctions whenever the agreement was not honored. That is material for later chapters. For the mo-ment and at this point in our analysis, the no less meaningful insight is that whenever players are literally limited to playing such a game, without negotiation and enforcement, rational choices will lead them into a dilemma. Example: Hotelling’s location game (slides 20-23). This is not an easy example and will take some time to really digest and understand, but it serves an important function: to take the concept of iterated elimination beyond the simple world of 2-player matrix games (even though, as hinted at on slide 22, you *could* in principle write this game down in a very large matrix). The most important step (beyond identifying the game’s elements: players, strategies, preferences – see above) is to recall the definition of what it means for a strategy to be dominated, and to simply translate this notion into the specifics 1 Answer: Given anything your neighbors do, you prefer standing to sitting, but: you prefer everyone sitting to everyone standing. (The first times around, chances are that you might even have to convince yourself that these requirements are not contradictory.) 3 of the game at hand. More specifically, you should (yourself) complete the statement: “In this specific game, we say that, for player A, choosing location 𝑥𝑥𝐴𝐴=0 is dominated by choosing location 𝑥𝑥𝐴𝐴=1/𝛾𝛾 if…” Once you have this condition down and understand it, checking that it holds is actually the much easier part. 2 By the way: if you find yourself troubled at first by the generic formulation concerning any 𝛾𝛾+1 evenly space positions (𝛾𝛾≥2 and even), there’s nothing wrong with starting with 𝛾𝛾=2 (which gives a nice 3x3-matrix in which you can check/replicate all the general arguments. A good question to ask yourself here (and to check your understanding) is: In the *original* game (with no positions eliminated), why is location 𝑥𝑥𝐴𝐴=1/𝛾𝛾 *not* strictly dominated by location 𝑥𝑥𝐴𝐴=2/𝛾𝛾? Why is it the case once I eliminate locations 0 and 1 (for the other player)? Another question to test your understanding: does locating at 𝑥𝑥𝐴𝐴=1/2 strictly dominate locating at 𝑥𝑥𝐴𝐴=0? A rather unimportant technical detail: on slide 22 it says that the remaining game (after eliminating the extreme positions) is *almost* the same as the original game. It is not *exactly* the same because of the following: having eliminated the extreme positions, we can indeed relabel the remaining posi-tions (beginning with 1), but the consumers beyond those positions remain, so beyond the leftmost position I still have mass 1/𝛾𝛾 of consumers, I have the same mass beyond the rightmost position, and the consumers between the (remaining) available positions have mass 1−2/𝛾𝛾 (rather than 1). But you will quickly check that this simply means that, relative to the game with 𝛾𝛾−2 positions, except at the extremes (at 0 and 1), the game with 𝛾𝛾 positions has the same payoffs/demand, *except* multi-plied by factor 1−2/𝛾𝛾 and with added constant 1/𝛾𝛾 (because, no matter where vendors locate, they always evenly share the 2/𝛾𝛾 consumers “outside”)– a (linear) transformation which leaves compari-sons between different actions unaffected. If all this puzzles you: go ahead and write down the matrix with payoffs for 𝛾𝛾=4, and compare it to the game with 𝛾𝛾=2. Regarding the final question, “is this efficient?” (slide 23, bottom): It depends a bit on the efficiency criterion. Considering consumers alone, the predicted outcome is not Pareto-efficient: you will quickly see that no consumer loses but some will strictly improve if we move *just one* vendor (to any other location). At the same time, that vendor will lose, though, so this is not a Pareto-improvement as far as vendors are concerned. It is fairly easy to see though, that from the point of view of maximizing joint surplus (i.e. if we allow for transfers between parties), the equilibrium is utterly inefficient. This result is sometimes dubbed the phenomenon of “excessive sameness” (in a context where the Hoteling line refers to different consumer tastes rather than physical locations). Remark: ‘rationalizability’ (24). If you’re interested in knowing more about the concept of “rationali-zability” (i.e., which predictions derive from rationality and common knowledge thereof alone), check Osborne’s chapter 12 or Tadelis’ section 6.3. Nash equilibrium: motivation (slide 25). This slide makes two key points: 1) ESDS and IESDS are neat concepts, but in many games (and, as you will check: all of the introductory examples except the pris-oners’ dilemma!), they make no prediction, i.e. they are “useless”; 2) any concept which goes fur-ther/makes more precise predictions will have to assume something more than rationality and joint knowledge thereof. As is the case with Nash equilibrium! Strategy profiles and best responses (26). There’s a technical detail worth mentioning here: strictly speaking, best responses are not functions, but what mathematicians call correspondences. Difference being: functions are things which map any element (an “argument”) from one set (the “domain”) into an element from another set (the “range”). Correspondences, in contrast, are not quite as well be-haved: they may return an element from the range, but (for certain arguments) they also return mul-tiple elements, or even none (i.e., the empty set). Put into our context: for certain strategies chosen by 2 …and, before you might ask: the second part of the sentence should read something like: …”if, for any loca-tion player B can possibly choose, location 𝑥𝑥𝐴𝐴=1/𝛾𝛾 always gives a strictly higher payoff than location 𝑥𝑥𝐴𝐴=0.” 4 others, there might exist more than one optimal strategy for myself, or even none. We will see exam-ples of both. Nash equilibrium (27-29). Having introduced Nash equilibrium, a natural question which might come up is: To what extent do predictions differ from those of ESDS/IESDS? In the simple example used on the slides, they don’t differ (precisely speaking: Nash and IESDS deliver the same prediction, ESDS doesn’t): this is because for the row player 1, d is a strictly dominated strategy, after which we can eliminate r for column player 2. In general though, predictions will differ. Two examples: The second example is meant to illustrate that predictions may differ even if Nash-equilibrium is unique. We will see yet more (perhaps economically more meaningful) examples shortly, such as Ber-trand competition (where there exists no strictly dominated strategy, but a unique Nash equilibrium). And: we will still say more about the relation between equilibrium concepts. Example: Cournot duopoly (30-32). This is a review (from Micro I/II), and it is a classic (any game-theory textbook will discuss it). Relating to slide 29, notice that here, we find equilibrium “construc-tively”, i.e. by figuring out best responses, and then intersecting them. The (ugly) bimatrix on slide 32 is meant to help you see the analogy between the first simple bimatrix games (and best responses as indicated there by underlining players’ payoffs) and the Cournot game with continuous strategy spaces (where best responses are now indicated by lines). Example: Bertrand duopoly (33-35). Again, this is a review, and a classic. Relating to slide 29, notice that here, we use an “explorative” approach to finding equilibrium: we check different classes of can-didate equilibria for whether or not they constitute an equilibrium (i.e. whether anyone has an incen-tive to deviate). If you are wondering why, i.e. why we don’t just again draw best response functions and intersect them: give it a try – it’s a good and worthwhile exercise! And, here’s an idea of what player 1’s best response will look like (𝑝𝑝𝑚𝑚 denotes the price which a monopolist on this market would set): 5 for 𝑝𝑝2<𝑐𝑐, any 𝑝𝑝1>𝑝𝑝2 is optimal; for 𝑝𝑝2=𝑐𝑐, any 𝑝𝑝1≥𝑐𝑐 is optimal; for 𝑝𝑝2∈(𝑐𝑐,𝑝𝑝𝑚𝑚), there exists no best response; and for 𝑝𝑝2>𝑝𝑝𝑚𝑚, 𝑝𝑝1=𝑝𝑝𝑚𝑚 is optimal. Intersecting this with the other player’s best re-sponse (by symmetry, a mirror image of player 1’s best response, as mirrored by the 45°-line) is not impossible, but rather messy – and hence not the approach usually taken. By the way, if you’re wondering why the set of best responses is empty whenever the rival sets a 𝑝𝑝𝑗𝑗∈(𝑐𝑐,𝑝𝑝𝑚𝑚): this is for the same reason that, for instance, the (open) set 𝑋𝑋=(0,1) has no maximum! I.e., recalling the definition of maximum: it contains no element which is larger than all other elements.3 (It has what mathematicians call a “supremum”, but that is a different story.) This feature is a rather technical one, but it is worth wrapping your head around because it will pop up in other exam-ples/models time and again. One way around this issue is to consider finite discrete action spaces, such as by letting firms in the above example charge prices in cents – in which case the best response to 𝑝𝑝𝑗𝑗∈(𝑐𝑐,𝑝𝑝𝑚𝑚) will be to charge one cent below 𝑝𝑝𝑗𝑗. This approach has other downsides, though, such as the introduction of multiple equilibria.4 Finally, coming back to the (“explorative”) approach of finding Bertrand equilibria “by checking”: To verify the claim that, not only is 𝑝𝑝1=𝑝𝑝2=𝑐𝑐 a Nash equilibrium, but in fact the only Nash equilibrium, you should of course convince yourself that we have indeed checked all other candidates. A sketch like the following might help: (numbers correspond to the step numbers on the slides). In particular, notice how “region 2” (𝑝𝑝𝑖𝑖=𝑐𝑐 and 𝑝𝑝𝑗𝑗>𝑐𝑐) indeed requires an argument separate from those made for the other two regions/cases! By the way, you will not have to look very far to find introductory textbooks which depict best re-sponses in the Bertrand game like this: 3A formal proof might be formulated as follows: For any 𝑥𝑥∈𝑋𝑋, (𝑥𝑥+1)/2 is larger and also contained in 𝑋𝑋, so 𝑥𝑥 cannot have been a maximum.∎ 4 In case you’re interested, Tadelis quite elaborately discusses the difference between the continuous and the discrete version of the Bertrand game in Section 5.2.4. Also: you’ve already witnessed the problem of adding equilibria through discretization of strategies in our discrete-action version of Cournot. 6 Strictly speaking, as argued above, this illustration is incorrect: the depicted best responses are both incomplete (do not depict points which are best responses) and wrong (depict points which are not). Which is not to say that this “simplified” illustration does not have its merits at an introductory level. But for us and at this level in the micro sequence, where we better understand the nuts and bolts of this model, we are in a position to understand where the simplified graph is actually wrong. Example: The tragedy of the commons (36-37). This example is literally taken from Bob Gibbons’ book (p. 27-29), but other textbooks will have a very similar example, as this is a classic model (Steve Tadelis has it on p.84-87, albeit with a specific function form). The way it (didactically) fits into the slides here is as follows: If I gave you a specific functional form for the value of a cow, such as, say, the linear form 𝑣𝑣(𝐺𝐺)=𝑎𝑎−𝑏𝑏⋅𝐺𝐺, then you could go and solve things exactly as in the Cournot game. In fact, if you try, you’ll see that the two games are structurally identi-cal! The real new challenge in this example is that you are asked to solve things for a generic function 𝑣𝑣(𝐺𝐺) (albeit with certain properties of 𝑣𝑣’ and 𝑣𝑣’’). Thus, we cannot obtain an explicit closed-form solu-tion for equilibrium. But we can nonetheless derive the key property, which is: the total number of cows in Nash equilibrium will exceed the number of cows which a social planner would pick (with the aim of maximizing social surplus). Cast back into the Cournot-setting: the example here corresponds to taking Cournot with a generic inverse demand function 𝑃𝑃(𝑄𝑄), and then showing that aggregate output will be higher than what firms would pick if their aim was to maximize firms joint profits (which would be considered collusion, though). The logic captured by this model is of course as pervasive as it is important. Any time decisionmakers, be they individuals, firms, nations etc. depend on a joint resource, be it water, (clean) air, fish etc., use of that resource will tend to be inefficiently high as decisionmakers fail to take account of (or “inter-nalize”) the impact of their use on others. Succinctly put: individually rational use will lead to an inef-ficient outcome. (A similar result holds when it comes to contributing to a public good.) In terms of practical applications, it’s hard to overemphasize the relevance of this argument concerning the covid-19 pandemic which we currently find ourselves in. To develop a sense for this, take our lec-ture’s model and, instead of cows or goats, let 𝑔𝑔𝑖𝑖 denote how much I currently leave my house and put myself and others at risk of catching the virus. Instead of green grass, let the scarce common re-source be intensive-care beds and ventilators (and medical personnel). The risk we face at the moment is one of running very, very short of this common resource, to the point where we see (many) people die because of its scarcity. At the same time, as individuals, we have a very marginal influence. More succinctly put: should we end up running out of hospital beds, it is essentially impossible that my very own staying at home would ever have changed that. And, as regards the notorious argument “well, if everyone thinks like that…”: correct, but like my action, my thinking will at best have a marginal impact on others’. Consequently, it is perfectly rational for me to leave the house – problem of course being that, if we all behave rationally, we are certain to run into tremendous trouble! (A similar rationale holds for individual firms, restaurants etc. regarding keeping their business open.) What can we do? We might urge people (and businesses) to be “reasonable” and “responsible”. Which is not a bad idea. 7 But experience shows that if reason and responsibility run counter to people’s own best interest, then reason and responsibility will soon go out the window (just take a look around – and, no, social shaming doesn’t seem to be a relevant corrective). So society might actually decide that it is best to force people to behave in a certain way – such as by means of rules (curfews) and penalties. Even if that entails some costs because now also reasonable people (who would have been very prudent) must stay home. But it might be the only way to avert tragedy. Comparing equilibrium concepts (38-41). A useful way to understand and appreciate what these slides establish is to start by depicting the most generic thinkable situation regarding how our 3 equilibrium concepts relate in a Venn diagram (below), and to then observe how the arguments successively es-tablish that some of these sets/areas are in fact empty. Which eventually lets us arrive at the diagram on slide 41. (Note: here, “ESDS” is short for “strategy profiles which survive ESDS, and likewise for IESDS.) The proofs given here (that any Nash equilibrium survives ESDS and IESDS) can be found in slightly more elaborate form in Gibbons’ Appendix 1.1.C (p. 12-14). Mixed strategies: motivation (44-45). Notice how, once we permit players to mix between the two strategies (H and T), their strategy spaces effectively go from being binary to being continuous (𝑝𝑝𝑖𝑖∈[0,1]). Even if best responses look a bit different, you will hopefully see the similarity in approaches to how we analyzed Cournot: we draw best responses in strategy space (now (𝑝𝑝1,𝑝𝑝2) instead of (𝑞𝑞1,𝑞𝑞2)), and intersect them. To familiarize yourself with this diagram, it is useful to identify best responses from the original game (for example: that 𝑝𝑝1=0 is a best response to 𝑝𝑝2=0 is nothing other than a trans-lation of the fact that, for player 1, T is a best response to T). The example is also meant to make clear: mixed-strategy equilibria are not about using a new equilib-rium concept – it is exactly the same concept as before (namely Nash equilibrium), but we have ex-tended the set of available strategies to strategies which randomize. You will hopefully also recognize this in the formal definition on slide 48. 8 On a technical note (and relating back to the lecture’s first part, on uncertainty): as soon as randomi-zation and uncertainty come into play, payoffs are to be understood as Bernoulli-utilities (i.e., they have a cardinal rather than just an ordinal interpretation). Mixed strategies and mixed extension of a game (46-47). As noted, our exposition restricts players to randomizing independently of one another (which seems a reasonable restriction in most situations). You should see where this comes into play in the definition of payoffs for the mixed extension of a game (slide 47), namely: where the probability of the joint event equals the product of each individual event’s probability, i.e. where Prob(𝑠𝑠1,𝑠𝑠2,…,𝑠𝑠𝑛𝑛)=Prob(𝑠𝑠1)× Prob(𝑠𝑠1)×⋯×Prob(𝑠𝑠𝑛𝑛). If the definition has you confused at first, be sure to go back to the motivating example and identify all of the elements there: strategies, (pure) strategy profiles (i.e., “matrix cells”), and (joint) probabilities of (pure) strategy profiles (i.e., the probabilities associated with each matrix cell). By the way: having introduced the notion of mixed strategies, we could now also go back and extend our notion of strictly dominated strategies (and the equilibrium concepts ESDS and IESDS) to allow for the possibility of mixing. For instance, in the following game, for the row player, the (pure) strategy D is strictly dominated by a strategy which mixes U and M with equal probability (but D is not strictly dominated by another pure strategy): For any (possibly mixed) strategy 𝑝𝑝≔ Prob(𝑠𝑠2=𝑙𝑙)∈[0,1] for the column player, this mixed strategy gives the row player expected payoff .5×𝑝𝑝×5+.5×(1−𝑝𝑝)×4=2+.5𝑝𝑝 which, for any 𝑝𝑝∈[0,1], strictly exceeds the expected payoff of 2𝑝𝑝+(1−𝑝𝑝)×1=1+𝑝𝑝 from playing D (the difference, 1−.5𝑝𝑝, is strictly positive for all 𝑝𝑝∈[0,1]). Nash Equilibria in mixed strategies: properties (49-50): These properties are important in that, in many applications, i.e. when looking for mixed-strategy equilibria in a specific game, you will not go through the whole construction which we used in the motivating coin-toss example, but you will di-rectly resort to these two properties: that strictly dominated (pure) strategies can never be part of a Nash equilibrium, and that any (pure) strategies which are played with strictly positive probability must constitute a best response, meaning they must deliver the same (expected) payoff. Mixed strategies in ‘meeting in New York’ (52). The comparative statics demonstrated in this example are really a key to understanding what mixed-strategy equilibria are all about: I randomize not because I myself care, but my aim is to keep the other player indifferent. Think about the penalty shooter in front of a goal, who (from the goalie’s point of view) randomizes between aiming for the left or the right corner. All that counts for equilibrium to work is that the goalie believes that the kicker random-izes, rendering the goalie indifferent (between jumping left or right). As the meeting-in-New-York example illustrates, this can sometimes produce somewhat counter-intu-itive comparative statics. Note however that, at the same time, the pure-strategy equilibria (in which both go to the same place) still continue to exist. And there is a sense in which, as 𝑐𝑐 becomes very large, we might be tempted to think that players are likely to “choose” the equilibrium in which they both go to the Empire State Building (for sure). This then belongs to a further major topic called “equi-librium selection”: when there is more than one Nash equilibrium, are there any equilibria that we deem “more likely” than others? But this is a huge topic area (without clear answers) which we will not get into here… l r U 5,0 0,1 M 0,0 4,2 D 2,3 1,0 9 By the way: this parameterized meeting-in-New-York example is also a nice way to interpret our pre-vious point about the cardinal vs. ordinal interpretation of payoffs as soon as players can mix. To see this, notice that all 𝑐𝑐>1 represent the same ordinal preferences over (certain outcomes), and pure equilibria will indeed be the same for all such 𝑐𝑐. In contrast, the mixed-strategy equilibrium changes as 𝑐𝑐 changes. Existence (optional) (54-58). Even if this part is optional, a useful take-home message relating to the comparison of equilibrium concepts (slide 41) is: Nash equilibrium is most precise in terms of giving us the smallest set of predictions – but the set never becomes so small that it yields *no* prediction (i.e., that it collapse into an empty set). Which is really good to know! Oh, and now might be a good time to go back and check the rest of the introductory game (see sepa-rate slides): What do our equilibrium concepts say? How does this square with what we observe (or what you would have said yourself)? What are your thoughts?