Market Design: A Linear Programming Approach to Auctions and Matching

Description

This textbook is intended to provide a one-semester course on market design. I am pri- marily targeting students with a background in computer science, information systems, mathematics, and management science. Hence, I will first introduce in Part I necessary concepts from game theory and mechanism design, as these students typically have not had the respective introductory courses. Parts II and III cover material which is more recent and is often not covered in microeconomics. One prerequisite for this book is a familiarity with linear and integer linear program- ming and an introductory course in calculus and probability theory. There are many introductory textbooks on these subjects which would provide an excellent start for the topics discussed throughout this book. The appendices summarize important results from mathematical optimization and should serve as a convenient reference for the reader and a brief introduction for those who have not studied the respective courses. 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