Market Design: A Linear Programming Approach to Auctions and Matching

Contents
1 Introduction page
	1.1 Market Design and Mechanism Design
	1.2 Market Design and Mathematical Optimization
	1.3 Outline of the Book
		1.3.1 Part I Microeconomic Fundamentals
		1.3.2 Part II Multi-Object Auction Design
		1.3.3 Part III Approximation and Matching Markets
		1.3.4 Part IV Appendices: Mathematical Optimization
	1.4 Acknowledgements
Part I Microeconomic Fundamentals
	2 Game-Theoretical Basics
		2.1 Normal-Form Games
			2.1.1 Dominant-Strategy Equilibrium
			2.1.2 Pareto Optimality
			2.1.3 Nash Equilibrium
			2.1.4 Correlated Equilibrium
			2.1.5 Further Solution Concepts
		2.2 Extensive-Form Games
		2.3 Bayesian Games
			2.3.1 Bayesian Nash Equilibrium
			2.3.2 Ex Post Equilibrium
		2.4 Games and Human Behavior
		2.5 Summary
		2.6 Comprehension Questions
		2.7 Problems
	3 Mechanism Design
		3.1 Social Choice
			3.1.1 Voting Rules
			3.1.2 Arrow’s Impossibility
		3.2 Utility Functions
		3.3 Mechanism Design Theory
		3.4 Quasi-Linear Mechanism Design
			3.4.1 Quasi-Linear Utility Functions
			3.4.2 The Vickrey–Clarke–Groves Mechanism
			3.4.3 The Myerson–Satterthwaite Theorem
		3.5 Summary
			3.5.1 Robust Mechanism Design
			3.5.2 Algorithmic Mechanism Design
			3.5.3 Dynamic Mechanism Design
			3.5.4 Non-Quasi-Linear Mechanism Design
		3.6 Comprehension Questions
		3.7 Problems
	4 Single-Object Auctions
		4.1 Single-Object Auction Formats
		4.2 Model Assumptions
		4.3 Equilibrium Bidding Strategies in the IPV Model
			4.3.1 Ascending Auctions
			4.3.2 Second-Price Sealed-Bid Auctions
			4.3.3 First-Price Sealed-Bid Auctions
			4.3.4 Descending Auctions
		4.4 Comparing Equilibrium Outcomes
		4.5 Robustness of the Revenue Equivalence Theorem
			4.5.1 Risk-Averse Bidders
			4.5.2 Interdependent Values
			4.5.3 Asymmetry of Bidders
			4.5.4 Uncertainty about the Number of Bidders
		4.6 Bidder Collusion
		4.7 Optimal Auction Design
		4.8 Selected Experimental Results
		4.9 Summary
		4.10 Comprehension Questions
		4.11 Problems
Part II Multi-Object Auction Design
	5 An Overview of Multi-Object Auctions
		5.1 General Equilibrium Models
		5.2 Multi-Unit Auction Formats
			5.2.1 Sealed-Bid Multi-Unit Auction Formats
			5.2.2 Open Multi-Unit Auction Formats
			5.2.3 Sequential Sales
		5.3 Multi-Item Auction Formats
			5.3.1 Simultaneous Auctions
			5.3.2 Combinatorial Auctions
		5.4 Online and Dynamic Auction Design
		5.5 Summary
		5.6 Comprehension Questions
	6 The Simultaneous Multi-Round Auction Format
		6.1 SMRA Rules
		6.2 Tactics in the SMRA
		6.3 Strategic Situations in SMRA
			6.3.1 War of Attrition
			6.3.2 English Auction vs. War of Attrition
		6.4 Summary
		6.5 Comprehension Questions
	7 Sealed-Bid Multi-Object Auctions
		7.1 Generic Bid Languages
		7.2 The Winner Determination Problem
		7.3 Payment Rules
			7.3.1 Pay-as-Bid Payment Rules
			7.3.2 Vickrey–Clarke–Groves Payment Rules
			7.3.3 Bidder-Optimal Core Payment Rules
		7.4 Equilibrium Bidding Strategies
			7.4.1 First-Price Sealed-Bid Auctions
			7.4.2 Bidder-Optimal Core-Selecting Auctions
		7.5 Domain-Specific Compact Bid Languages
			7.5.1 Procurement Markets with Economies of Scale and Scope
			7.5.2 Distributed Scheduling in TV Ad Markets
		7.6 Combinatorial Double Auctions
		7.7 Empirical Results
		7.8 Summary
		7.9 Comprehension Questions
		7.10 Problems
	8 Open Multi-Object Auctions
		8.1 Primal–Dual Auctions for Assignment Markets
			8.1.1 Dual Prices and VCG Payments
			8.1.2 An Ascending Auction for the Assignment Problem
		8.2 Greedy Auctions and Matroids
		8.3 Models of Open Combinatorial Auctions
			8.3.1 Limits of Linear Prices
			8.3.2 Algorithmic Models of Ascending Auctions
			8.3.3 Perfect Bayesian Equilibria with General Valuations
			8.3.4 Large Markets with Non-Convexities
		8.4 Overview of Open Combinatorial Auction Formats
			8.4.1 Auction Formats with Non-Linear Prices
			8.4.2 Auction Formats with Linear Ask Prices
		8.5 Empirical Results
			8.5.1 Experiments with Small Markets
			8.5.2 Experiments with Larger Markets
		8.6 Summary
		8.7 Comprehension Questions
		8.8 Problems
	9 The Combinatorial Clock Auction Formats
		9.1 The Single-Stage Combinatorial Clock Auction
			9.1.1 Auction Process
			9.1.2 Efficiency of the SCCA
		9.2 The Two-Stage Combinatorial Clock Auction Format
			9.2.1 Auction Process
			9.2.2 Activity Rules
			9.2.3 A Note on Revealed Preference Theory
			9.2.4 Strategies in the Two-Stage CCA
		9.3 Experiments on the Two-Stage CCA
		9.4 Summary
		9.5 Comprehension Questions
		9.6 Problems
Part III Approximation and Matching Markets
	10 Approximation Mechanisms
		10.1 Approximation and Truthfulness
			10.1.1 Deterministic Approximation Mechanisms
			10.1.2 Randomized Approximation Mechanisms
		10.2 Deterministic Mechanisms for Single-Minded Bidders
			10.2.1 Greedy-Acceptance Auctions
			10.2.2 Deferred-Acceptance Auctions
		10.3 Randomized Mechanisms
			10.3.1 The Relax-and-Round Framework
			10.3.2 Combinatorial Auctions via Relax-and-Round
		10.4 Summary
		10.5 Comprehension Questions
	11 Matching Markets
		11.1 Overview of Matching Problems
		11.2 Two-Sided Matching
			11.2.1 Definitions and Notation
			11.2.2 The Gale–Shapley Student-Optimal Stable Mechanism
			11.2.3 The Efficiency-Adjusted Deferred-Acceptance Mechanism
		11.3 One-Sided Matching
			11.3.1 The Top Trading Cycle Mechanism
			11.3.2 The Probabilistic Serial Mechanism
		11.4 One-Sided Matching with Complementarities
			11.4.1 Multi-Unit and Combinatorial Assignments
			11.4.2 Cardinal Assignment Problems with Complementarities
		11.5 Applications and Empirical Results
		11.6 Summary
			11.6.1 Two-Sided Matching Mechanisms
			11.6.2 One-Sided Matching Mechanisms
		11.7 Comprehension Questions
		11.8 Problems
	12 Outlook
		12.1 Challenges in Market Design
		12.2 Going Forward
Part IV Appendices: Mathematical Optimization
	A Linear Optimization
		A.1 Geometry of Linear Programs
		A.2 Feasibility
		A.3 Duality Theory
		A.4 Integrality of Linear Programs
	B Algorithms and Complexity
		B.1 Computational Complexity
		B.2 Algorithms for Linear Programs
		B.3 Algorithms for Integer Linear Programs
		B.4 Approximation Algorithms
			B.4.1 Complexity Classes
			B.4.2 LP-Based Approximation Algorithms
References
Index