دانلود کتاب 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