Publicly­availablesolutionsfor AN INTRODUCTION TO GAME …

1 Publicly-available solutions forAN INTRODUCTION TOGAMETHEORYP ublicly-available solutions forAN INTRODUCTION TOGAMETHEORYMARTINJ. OSBORNEU niversity of TorontoCopyright 2012 by Martin J. OsborneAll rights reserved. No part of this publication may be reproduced, stored in aretrieval system, or transmitted, in any form or by any means, electronic,mechanical, photocopying, recording, or otherwise, without the prior permissionof Martin J. manual was typeset by the author, who is greatly indebted to Donald Knuth(TEX), Leslie Lamport (LATEX), Diego Puga (mathpazo), Christian Schenk(MiKTEX), Ed Sznyter (ppctr), Timothy van Zandt (PSTricks), and others, forgenerously making superlative software freely main font is 6: 2012-4-7 ContentsPreface xi1 INTRODUCTION 1 Exercise (Altruistic preferences) 1 Exercise (Alternative representations of preferences) 12 Nash Equilibrium 3 Exercise (Working on a joint project) 3 Exercise (Games equivalent to thePrisoner s Dilemma) 3 Exercise (Games without conflict) 3 Exercise (Extension of theStag Hunt) 4 Exercise (Guessing two-thirds of the average) 4 Exercise (Choosing a route) 5 Exercise (Finding Nash equilibria using best response functions) 6 Exercise (Constructing best response functions) 6 Exercise (Dividing money) 7 Exercise (Strict and nonstrict Nash equilibria) 7 Exercise (Strict equilibria and dominated actions) 8 Exercise (Nash equilibrium and weakly dominated actions) 8 Exercise (Other Nash equilibria of the game modeling collectivedecision-making) 8 Exercise (Symmetric strategic games)

2 9 Exercise (Equilibrium for pairwise interactions in a single population) 93 Nash Equilibrium: Illustrations 11 Exercise (Cournot s duopoly game with linear inverse demand and differentunit costs) 11 Exercise (Nash equilibrium of Cournot s duopoly game and the collusiveoutcome) 12 Exercise (Interaction among resource-users) 12 Exercise (Bertrand s duopoly game with constant unit cost) 13 Exercise (Bertrand s oligopoly game) 13 Exercise (Bertrand s duopoly game with different unit costs) 13 Exercise (Electoral competition with asymmetric voters preferences) 14 Exercise (Electoral competition for more general preferences) 14 Exercise (Competition in product characteristics) 15 Exercise (Direct argument for Nash equilibria ofWar of Attrition) 15 Exercise (Second-price sealed-bid auction with two bidders) 16vviContentsExercise (Nash equilibrium of first-price sealed-bid auction) 17 Exercise (First-price sealed-bid auction) 17 Exercise (All-pay auctions)

3 18 Exercise (Multiunit auctions) 18 Exercise (Internet pricing) 19 Exercise (Alternative standards of care under negligence with contributorynegligence) 194 Mixed Strategy Equilibrium 23 Exercise (Variant ofMatching Pennies) 23 Exercise (Extensions ofBoSwith vNM preferences) 23 Exercise (Expected payoffs) 24 Exercise (Examples of best responses) 24 Exercise (Mixed strategy equilibrium ofHawk Dove) 25 Exercise (Choosing numbers) 26 Exercise (Strictly dominating mixed strategies) 26 Exercise (Strict domination for mixed strategies) 26 Exercise (Equilibrium in the expert diagnosis game) 27 Exercise (Bargaining) 27 Exercise (Reporting a crime when the witnesses are heterogeneous) 28 Exercise (Best response dynamics in Cournot s duopoly game) 29 Exercise (Finding all mixed strategy equilibria of two-player games) 29 Exercise (All-pay auction with many bidders) 30 Exercise (Preferences over lotteries) 31 Exercise (Normalized vNM payoff functions) 315 Extensive Games with Perfect Information: Theory 33 Exercise (Nash equilibria of extensive games) 33 Exercise (Subgames) 33 Exercise (Checking for subgame perfect equilibria) 33 Exercise (Sharing heterogeneous objects) 34 Exercise (Comparing simultaneous and sequential games) 34 Exercise (Three Men s Morris, or Mill) 356 Extensive Games with Perfect Information.

4 Illustrations37 Exercise (Nash equilibria of the ultimatum game) 37 Exercise (Subgame perfect equilibria of the ultimatum game with indivisibleunits) 37 Exercise (Holdup game) 37 Exercise (Stackelberg s duopoly game with quadratic costs) 38 Exercise (Sequential positioning by three political candidates) 38 Exercise (The race G1(2, 2)) 40 Exercise (A race with a liquidity constraint) 40 Contentsvii7 Extensive Games with Perfect Information: Extensions andDiscussion 43 Exercise (Extensive game with simultaneous moves) 43 Exercise (Electoral competition with strategic voters) 43 Exercise (Top cycle set) 44 Exercise (Exit from a declining industry) 45 Exercise (Variant of ultimatum game with equity-conscious players) 45 Exercise (Nash equilibria when players may make mistakes) 46 Exercise (Nash equilibria of the chain-store game) 478 Coalitional Games and the Core 49 Exercise (Three-player majority game) 49 Exercise (Core of landowner worker game) 49 Exercise (Unionized workers in landowner worker game) 49 Exercise (Landowner worker game with increasing marginal products) 50 Exercise (Range of prices in horse market) 50 Exercise (House assignment with identical preferences) 51 Exercise (Median voter theorem) 51 Exercise (Empty core in roommate problem)

5 519 Bayesian Games 53 Exercise (Equilibria of a variant ofBoSwith imperfect information) 53 Exercise (Expected payoffs in a variant ofBoSwith imperfectinformation) 53 Exercise (An exchange game) 54 Exercise (Cournot s duopoly game with imperfect information) 55 Exercise (Cournot s duopoly game with imperfect information) 55 Exercise (Nash equilibria of game of contributing to a public good) 57 Exercise (Weak domination in second-price sealed-bid action) 58 Exercise (Asymmetric Nash equilibria of second-price sealed-bid commonvalue auctions) 59 Exercise (First-price sealed-bid auction with common valuations) 59 Exercise (Properties of the bidding function in a first-price sealed-bidauction) 60 Exercise (Example of Nash equilibrium in a first-price auction) 6010 Extensive Games with Imperfect Information 61 Exercise (Variant of card game) 61 Exercise (Strategies in variants of card game and entry game) 61 Exercise (Weak sequential equilibrium and Nash equilibrium insubgames) 62 Exercise (Pooling equilibria of game in which expenditure signals quality) 62 Exercise (Comparing the receiver s expected payoff in two equilibria) 63 Exercise (Variant of model with piecewise linear payoff functions) 63viiiContents11 Strictly Competitive Games and Maxminimization 65 Exercise (Maxminimizers in a bargaining game) 65 Exercise (Finding a maxminimizer) 65 Exercise (Determining strictly competitiveness) 66 Exercise (Maxminimizing in BoS) 66 Exercise (Equilibrium in strictly competitive game) 66 Exercise (O Neill s game) 6612 Rationalizability 69 Exercise (Best responses to beliefs) 69 Exercise (Mixed strategy equilibria of game in Figure ) 69 Exercise (Finding rationalizable actions)

6 70 Exercise (Hotelling s model of electoral competition) 70 Exercise (Cournot s duopoly game) 70 Exercise (Example of dominance-solvable game) 71 Exercise (Dividing money) 71 Exercise (Strictly competitive extensive games with perfect information) 7113 Evolutionary Equilibrium 73 Exercise (Evolutionary stability and weak domination) 73 Exercise (Hawk Dove Retaliator) 73 Exercise (Bargaining) 74 Exercise (Equilibria of C and of G) 74 Exercise (A coordination game between siblings) 75 Exercise (Assortative mating) 75 Exercise (Darwin s theory of the sex ratio) 7614 Repeated Games: ThePrisoner s Dilemma77 Exercise (Equivalence of payoff functions) 77 Exercise (Subgame perfect equilibrium of finitely repeatedPrisoner sDilemma) 77 Exercise (Strategies in an infinitely repeatedPrisoner s Dilemma) 78 Exercise (Finitely repeatedPrisoner s Dilemmawith switching cost) 78 Exercise (Deviations from grim trigger strategy) 80 Exercise (Different punishment lengths in subgame perfect equilibrium) 80 Exercise (Tit-for-tatas a subgame perfect equilibrium) 8115 Repeated Games: General Results 83 Exercise (Repeated Bertrand duopoly) 83 Exercise (Detection lags) 8416 Bargaining 85 Exercise (Two-period bargaining with constant cost of delay) 85 Exercise (Three-period bargaining with constant cost of delay) 85 Contentsix17 Appendix.

7 Mathematics 87 Exercise (Maximizer of quadratic function) 87 Exercise (Sums of sequences) 87 Exercise (Bayes law) 87 References 89 PrefaceThis manual contains all publicly-available solutions to exercises in my bookAnIntroduction to Game Theory(Oxford University Press, 2004). The sources of theproblems are given in the section entitled Notes at the endof each chapter of thebook. Please alert me to of Economics, 150 St. George Street,University of Toronto, Toronto, Canada M5S Altruistic preferencesPerson 1 is indifferent between(1, 4)and(3, 0), and prefers both of these to(2, 1).The payoff functionudefined byu(x,y) =x+12y, wherexis person 1 s incomeandyis person 2 s, represents person 1 s preferences. Any function that is anincreasing function ofualso represents her preferences. For example, the functionsk(x+12y)for any positive numberk, and(x+12y)2, do Alternative representations of preferencesThe functionvrepresents the same preferences as doesu(becauseu(a)<u(b)<u(c)andv(a)<v(b)< v(c)), but the functionwdoes not represent the samepreferences, becausew(a) =w(b)whileu(a)<u(b).

8 12 Nash Working on a joint projectThe game in Figure models this situation (as does any other game with thesame players and actions in which the ordering of the payoffsis the same as theordering in Figure ).Work hard goof offWork hard3, 30, 2 goof off2, 01, 1 Figure on a joint project (alternative version). Games equivalent to thePrisoner s DilemmaThe game in the left panel differs from thePrisoner s Dilemmain both players pref-erences. Player 1 prefers(Y,X)to(X,X)to(X,Y)to(Y,Y), for example, whichdiffers from her preference in thePrisoner s Dilemma, which is(F,Q)to(Q,Q)to(F,F)to(Q,F), whether we letX=ForX= game in the right panel is equivalent to thePrisoner s Dilemma. If we letX=QandY=Fthen player 1 prefers(F,Q)to(Q,Q)to(F,F)to(Q,F)andplay er 2 prefers(Q,F)to(Q,Q)to(F,F)to(F,Q), as in thePrisoner s Games without conflictAny two-player game in which each player has two actions and the players havethe same preferences may be represented by a table of the formgiven in Figure ,wherea,b,c, anddare any ,ab,bBc,cd,dFigure strategic game in which conflict is 2.

9 Nash Extension of theStag HuntEvery profile(e, .. ,e), whereeis an integer from 0 toK, is a Nash equilibrium. Inthe equilibrium(e, .. ,e), each player s payoff ise. The profile(e, .. ,e)is a Nashequilibrium since if playerichoosesei<ethen her payoff is 2ei ei=ei<e, andif she choosesei>ethen her payoff is 2e ei< an action profile(e1, .. ,en)in which not all effort levels are the thateiis the minimum. Consider some playerjwhose effort level exceedsei. Her payoff is 2ei ej<ei, while if she deviates to the effort leveleiher payoffis 2ei ei=ei. Thus she can increase her payoff by deviating, so that(e1, .. ,en)isnot a Nash equilibrium.(This game is studied experimentally by van Huyck, Battalio, and Beil (1990).See also Ochs (1995, 209 233).) Guessing two-thirds of the averageIf all three players announce the same integerk 2 then any one of them can devi-ate tok 1 and obtain $1 (since her number is now closer to23of the average thanthe other two) rather than $13.

10 Thus no such action profile is a Nash all three players announce 1, then no player can deviate and increase her payoff;thus(1, 1, 1)is a Nash consider an action profile in which not all three integersare the same;denote the highest byk . Suppose only one player namesk ; denote the other integers named byk1andk2, withk1 k2. The average of the three integers is13(k +k1+k2),so that23of the average is29(k +k1+k2). Ifk1 29(k +k1+k2)thenk is further from23of the average than isk1, and hence does not win. Ifk1<29(k +k1+k2)then the difference betweenk and23of the average isk 29(k +k1+k2) =79k 29k1 29k2, while the difference betweenk1and23of the average is29(k +k1+k2) k1=29k 79k1+29k2. The differencebetween the former and the latter is59k +59k1 49k2>0, sok1is closer to23of the average than isk . Hence the player who namesk does not win, andis better off namingk2, in which case she obtains a share of the prize. Thusno such action profile is a Nash equilibrium.