Market Design: A Linear Programming Approach to Auctions and Matching

Contents......Page 8
1 Introduction page......Page 14
1.1 Market Design and Mechanism Design......Page 15
1.2 Market Design and Mathematical Optimization......Page 16
1.3 Outline of the Book......Page 17
1.3.1 Part I Microeconomic Fundamentals......Page 18
1.3.2 Part II Multi-Object Auction Design......Page 19
1.3.4 Part IV Appendices: Mathematical Optimization......Page 20
1.4 Acknowledgements......Page 21
Part I Microeconomic Fundamentals......Page 22
2.1 Normal-Form Games......Page 24
2.1.2 Pareto Optimality......Page 26
2.1.3 Nash Equilibrium......Page 27
2.1.4 Correlated Equilibrium......Page 30
2.1.5 Further Solution Concepts......Page 32
2.2 Extensive-Form Games......Page 33
2.3 Bayesian Games......Page 35
2.3.1 Bayesian Nash Equilibrium......Page 37
2.3.2 Ex Post Equilibrium......Page 38
2.4 Games and Human Behavior......Page 39
2.5 Summary......Page 40
2.7 Problems......Page 41
3 Mechanism Design......Page 43
3.1.1 Voting Rules......Page 44
3.1.2 Arrow’s Impossibility......Page 46
3.2 Utility Functions......Page 48
3.3 Mechanism Design Theory......Page 52
3.4.1 Quasi-Linear Utility Functions......Page 55
3.4.2 The Vickrey–Clarke–Groves Mechanism......Page 57
3.4.3 The Myerson–Satterthwaite Theorem......Page 59
3.5.1 Robust Mechanism Design......Page 61
3.5.3 Dynamic Mechanism Design......Page 62
3.5.4 Non-Quasi-Linear Mechanism Design......Page 63
3.7 Problems......Page 64
4.1 Single-Object Auction Formats......Page 66
4.2 Model Assumptions......Page 67
4.3 Equilibrium Bidding Strategies in the IPV Model......Page 68
4.3.2 Second-Price Sealed-Bid Auctions......Page 69
4.3.3 First-Price Sealed-Bid Auctions......Page 70
4.4 Comparing Equilibrium Outcomes......Page 73
4.5.1 Risk-Averse Bidders......Page 75
4.5.2 Interdependent Values......Page 77
4.6 Bidder Collusion......Page 78
4.7 Optimal Auction Design......Page 79
4.8 Selected Experimental Results......Page 81
4.9 Summary......Page 83
4.11 Problems......Page 84
Part II Multi-Object Auction Design......Page 86
5.1 General Equilibrium Models......Page 88
5.2.1 Sealed-Bid Multi-Unit Auction Formats......Page 90
5.2.2 Open Multi-Unit Auction Formats......Page 91
5.2.3 Sequential Sales......Page 93
5.3.2 Combinatorial Auctions......Page 94
5.5 Summary......Page 96
5.6 Comprehension Questions......Page 97
6.1 SMRA Rules......Page 98
6.2 Tactics in the SMRA......Page 99
6.3 Strategic Situations in SMRA......Page 101
6.3.1 War of Attrition......Page 102
6.3.2 English Auction vs. War of Attrition......Page 106
6.5 Comprehension Questions......Page 108
7.1 Generic Bid Languages......Page 109
7.2 The Winner Determination Problem......Page 111
7.3.2 Vickrey–Clarke–Groves Payment Rules......Page 114
7.3.3 Bidder-Optimal Core Payment Rules......Page 118
7.4.1 First-Price Sealed-Bid Auctions......Page 120
7.5 Domain-Specific Compact Bid Languages......Page 124
7.5.1 Procurement Markets with Economies of Scale and Scope......Page 125
7.5.2 Distributed Scheduling in TV Ad Markets......Page 130
7.6 Combinatorial Double Auctions......Page 133
7.7 Empirical Results......Page 134
7.8 Summary......Page 135
7.9 Comprehension Questions......Page 136
7.10 Problems......Page 137
8 Open Multi-Object Auctions......Page 139
8.1 Primal–Dual Auctions for Assignment Markets......Page 140
8.1.1 Dual Prices and VCG Payments......Page 141
8.1.2 An Ascending Auction for the Assignment Problem......Page 144
8.2 Greedy Auctions and Matroids......Page 152
8.3.1 Limits of Linear Prices......Page 157
8.3.2 Algorithmic Models of Ascending Auctions......Page 163
8.3.3 Perfect Bayesian Equilibria with General Valuations......Page 165
8.3.4 Large Markets with Non-Convexities......Page 167
8.4.1 Auction Formats with Non-Linear Prices......Page 168
8.4.2 Auction Formats with Linear Ask Prices......Page 171
8.5.1 Experiments with Small Markets......Page 175
8.5.2 Experiments with Larger Markets......Page 176
8.7 Comprehension Questions......Page 177
8.8 Problems......Page 178
9.1.1 Auction Process......Page 180
9.1.2 Efficiency of the SCCA......Page 181
9.2.1 Auction Process......Page 185
9.2.2 Activity Rules......Page 186
9.2.3 A Note on Revealed Preference Theory......Page 188
9.2.4 Strategies in the Two-Stage CCA......Page 191
9.3 Experiments on the Two-Stage CCA......Page 196
9.6 Problems......Page 198
Part III Approximation and Matching Markets......Page 200
10 Approximation Mechanisms......Page 202
10.1 Approximation and Truthfulness......Page 203
10.1.2 Randomized Approximation Mechanisms......Page 204
10.2 Deterministic Mechanisms for Single-Minded Bidders......Page 206
10.2.1 Greedy-Acceptance Auctions......Page 207
10.2.2 Deferred-Acceptance Auctions......Page 209
10.3 Randomized Mechanisms......Page 211
10.3.1 The Relax-and-Round Framework......Page 212
10.3.2 Combinatorial Auctions via Relax-and-Round......Page 214
10.5 Comprehension Questions......Page 217
11.1 Overview of Matching Problems......Page 219
11.2 Two-Sided Matching......Page 221
11.2.1 Definitions and Notation......Page 222
11.2.2 The Gale–Shapley Student-Optimal Stable Mechanism......Page 226
11.2.3 The Efficiency-Adjusted Deferred-Acceptance Mechanism......Page 230
11.3 One-Sided Matching......Page 232
11.3.1 The Top Trading Cycle Mechanism......Page 233
11.3.2 The Probabilistic Serial Mechanism......Page 236
11.4.1 Multi-Unit and Combinatorial Assignments......Page 238
11.4.2 Cardinal Assignment Problems with Complementarities......Page 239
11.5 Applications and Empirical Results......Page 244
11.6.1 Two-Sided Matching Mechanisms......Page 246
11.6.2 One-Sided Matching Mechanisms......Page 248
11.8 Problems......Page 249
12 Outlook......Page 251
12.1 Challenges in Market Design......Page 252
12.2 Going Forward......Page 253
Part IV Appendices: Mathematical Optimization......Page 256
A.1 Geometry of Linear Programs......Page 258
A.2 Feasibility......Page 262
A.3 Duality Theory......Page 263
A.4 Integrality of Linear Programs......Page 267
B.1 Computational Complexity......Page 269
B.3 Algorithms for Integer Linear Programs......Page 271
B.4 Approximation Algorithms......Page 275
B.4.1 Complexity Classes......Page 276
B.4.2 LP-Based Approximation Algorithms......Page 277
References......Page 281
Index......Page 294