Game theory through examples

front cover ... 1
Game TheoryThrough Examples ... 4
copyright page ... 3
Contents ... 8
Preface ... 17
Chapter 1 Theory 1: Introduction ... 22
	1.2 Game, Play, Move: Some De?nitions ... 22
	1.3 Classi?cation of Games ... 23
	Exercises ... 24
Chapter 2 Theory 2: Simultaneous Games ... 25
	2.1 Normal Form—Bimatrix Description ... 25
		2.1.1 Two Players ... 25
		2.1.2 Two Players, Zero-sum ... 26
		2.1.3 Three or More Players ... 26
		2.1.4 Symmetric Games ... 27
	2.2 Which Option to Choose ... 27
		2.2.1 Maximin Move and Security Level ... 27
		2.2.2 Dominated Moves ... 28
		2.2.3 Best Response ... 29
		2.2.4 Nash Equilibria ... 30
	2.3 Additional Topics ... 34
		2.3.1 Best Response Digraphs ... 34
		2.3.2 2-Player Zero-sum Symmetric Games ... 35
	Exercises ... 36
Chapter 3 Example: Selecting a Class ... 40
	3.1 Three Players, Two Classes ... 40
		3.1.1 “I like you both” ... 40
		3.1.2 Disliking the Rival ... 42
		3.1.3 Outsider ... 42
	3.2 Larger Cases ... 43
	3.3 Assumptions ... 44
	Exercises ... 44
Chapter 4 Example: Doctor Location Games ... 46
	4.1 Doctor Location ... 46
		4.1.1 An Example Graph ... 47
		4.1.2 No (Pure) Nash Equilibrium? ... 48
		4.1.3 How Good are the Nash Equilibria for the Public? ... 49
	4.2 Trees ... 49
	4.3 More than one Of?ce (optional) ... 52
	Exercises ... 52
Chapter 5 Example: Restaurant Location Games ... 55
	5.1 A First Graph ... 56
	5.2 A Second Graph ... 57
	5.3 Existence of Pure Nash Equilibria ... 58
	5.4 More than one Restaurant (optional) ... 59
	Exercises ... 60
Chapter 6 Using Excel ... 63
	6.1 Spreadsheet Programs like Excel ... 63
	6.2 Two-Person Simultaneous Games ... 64
	6.3 Three-Person Simultaneous Games ... 64
	Exercises ... 64
Chapter 7 Example: Election I ... 68
	7.1 First Example ... 68
	7.2 Second Example ... 69
	7.3 The General Model ... 71
	7.4 Third Example ... 71
	7.5 The Eight Cases ... 72
	7.6 Voting Power Indices (optional) ... 72
	Exercises ... 73
Chapter 8 Theory 3: Sequential Games I: Perfect Information and no Randomness ... 74
	8.1 Extensive Form: Game Tree and Game Digraph ... 74
	8.2 Analyzing the Game: Backward Induction ... 77
		8.2.1 Finite Games ... 77
		8.2.2 The Procedure ... 78
		8.2.3 Zermelo’s Theorem ... 80
	8.3 Additional Topics ... 80
		8.3.1 Reality Check ... 80
		8.3.2 Playing it Safe—Guaranteed Payoffs ... 82
		8.3.3 Two-person Zero-sum Games ... 84
		8.3.4 Breaking Ties ... 85
		8.3.5 Existing Games ... 85
		8.3.6 Greedy Strategies ... 86
	Exercises ... 86
Chapter 9 Example: Dividing A Few Items I ... 91
	9.1 Greedy Strategy ... 91
	9.2 Backward Induction ... 92
		9.2.1 Game Tree ... 92
		9.2.2 Game Digraph ... 92
		9.2.3 Example: Game Digraph for ABBAB ... 93
	9.3 An Abbreviated Analysis ... 93
		9.3.1 Why it Matters: Complexity (optional) ... 95
	9.4 Bottom-Up Analysis ... 96
	9.5 Interdependencies between the Items (optional) ... 97
	Exercises ... 97
Chapter 10 Example: Shubik Auction I ... 98
Chapter 11 Example: Sequential Doctor and Restaurant Location ... 101
	11.1 General Observations for Symmetric Games ... 101
	11.2 Doctor Location ... 102
	11.3 Constant-Sum Games ... 103
	11.4 Restaurant Location ... 104
	11.5 Nash Equilibria and First Mover Advantage for Symmetric Games ... 105
	Exercises ... 105
Chapter 12 Theory 4: Probability ... 107
	12.1 Terminology ... 107
	12.2 Computing Probabilities ... 109
		12.2.1 Equally Likely Simple Events ... 109
		12.2.2 Simple Events not Equally Likely ... 109
	12.3 Expected Value ... 110
	12.4 Multistep Experiments ... 112
		12.4.1 Probability Trees ... 112
		12.4.2 Conditional Probabilities ... 112
		12.4.3 Probability Digraphs ... 114
	12.5 Randomness in Simultaneous Games ... 115
	12.6 Counting without Counting ... 116
	Exercises ... 116
Chapter 13 France 1654 ... 120DarkBlue,bold,notItalic,open,TopLeftZoom,239,145,0.0
Chapter 14 Example: DMA Soccer I ... 123
	14.1 1-Round 2-Step Experiment for Given Player Distributions ... 124
	14.2 Expected Goal Difference for the One-Round Game ... 125
	14.3 3-Rounds Experiment for Given Player Distributions ... 126
	14.4 Static Three-round Game ... 128
	14.5 Static Nine-round DMA Soccer ... 129
	Exercises ... 129
Chapter 15 Example: Dividing A Few Items II ... 131
	15.1 Goals of Fairness and Ef?ciency ... 131
		15.1.1 Fairness ... 131
		15.1.2 Ef?ciency ... 132
		15.1.3 Three Additional Features ... 132
		15.1.4 Mechanism Design ... 133
	15.2 Some Games ... 133
		15.2.1 Selecting one by one Games ... 133
		15.2.2 Cut and Choose ... 133
		15.2.3 Random and Exchange ... 134
	15.3 Examples ... 134
	15.4 Comparison of the Games for Seven Items and Complete Information ... 136
		15.4.1 Opposing or Similar Preferences ... 137
	15.5 Incomplete Information ... 139
	Exercises ... 140
Chapter 16 Theory 5: Sequential Games with Randomness ... 142
	16.1 Extensive Form Extended ... 142
	16.2 Analyzing the Game: Backward Induction again ... 142
	16.3 Decision Theory: Alone against Nature ... 143
	Exercises ... 146
Chapter 17 Example: Sequential Quiz Show I ... 150
	Prerequisites: Chapters 8, 12, and 16. ... 150
	17.1 Candidates with Little Knowledge ... 150
		17.1.1 More May be Less ... 151
	17.2 One Candidate Knows More ... 152
		17.2.1 Cindy Knows one Answer to be False ... 154
	Exercises ... 154
Chapter 18 Las Vegas 1962 ... 156DarkBlue,bold,notItalic,open,TopLeftZoom,239,145,0.0
Chapter 19 Example: Mini Blackjack and Card Counting ... 160
	19.1 The Basic Game ... 160
	19.2 Playing against the House ... 163
		19.2.1 How Likely are the Distributions? ... 164
		19.2.2 Betting High and Low ... 166
		19.2.3 Reshuf?ing ... 167
	Exercises ... 168
Chapter 20 Example: Duel ... 170
	20.1 One Bullet ... 170
		20.1.1 Analysis of One-bullet Variants with Increasing Probabilities without Computer Help ... 171
		20.1.2 Analysis of DUEL(1 ; 1 j m ; 2m ; 3m ; : : : ) ... 172
	20.2 Two or more Bullets ... 173
		20.2.1 A few Cases of DUEL(2; 2jm; 2m; 3m; : : :) ... 174
	Exercises ... 175
Chapter 21 Santa Monica in the 50s ... 177DarkBlue,bold,notItalic,open,TopLeftZoom,239,145,0.0
Chapter 22 Theory 6: Extensive Form of General Games ... 180
	22.1 Extensive Form and Information Sets ... 180
	22.2 No Backward Induction for Imperfect Information ... 184
	22.3 Subgames ... 185
	22.4 Multi-round Games ... 186
	22.5 Why Trees for Imperfect Information? ... 186
	Exercises ... 187
Chapter 23 Example: Shubik Auction II ... 190
	23.1 Possible Sudden End ... 190
	23.2 Imperfect and Incomplete Information ... 193
	23.3 The Auctioneer Enters the Game (optional) ... 193
	Exercises ... 195
Chapter 24 Theory 7: Normal Form and Strategies ... 197
	24.1 Pure Strategies ... 197
		24.1.1 Reduced Pure Strategies ... 198
	24.2 Normal Form ... 198
	24.3 Using Tools from Simultaneous Games for the Normal Form ... 201
	24.4 Subgame Perfectness ... 201
	24.5 Special Case of Sequential Games with Perfect Information ... 203
	Exercises ... 203
Chapter 25 Example: VNM POKER and KUHN POKER ... 206
	25.1 Description ... 206
	25.2 VNM POKER ... 208
	25.3 KUHN POKER ... 211
	Exercises ... 212
Chapter 26 Example: Waiting for Mr. Perfect ... 214
	26.1 The Last Round ... 214
	26.2 The Eight Pure Strategies ... 215
	26.3 Computing the Payoffs ... 215
	26.4 Domination ... 216
	26.5 The Reduced Normal Forms in the Three Cases ... 217
		26.5.1 The Case p 2 C 2p 3 < 1 ... 217
		26.5.2 The Case p 2 C 2p 3 > 1 ... 218
		26.5.3 The Case p 2 C 2p 3 D 1 ... 218
Chapter 27 Theory 8: Mixed Strategies ... 220
	27.1 Mixed Strategies ... 220
		27.1.1 Best Response ... 221
		27.1.2 Brown’s Fictitious Play ... 221
		27.1.3 Mixed Maximin Strategy, Mixed Security Level, and Linear Programs ... 223
	27.2 Mixed Nash Equilibria ... 224
		27.2.1 Two-player Zero-sum Games ... 224
		27.2.2 Non-Zero-sum Games ... 224
	27.3 Computing Mixed Nash Equilibria ... 225
		27.3.1 Small Two-player Zero-sum Games (optional) ... 226
			2 x n zero-sum games ... 226
			3 x n zero-sum games ... 227
		27.3.2 Solving Small non Zero-sum Two-player Games by Solving Equations (optional) ... 228
	Exercises ... 230
Chapter 28 Princeton in 1950 ... 233DarkBlue,bold,notItalic,open,TopLeftZoom,239,145,0.0
Chapter 29 Example: Airport Shuttle ... 236
	29.1 The Simple Model ... 236
		29.1.1 To the Airport ... 236
		29.1.2 From the Airport ... 239
		29.1.3 Combining Both ... 239
	29.2 Impatient Customers ... 240
	Exercises ... 240
Chapter 30 Example: Election II ... 241
	30.1 Left Over from Election I ... 241
	30.2 More Effort into Large Districts ... 242
	30.3 Defend Where Ahead or Attack Where Weak? ... 243
	30.4 Is Larger Better? ... 244
	30.5 ELECTION(7; 8; 13j   1;  1; 2jx; x ... 244
	Exercises ... 245
Chapter 31 Example: VNM POKER(2; r; m; n) ... 246
Chapter 32 Theory 9: Behavioral Strategies ... 252
	32.1 Behavioral versus Mixed Strategies ... 253
		32.1.1 Calculating Mixed Strategies from Behavioral Strategies ... 254
		32.1.2 Calculating Behavioral Strategies from Mixed Strategies for a Game Tree with Perfect Recall ... 254
	32.1.3 Kuhn’s Theorem ... 256
	Exercises ... 256
	cases where Ann exchanged and Ann has card ... 257
Chapter 33 Example: Multiple-Round Chicken ... 258
	33.1 Ordinary Chicken ... 258
	33.2 Two-round Chicken ... 259
		33.2.1 Generalized Backward Induction, using the Extensive Form ... 259
		33.2.2 Working with the Normal Form ... 261
		33.2.3 Connections between the two Approaches ... 261
	33.3 Three-round Chicken ... 262
	Exercises ... 264
Chapter 34 Example: DMA Soccer II ... 265
	34.1 Multi-round Simultaneous Games ... 265
	34.2 Information Sets and Moves ... 266
	34.3 The Optimal Third Move in Selected Cases ... 267
		34.3.1 A Detailed Example: (2, 2) versus (3, 1) ... 267
			Ann is one Goal Behind ... 268
			Other Goal Differences ... 269
		34.3.2 A Second Example: (1, 3) versus (2, 2) ... 270
	34.4 The Optimal Second Move for Seven Positions: (1, 3) versus (2, 2) and any Goal Difference ... 270
	34.5 Couldn’t We Analyze the Whole Game? ... 272
	34.6 How Good a Model is it? ... 272
Chapter 35 Example: Sequential Quiz Show II ... 273
	Prerequisites: Chapters 16 and 17. This chapter provides a glimpse into cooperative game theory, which is otherwise not covered. ... 273
	35.1 Fixed Coalitions ... 273
		35.1.1 Ann and Cindy Form a Coalition ... 273
		35.1.2 Ann and Beth Form a Coalition ... 275
		35.1.3 Beth and Cindy Form a Coalition ... 275
	35.2 Which Coalition Will Form? ... 275
		35.2.1 Fixed 50:50 Split ... 275
	35.3 Another Variant: Split can be Negotiated ... 276
	35.4 The Grand Coalition ... 277
		35.4.1 The Core ... 277
		35.4.2 The Shapley Value ... 277
	Exercises ... 278
Chapter 36 Example: VNM POKER(4, 4, 3, 5) ... 280
	36.1 Mixed Nash Equilibria ... 280
	36.2 Performance of Pure Strategies against the Mixed Nash Equilibria ... 282
Chapter 37 Example: KUHN POKER(3, 4, 2, 3) ... 285
	37.1 From Behavioral Strategies to Mixed Strategies to Expectations ... 286
	37.2 From Mixed Strategies to Behavioral Strategies ... 287
	Exercises ... 287
Chapter 38 Example: End-of-Semester Poker Tournament ... 289
	Prerequisites: Chapter 25 and all theory chapters, in particular Chapters 24, 27, and 32. Each semester my game theory class has ... 289
	38.1 Expectations ... 290
	38.2 Odds ... 291
		38.2.1 Many Rounds ... 294
	38.3 The Favorite in Knockout Tournaments ... 294
	38.4 Similarity of the DNA (optional) ... 295
	38.5 How to Create your own Tournament ... 295
	Exercises ... 296
Chapter 39 Stockholm 1994 ... 298
Bibliography ... 301
Index ... 305