Solution manual for AN INTRODUCTION TO GAME THEORY Solution manual for AN INTRODUCTION TO GAME THEORY Solution manual for AN INTR...

Author:
Martin J. Osborne

16 downloads 188 Views 363KB Size

AN INTRODUCTION TO GAME THEORY

Copyright © 2005 by Martin J. Osborne All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior permission of Martin J. Osborne. This 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, for generously making superlative software freely available. The main font is 10pt Palatino.

Version 9: 2005-10-7

Contents

Preface 1

2

xiii

Introduction 1 Exercise 5.3 (Altruistic preferences) 1 Exercise 6.1 (Alternative representations of preferences)

1

Nash Equilibrium 3 Exercise 16.1 (Working on a joint project) 3 Exercise 17.1 (Games equivalent to the Prisoner’s Dilemma) 3 Exercise 18.1 (Hermaphroditic ﬁsh) 3 Exercise 20.1 (Games without conﬂict) 4 Exercise 27.1 (Variant of Prisoner’s Dilemma with altruistic preferences) 4 Exercise 27.2 (Selﬁsh and altruistic social behavior) 5 Exercise 30.1 (Variants of the Stag Hunt) 5 Exercise 31.1 (Extension of the Stag Hunt) 6 Exercise 31.2 (Hawk–Dove) 6 Exercise 33.1 (Contributing to a public good) 7 Exercise 34.1 (Guessing two-thirds of the average) 7 Exercise 34.2 (Voter participation) 8 Exercise 34.3 (Choosing a route) 9 Exercise 37.1 (Finding Nash equilibria using best response functions) 10 Exercise 38.1 (Constructing best response functions) 11 Exercise 38.2 (Dividing money) 11 Exercise 41.1 (Strict and nonstrict Nash equilibria) 12 Exercise 42.1 (Finding Nash equilibria using best response functions) 13 Exercise 42.2 (A joint project) 13 Exercise 44.1 (Contributing to a public good) 15 Exercise 47.1 (Strict equilibria and dominated actions) 16 Exercise 47.2 (Nash equilibrium and weakly dominated actions) 17 Exercise 48.1 (Voting) 17 Exercise 49.1 (Voting between three candidates) 17 Exercise 49.2 (Approval voting) 18 Exercise 50.1 (Other Nash equilibria of the game modeling collective decision-making) 19 Exercise 50.2 (Another mechanism for collective decision-making) 20 Exercise 51.2 (Symmetric strategic games) 20 Exercise 52.2 (Equilibrium for pairwise interactions in a single population) 20 v

Contents

Exercise 97.1 (Equilibrium under strict liability)

vii

47

4

Mixed Strategy Equilibrium 49 Exercise 101.1 (Variant of Matching Pennies) 49 Exercise 106.2 (Extensions of BoS with vNM preferences) 49 Exercise 110.1 (Expected payoffs) 50 Exercise 111.1 (Examples of best responses) 50 Exercise 114.1 (Mixed strategy equilibrium of Hawk–Dove) 51 Exercise 114.2 (Games with mixed strategy equilibria) 52 Exercise 114.3 (A coordination game) 52 Exercise 114.4 (Swimming with sharks) 52 Exercise 117.2 (Choosing numbers) 54 Exercise 118.1 (Silverman’s game) 55 Exercise 118.2 (Voter participation) 56 Exercise 118.3 (Defending territory) 57 Exercise 120.2 (Strictly dominating mixed strategies) 58 Exercise 120.3 (Strict domination for mixed strategies) 58 Exercise 121.2 (Eliminating dominated actions when ﬁnding equilibria) 59 Exercise 127.1 (Equilibrium in the expert diagnosis game) 59 Exercise 127.2 (Incompetent experts) 59 Exercise 128.1 (Choosing a seller) 60 Exercise 130.2 (Approaching cars) 62 Exercise 130.3 (Bargaining) 63 Exercise 132.2 (Reporting a crime when the witnesses are heterogeneous) 63 Exercise 132.3 (Contributing to a public good) 64 Exercise 136.1 (Best response dynamics in Cournot’s duopoly game) 65 Exercise 136.2 (Best response dynamics in Bertrand’s duopoly game) 65 Exercise 139.1 (Finding all mixed strategy equilibria of two-player games) 66 Exercise 141.1 (Finding all mixed strategy equilibria of a two-player game) 67 Exercise 141.2 (Rock, paper, scissors) 68 Exercise 141.3 (Election campaigns) 69 Exercise 142.1 (A three-player game) 71 Exercise 145.1 (All-pay auction with many bidders) 72 Exercise 146.1 (Bertrand’s duopoly game) 72 Exercise 147.2 (Preferences over lotteries) 73 Exercise 149.2 (Normalized vNM payoff functions) 73 Exercise 150.1 (Games equivalent to the Prisoner’s Dilemma) 73

5

Extensive Games with Perfect Information: Theory 75 Exercise 156.2 (Examples of extensive games with perfect information) 75 Exercise 161.1 (Strategies in extensive games) 76 Exercise 163.1 (Nash equilibria of extensive games) 76 Exercise 163.2 (Voting by alternating veto) 77 Exercise 164.2 (Subgames) 77

viii

Contents

Exercise 168.1 (Checking for subgame perfect equilibria) 78 Exercise 173.2 (Finding subgame perfect equilibria) 78 Exercise 173.3 (Voting by alternating veto) 78 Exercise 173.4 (Burning a bridge) 79 Exercise 174.1 (Sharing heterogeneous objects) 79 Exercise 174.2 (An entry game with a ﬁnancially-constrained ﬁrm) 80 Exercise 176.1 (Dollar auction) 81 Exercise 177.1 (Firm–union bargaining) 82 Exercise 177.2 (The “rotten kid theorem”) 83 Exercise 177.3 (Comparing simultaneous and sequential games) 84 Exercise 179.1 (Subgame perfect equilibria of ticktacktoe) 85 Exercise 179.2 (Toetacktick) 86 Exercise 179.3 (Three Men’s Morris, or Mill) 86 6

Extensive Games with Perfect Information: Illustrations 87 Exercise 183.1 (Nash equilibria of the ultimatum game) 87 Exercise 183.2 (Subgame perfect equilibria of the ultimatum game with indivisible units) 87 Exercise 183.3 (Dictator game and impunity game) 87 Exercise 183.4 (Variants of ultimatum game and impunity game with equity-conscious players) 88 Exercise 185.1 (Bargaining over two indivisible objects) 91 Exercise 185.2 (Dividing a cake fairly) 92 Exercise 186.1 (Holdup game) 93 Exercise 187.1 (Agenda control) 93 Exercise 189.1 (Stackelberg’s duopoly game with quadratic costs) 94 Exercise 191.1 (Stackelberg’s duopoly game with ﬁxed costs) 95 Exercise 192.1 (Sequential variant of Bertrand’s duopoly game) 95 Exercise 196.1 (Three interest groups buying votes) 96 Exercise 196.2 (Interest groups buying votes under supermajority rule) 97 Exercise 196.3 (Sequential positioning by two political candidates) 97 Exercise 196.4 (Sequential positioning by three political candidates) 98 Exercise 198.1 (The race G1(2, 2)) 100 Exercise 201.1 (A race in which the players’ valuations of the prize differ) 100 Exercise 201.2 (Removing stones) 101 Exercise 202.1 (Hungry lions) 102 Exercise 203.1 (A race with a liquidity constraint) 103

7

Extensive Games with Perfect Information: Extensions and Discussion 105 Exercise 210.2 (Extensive game with simultaneous moves) 105 Exercise 210.3 (Two-period Prisoner’s Dilemma) 105 Exercise 211.1 (Timing claims on an investment) 106 Exercise 211.2 (A market game) 107 Exercise 212.1 (Price competition) 108

x

9

Contents

Bayesian Games 137 Exercise 276.1 (Equilibria of a variant of BoS with imperfect information) 137 Exercise 277.1 (Expected payoffs in a variant of BoS with imperfect information) 137 Exercise 282.1 (Fighting an opponent of unknown strength) 138 Exercise 282.2 (An exchange game) 139 Exercise 282.3 (Adverse selection) 139 Exercise 284.1 (Infection argument) 140 Exercise 287.1 (Cournot’s duopoly game with imperfect information) 141 Exercise 288.1 (Cournot’s duopoly game with imperfect information) 141 Exercise 290.1 (Nash equilibria of game of contributing to a public good) 143 Exercise 291.1 (Reporting a crime with an unknown number of witnesses) 144 Exercise 294.1 (Weak domination in second-price sealed-bid action) 145 Exercise 294.2 (Nash equilibria of a second-price sealed-bid auction) 146 Exercise 296.1 (Auctions with risk-averse bidders) 146 Exercise 299.1 (Asymmetric Nash equilibria of second-price sealed-bid common value auctions) 147 Exercise 299.2 (First-price sealed-bid auction with common valuations) 148 Exercise 306.1 (Signal-independent equilibria in a model of a jury) 148 Exercise 307.1 (Swing voter’s curse) 149 Exercise 309.2 (Property of the bidding function in a ﬁrst-price sealed-bid auction) 150 Exercise 309.3 (Example of Nash equilibrium in a ﬁrst-price auction) 151 Exercise 310.2 (Reserve prices in second-price sealed-bid auction) 151

10 Extensive Games with Imperfect Information 153 Exercise 316.1 (Variant of card game) 153 Exercise 318.2 (Strategies in variants of card game and entry game) 153 Exercise 319.3 (Nash equilibrium of card game) 154 Exercise 320.1 (Nash equilibria of variant of card game) 154 Exercise 331.1 (Selten’s horse) 155 Exercise 331.2 (Weak sequential equilibrium and Nash equilibrium in subgames) 156 Exercise 335.1 (Pooling and separating equilibria in a signaling game) 156 Exercise 335.2 (Sir Philip Sydney game) 158 Exercise 340.1 (Pooling equilibria of game in which expenditure signals quality) 159 Exercise 342.1 (Pooling equilibria of game in which education signals ability) 159 Exercise 346.1 (Comparing the receiver’s expected payoff in two equilibria) 160 Exercise 350.1 (Variant of model with piecewise linear payoff functions) 160 Exercise 350.2 (Pooling equilibrium in a general model) 160 11 Strictly Competitive Games and Maxminimization 163 Exercise 363.1 (Maxminimizers in a bargaining game) 163

Contents

xi

Exercise 363.3 (Finding a maxminimizer) 163 Exercise 364.2 (Nash equilibrium payoffs and maxminimized payoffs) 164 Exercise 365.1 (Nash equilibrium payoffs and maxminimized payoffs) 164 Exercise 366.2 (Determining strictly competitiveness) 164 Exercise 369.2 (Equilibrium payoffs in symmetric game) 165 Exercise 370.2 (Maxminimizing in BoS) 165 Exercise 372.1 (Increasing payoffs and eliminating actions) 165 Exercise 372.2 (Equilibrium in strictly competitive game) 166 Exercise 372.3 (Morra) 166 Exercise 372.4 (O’Neill’s game) 167 12 Rationalizability 169 Exercise 379.2 (Best responses to beliefs) 169 Exercise 384.1 (Mixed strategy equilibria of game in Figure 384.1) 169 Exercise 387.2 (Finding rationalizable actions) 170 Exercise 387.3 (Morra) 170 Exercise 387.4 (Guessing two-thirds of the average) 170 Exercise 387.5 (Hotelling’s model of electoral competition) 170 Exercise 388.1 (Contributing to a public good) 171 Exercise 388.2 (Cournot’s duopoly game) 172 Exercise 391.1 (Example of dominance-solvable game) 172 Exercise 391.2 (Dividing money) 173 Exercise 391.3 (Voting) 173 Exercise 392.1 (Bertrand’s duopoly game) 173 Exercise 392.2 (Strictly competitive extensive games with perfect information) 13 Evolutionary Equilibrium 175 Exercise 400.1 (Evolutionary stability and weak domination) 175 Exercise 400.2 (Example of evolutionarily stable actions) 175 Exercise 402.1 (Mixed strategy ESSs) 175 Exercise 405.1 (Hawk–Dove–Retaliator) 176 Exercise 405.2 (Variant of BoS) 176 Exercise 405.3 (Bargaining) 177 Exercise 408.1 (Equilibria of C and of G) 177 Exercise 409.2 (Variant of BoS) 178 Exercise 414.1 (A coordination game between siblings) 178 Exercise 414.2 (Assortative mating) 178 Exercise 416.1 (Darwin’s theory of the sex ratio) 179 14 Repeated Games: The Prisoner’s Dilemma 181 Exercise 423.1 (Equivalence of payoff functions) 181 Exercise 426.1 (Subgame perfect equilibrium of ﬁnitely repeated Prisoner’s Dilemma) 181 Exercise 428.1 (Strategies in an inﬁnitely repeated Prisoner’s Dilemma) 182

173

Preface

This manual contains the solutions to all the exercises in my book An Introduction to Game Theory (Oxford University Press, 2004). The sources of the problems are given in the section entitled “Notes” at the end of each chapter of the book. Please alert me to errors. M ARTIN J. O SBORNE [email protected] Department of Economics, 150 St. George Street, University of Toronto, Toronto, Canada M5S 3G7

xiii

1

Introduction

5.3 Altruistic preferences Person 1 is indifferent between (1, 4) and (3, 0), and prefers both of these to (2, 1). The payoff function u deﬁned by u( x, y) = x + 12 y, where x is person 1’s income and y is person 2’s, represents person 1’s preferences. Any function that is an increasing function of u also represents her preferences. For example, the functions k( x + 12y) for any positive number k, and (x + 12y)2 , do so. 6.1 Alternative representations of preferences The function v represents the same preferences as does u (because u( a) < u(b) < u(c) and v( a) < v(b) < v(c)), but the function w does not represent the same preferences, because w( a) = w(b) while u(a) < u(b).

1

2

Nash Equilibrium

16.1 Working on a joint project The game in Figure 3.1 models this situation (as does any other game with the same players and actions in which the ordering of the payoffs is the same as the ordering in Figure 3.1).

Work hard Goof off

Work hard 3, 3 2, 0

Goof off 0, 2 1, 1

Figure 3.1 Working on a joint project (alternative version).

17.1 Games equivalent to the Prisoner’s Dilemma The game in the left panel differs from the Prisoner’s Dilemma in both players’ preferences. Player 1 prefers (Y, X ) to (X, X ) to ( X, Y ) to (Y, Y), for example, which differs from her preference in the Prisoner’s Dilemma, which is ( F, Q) to (Q, Q) to ( F, F) to ( Q, F), whether we let X = F or X = Q. The game in the right panel is equivalent to the Prisoner’s Dilemma. If we let X = Q and Y = F then player 1 prefers ( F, Q) to (Q, Q) to (F, F ) to ( Q, F ) and player 2 prefers (Q, F) to ( Q, Q) to ( F, F) to ( F, Q), as in the Prisoner’s Dilemma. 18.1 Hermaphroditic ﬁsh A strategic game that models the situation is shown in Figure 3.2.

Either role Preferred role

Either role 1 ( H + L) , 1 ( H + L ) 2 2

Preferred role L, H

H, L

S, S

Figure 3.2 A model of encounters between pairs of hermaphroditic ﬁsh whose preferred roles differ.

In order for this game to differ from the Prisoner’s Dilemma only in the names of the players’ actions, there must be a way to associate each action with an action in the Prisoner’s Dilemma so that each player’s preferences over the four outcomes are the same as they are in the Prisoner’s Dilemma. Thus we need L < S < 12 ( H + L). 3

4

Chapter 2. Nash Equilibrium

That is, the probability of a ﬁsh’s encountering a potential partner must be large enough that S > L, but small enough that S < 12( H + L). 20.1 Games without conﬂict Any two-player game in which each player has two actions and the players have the same preferences may be represented by a table of the form given in Figure 4.1, where a, b, c, and d are any numbers.

T B

L a, a c, c

R b, b d, d

Figure 4.1 A strategic game in which conﬂict is absent.

27.1 Variant of Prisoner’s Dilemma with altruistic preferences a. A game that model the situation is given in Figure 4.2.

Quiet Fink

Quiet 4, 4 3, 3

Fink 3, 3 2, 2

Figure 4.2 The payoffs in a variant of the Prisoner’s Dilemma in which the players are altruistic.

This game is not the Prisoner’s Dilemma because one (in fact both) of the players’ preferences are not the same as they are in the Prisoner’s Dilemma. Specifically, player 1 prefers (Quiet, Quiet) to (Fink, Quiet), while in the Prisoner’s Dilemma she prefers (Fink, Quiet) to (Quiet, Quiet). (Alternatively, you may note that player 1 prefers (Quiet, Fink) to (Fink, Fink), while in the Prisoner’s Dilemma she prefers (Fink, Fink) to (Quiet, Fink), or that player 2’s preferences are similarly not the same as they are in the Prisoner’s Dilemma.) b. For an arbitrary value of α the payoffs are given in Figure 5.1. In order that the game be the Prisoner’s Dilemma we need 3 > 2(1 + α) (each player prefers Fink to Quiet when the other player chooses Quiet), 1 + α > 3α (each player prefers Fink to Quiet when the other player choose Fink), and 2(1 + α) > 1 + α (each player prefers (Quiet, Quiet) to (Fink, Fink)). The last condition is satisﬁed for all nonnegative values of α. The ﬁrst two conditions are both equivalent to α < 12. Thus the game is the Prisoner’s Dilemma if and only if α < 12 . If α = 12 then all four outcomes (Quiet, Quiet), (Quiet, Fink), (Fink, Quiet), and (Fink, Fink) are Nash equilibria; if α > 12 then only (Quiet, Quiet) is a Nash equilibrium.

6

Chapter 2. Nash Equilibrium

the stag is not a Nash equilibrium, because any one of the remaining hunters is better off joining the pursuit of the stag (thereby earning herself the right to a share of the stag). b. The set of Nash equilibria consists of the action proﬁle (Hare, . . . , Hare) in which all hunters catch hares, together with any action proﬁle in which exactly k hunters pursue the stag and the remaining hunters catch hares. Any player who deviates from the ﬁrst proﬁle obtains nothing, rather than a hare. A player who switches from the pursuit of the stag to catching a hare in the second type of proﬁle is worse off, since she obtains a hare rather than the fraction 1/k of the stag; a player who switches from catching a hare to pursuing the stag is also worse off since she obtains the fraction 1/(k + 1) of the stag rather than a hare, and 1/(k + 1) < 1/k. No other action proﬁle is a Nash equilibrium, by the following argument. • If some hunters, but fewer than m, pursue the stag then each of them obtains nothing, and is better off catching a hare. • If at least m and fewer than k hunters pursue the stag then each one that pursues a hare is better off switching to the pursuit of the stag. • If more than k hunters pursue the stag then the fraction of the stag that each of them obtains is less than 1/k, so each of them is better off catching a hare.

31.1 Extension of the Stag Hunt Every proﬁle (e, . . . , e), where e is an integer from 0 to K, is a Nash equilibrium. In the equilibrium (e, . . . , e), each player’s payoff is e. The proﬁle (e, . . . , e) is a Nash equilibrium since if player i chooses ei < e then her payoff is 2ei − e i = ei < e, and if she chooses ei > e then her payoff is 2e − ei < e. Consider an action proﬁle (e 1, . . . , e n ) in which not all effort levels are the same. Suppose that ei is the minimum. Consider some player j whose effort level exceeds ei . Her payoff is 2ei − e j < ei , while if she deviates to the effort level ei her payoff is 2ei − ei = ei . Thus she can increase her payoff by deviating, so that (e1, . . . , en ) is not a Nash equilibrium. (This game is studied experimentally by van Huyck, Battalio, and Beil (1990). See also Ochs (1995, 209–233).)

31.2 Hawk–Dove A strategic game that models the situation is shown in Figure 7.1. The game has two Nash equilibria, (Aggressive, Passive) and (Passive, Aggressive).

Chapter 2. Nash Equilibrium

7

Aggressive Passive

Aggressive 0, 0 1, 3

Passive 3, 1 2, 2

Figure 7.1 Hawk–Dove.

33.1 Contributing to a public good The following game models the situation. Players The n people. Actions Each person’s set of actions is {Contribute, Don’t contribute}. Preferences Each person’s preferences are those given in the problem. An action proﬁle in which more than k people contribute is not a Nash equilibrium: any contributor can induce an outcome she prefers by deviating to not contributing. An action proﬁle in which k people contribute is a Nash equilibrium: if any contributor stops contributing then the good is not provided; if any noncontributor switches to contributing then she is worse off. An action proﬁle in which fewer than k people contribute is a Nash equilibrium only if no one contributes: if someone contributes, she can increase her payoff by switching to noncontribution. In summary, the set of Nash equilibria is the set of action proﬁles in which k people contribute together with the action proﬁle in which no one contributes. 34.1 Guessing two-thirds of the average If all three players announce the same integer k ≥ 2 then any one of them can deviate to k − 1 and obtain $1 (since her number is now closer to 23 of the average than the other two) rather than $ 13. Thus no such action proﬁle is a Nash equilibrium. If all three players announce 1, then no player can deviate and increase her payoff; thus (1, 1, 1) is a Nash equilibrium. Now consider an action proﬁle in which not all three integers are the same; denote the highest by k∗ . • Suppose only one player names k∗ ; denote the other integers named by k1 and k 2, with k1 ≥ k2 . The average of the three integers is 13 (k∗ + k1 + k 2), so that 23 of the average is 29 (k ∗ + k 1 + k2). If k1 ≥ 29 (k∗ + k1 + k2 ) then k∗ is further from 23 of the average than is k 1, and hence does not win. If k1 < 29 (k ∗ + k1 + k2 ) then the difference between k∗ and 23 of the average is k∗ − 29 (k∗ + k 1 + k2) = 79 k ∗ − 29 k1 − 29k 2, while the difference between k1 and 2 2(k ∗ + k + k ) − k = 2 ∗ − 7 + 29k 2 . The difference 1 2 1 3 of the average is 9 9k 9 k1 between the former and the latter is 59 k ∗ + 59 k1 − 49k 2 > 0, so k 1 is closer to 23