Preface ........................................................ xi
1 Introduction and Examples .................................... 1
1.1 The Science of Rule-Making .............................. 1
1.2 When Is Selfish Behavior Near-Optimal? .................. 3
1.3 Can Strategic Players Learn an Equilibrium? ............. 6
Notes, Problems, and Exercises ............................... 9
2 Mechanism Design Basics ..................................... 11
2.1 Single-Item Auctions ................................... 11
2.2 Sealed-Bid Auctions .................................... 12
2.3 First-Price Auctions ................................... 12
2.4 Second-Price Auctions and Dominant Strategies .......... 13
2.5 Ideal Auctions ......................................... 15
2.6 Case Study: Sponsored Search Auctions .................. 16
Notes, Problems, and Exercises .............................. 20
3 Myerson's Lemma ............................................. 24
3.1 Single-Parameter Environments .......................... 24
3.2 Allocation and Payment Rules ........................... 26
3.3 Statement of Myerson's Lemma ........................... 26
3.4 Proof of Myerson's Lemma .............................. 28
3.5 Applying the Payment Formula .......................... 31
Notes, Problems, and Exercises .............................. 34
4 Algorithmic Mechanism Design ................................ 39
4.1 Knapsack Auctions ...................................... 39
4.2 Algorithmic Mechanism Design ........................... 42
4.3 The Revelation Principle ............................... 46
Notes, Problems, and Exercises .............................. 49
5 Revenue-Maximizing Auctions ................................. 55
5.1 The Challenge of Revenue Maximization .................. 55
5.2 Characterization of Optimal DSIC Mechanisms ............ 58
5.3 Case Study: Reserve Prices in Sponsored Search ......... 65
5.4 Proof of Lemma 5.1 ..................................... 66
Notes, Problems, and Exercises .............................. 69
6 Simple Near-Optimal Auctions ................................ 74
6.1 Optimal Auctions Can Be Complex ........................ 74
6.2 The Prophet Inequality ................................. 75
6.3 Simple Single-Item Auctions ............................ 77
6.4 Prior-Independent Mechanisms ........................... 79
Notes, Problems, and Exercises .............................. 82
7 Multi-Parameter Mechanism Design ............................ 87
7.1 General Mechanism Design Environments .................. 87
7.2 The VCG Mechanism ...................................... 88
7.3 Practical Considerations ............................... 91
Notes, Problems, and Exercises .............................. 93
8 Spectrum Auctions ........................................... 97
8.1 Indirect Mechanisms .................................... 97
8.2 Selling Items Separately ............................... 98
8.3 Case Study: Simultaneous Ascending Auctions ........... 100
8.4 Package Bidding ....................................... 105
8.5 Case Study: The 2016 FCC Incentive Auction ............ 106
Notes, Problems, and Exercises ............................. 110
9 Mechanism Design with Payment Constraints .................. 113
9.1 Budget Constraints .................................... 113
9.2 The Uniform-Price Multi-Unit Auction .................. 114
9.3 The Clinching Auction ................................. 116
9.4 Mechanism Design without Money ........................ 119
Notes, Problems, and Exercises ............................. 123
10 Kidney Exchange and Stable Matching ........................ 128
10.1 Case Study: Kidney Exchange ........................... 128
10.2 Stable Matching ....................................... 136
10.3 Further Properties .................................... 139
Notes, Problems, and Exercises ............................. 142
11 Selfish Routing and the Price of Anarchy ................... 145
11.1 Selfish Routing: Examples ............................. 145
11.2 Main Result: Informal Statement ....................... 147
11.3 Main Result: Formal Statement ......................... 149
11.4 Technical Preliminaries ............................... 152
11.5 Proof of Theorem 11.2 ................................. 153
Notes, Problems, and Exercises ............................. 156
12 Over-Provisioning and Atomic Selfish Routing ............... 159
12.1 Case Study: Network Over-Provisioning ................. 159
12.2 A Resource Augmentation Bound ......................... 161
12.3 Proof of Theorem 12.1 ................................. 162
12.4 Atomic Selfish Routing ................................ 163
12.5 Proof of Theorem 12.3 ................................. 165
Notes, Problems, and Exercises ............................. 169
13 Equilibria: Definitions, Examples, and Existence ........... 173
13.1 A Hierarchy of Equilibrium Concepts ................... 173
13.2 Existence of Pure Nash Equilibria ..................... 179
13.3 Potential Games ....................................... 181
Notes, Problems, and Exercises ............................. 183
14 Robust Price-of-Anarchy Bounds in Smooth Games ............. 187
14.1 A Recipe for POA Bounds ............................... 187
14.2 A Location Game ....................................... 188
14.3 Smooth Games .......................................... 194
14.4 Robust POA Bounds in Smooth Games ..................... 195
Notes, Problems, and Exercises ............................. 199
15 Best-Case and Strong Nash Equilibria ....................... 202
15.1 Network Cost-Sharing Games ............................ 202
15.2 The Price of Stability ................................ 205
15.3 The POA of Strong Nash Equilibria ..................... 208
15.4 Proof of Theorem 15.3 ................................. 210
Notes, Problems, and Exercises ............................. 213
16 Best-Response Dynamics ..................................... 216
16.1 Best-Response Dynamics in Potential Games ............. 216
16.2 Approximate PNE in Selfish Routing Games .............. 219
16.3 Proof of Theorem 16.3 ................................. 221
16.4 Low-Cost Outcomes in Smooth Potential Games ........... 223
Notes, Problems, and Exercises ............................. 226
17 No-Regret Dynamics ......................................... 230
17.1 Online Decision Making ................................ 230
17.2 The Multiplicative Weights Algorithm .................. 234
17.3 Proof of Theorem 17.6 ................................. 236
17.4 No Regret and Coarse Correlated Equilibria ............ 239
Notes, Problems, and Exercises ............................. 242
18 Swap Regret and the Minimax Theorem ........................ 247
18.1 Swap Regret and Correlated Equilibria ................. 247
18.2 Proof of Theorem 18.5 ................................. 249
18.3 The Minimax Theorem for Zero-Sum Games ................ 253
18.4 Proof of Theorem 18.7 ................................. 255
Notes, Problems, and Exercises ............................. 258
19 Pure Nash Equilibria and PLS-Completeness .................. 261
19.1 When Are Equilibrium Concepts Tractable? .............. 261
19.2 Local Search Problems ................................. 264
19.3 Computing a PNE of a Congestion Game .................. 271
Notes, Problems, and Exercises ............................. 276
20 Mixed Nash Equilibria and PPAD-Completeness ................ 279
20.1 Computing a MNE of a Bimatrix Game .................... 279
20.2 Total NP Search Problems (TFNP) ....................... 280
20.3 WAD: A Syntactic Subclass of TFNP ..................... 285
20.4 A Canonical PPAD Problem: Sperner's Lemma ............. 288
20.5 MNE and PPAD .......................................... 290
20.6 Discussion ............................................ 293
Notes, Problems, and Exercises ............................. 294
The Top 10 List ............................................... 299
Hints to Selected Exercises and Problems ...................... 301
Bibliography .................................................. 309
Index ......................................................... 329
|
