Online and Matching-Based Market Design

Contents
Contributors
Foreword
Preface
Part One Foundations of Market Design
	Chapter 1 Two-Sided Markets: Stable Matching
		1.1 Introduction
		1.2 The Gale-Shapley Deferred Acceptance Algorith,
			1.2.1 The DA Algorithm for Setting 1
			1.2.2 Extension to Setting II
			1.2.3 Reduction from Setting III to Setting II
		1.3 Incentive Compatibility
			1.3.1 Proof of DSIC for Setting I
			1.3.2 DSIC for Setting II
			1.3.3 DSIC for Setting III
		1.4 The Lattice of Stable Matchings
			1.4.1 The Lattice for Setting I
				1.4.1.1 Rotations, and Their Use for Traversing the Lattice
				1.4.1.2 Rotations Corresond to Join-Irreducible Stable Matchings
				1.4.1.3 Birkhoff\'s Representation Theorem
			1.4.2 The Lattice for Setting II and III
		1.5 Linear Programming Formulation
			1.5.1 LP for Setting I
			1.5.2 LPs for Settings II and III
		1.6 Exercises
		1.7 Bibliographic Notes
		References
	Chpater 2 One-Sided Matching Markets
		2.1 Introduction
		2.2 Preliminaries
		2.3 Random Priority and Probabilistic Serial: Ordinal, No Endowments
			2.3.1 Random Priority(RP
)
			2.3.2 Probabilistic Serial(PS) Mechanism
		2.4 Top Trading Cycle: Ordinal, 
Endowments
		2.5 Hylland-Zeckhauser: Cardinal, No Endowments
		2.6 ε-Approximate ADHZ: Cardinal, Endowments
		2.7 Online Bipartite Matching
			2.7.1 The Competitive Ratio of Online Algorithms
			2.7.2 The Algorithm RANKING
			2.7.3 Analysis of RANKING
			2.7.4 Upper-Bounding the Performance of Any Randomized Algorithm
				2.7.4.1 Sets pf Algorithms and Inputs
				2.7.4.2 Von Neumann\'s Minimax Theorem and Its Usefull Consequence
				2.7.4.3 Upper-Bounding the Performance of RANDOM
		2.8 Exercises
		2.9 Bibliographic Notes
		References
	Chapter 3 Matching Markets with Transfers and Salaries
		3.1 Introduction
		3.2 The Core Studied
 in a Paradigmatic Setting
			3.2.1 The Core via the Lens of Complementarity
			3.2.2 Consequences of Theorem 3.9
			3.2.3 Insights Provided by the Core into the Negotiating Power of Agents
			3.2.4 Entreme Inputations in the Core
		3.3 Approximate Core for the General Pragh Matching Game
			3.3.1 A Two-Thirds-Approximate Core for the Matching Game
		3.4 Many-to-One Matching With Salaries
			3.4.1 The Salary Adjustment Process
			3.4.2 A Model with a Contrinuum of Salaries
		3.5 Matching with Contracts
		3.6 Exercises
		3.7 Bibliographic Notes
		References
	Chapter 4 Objectives
		4.1 Inrtroduction
		4.2 Preliminaries: Individual Choice
			4.2.1 Quasilinear Utility
		4.3 A General Model of Social Choice
			4.3.1 Allocation
			4.3.2 Public Goods
		4.4 Norma
tive Desiderata
			4.4.1 Efficiency
			4.4.2 Fairness
		4.5 Preference Aggregation
			4.5.1 The Egalitarian Lexi-Min Rule
			4.5.2 Social Welfare Fuctions and Utilitatianism
		4.6 Pareto Optimality and Weighted Utilitarianism
		4.7 Partial Equilibrium Analysis and Quasilinear Utility
		4.8 Incentives
			4.8.1 Mechanisms
				4.8.1.1 Dominant Strategy
			4.8.2 Dominant-Strategy Implementation
			4.8.3 Revelation Principle
		4.9 Bibliographical Notes
		References
Part Two Applications(Modern and Traditional
)
	Chapter 5 Applications of Online Matching
		5.1 Introduction
		5.2 Models for Online Advertising
			5.2.1 RANKING with Vertex Weights
				5.2.1.1 Deriving the Optimal Prices
			5.2.2 Fractional and Multi-Matching Models
				5.2.2.1 WATER-FILLING
				5.2.2.2 BALANCE
			5.2.3 Edge-Weighted Online Matching with Free Disposal
			5.2.4 Online Matching with Stochastic Rewards
		5.3 Arrival Models for Other Applications
			5.3.1 Fully Online Matching
				5.3.1.2 WATER-FILLING
			5.3.2 General Vertex Arrivals
			5.3.3 Edge Arrivals
		5.4 Exercises
		5.5 Bibliographic Notes
		References
	Chapter 6 Online Matching in Advertisement Auctions
		6.1 Introduction
		6.2 The AdWords Problem
		6.3 A Family of Algorithms
		6.4 Adversarial Model
		6.5 Stochastic Models
		6.6 Packing
 Mixed Integer Linear Programs
		6.7 Autobidding: A Decentralized Approach to Matching
			6.7.1 Formulation of Autobidding under Constraints
			6.7.2 Optimal Bidding Algorithm
			6.7.3 The Price of Anarchy: Suboptimality of the Decentralized Approach
		6.8 The Design of Sponsored Search Auctions
			6.8.1 The Vickrey-Clarke-Groves(VCG) Auction
			6.8.2 The Generalized Second-Price(GSP) Auction
		6.9 Bibliographic Notes
		References
	Chapter 7 Spectrum Auctions from the Perspective of Matching
		7.1 Introduction
		7.2 Spectrum Auction Algorithms
			7.2.1 Static Matching with Proces
			7.2.2 Simultaneous Multiple-Round Auction
			7.2.3 Clock Auction with Assignment Round
		7.3 Bidder Incentives and Regulator Objectives
		7.4 Substitutes and Complements
			7.4.1 Exposure Risk
			7.4.2 Managing Exposure Risk
		7.5 Descending Clock Auctions
			7.5.1 Seven Weaknesses of the Vickrey Auctions
			7.5.2 Avoiding the Seven Weaknesses
		7.6 Conclusion
		7.7 Bibliographic Notes
		References
	Chapter 8 School Choice
		8.1 Introduction
		8.2 School Choice Problem
		8.3
 Schoold Choice Problem with Indefferences
		8.4 Controlled School Choice Problem
			8.4.1 Preliminaries
			8.4.2 Reserves and Quotas
		8.5 Exercises
		8.6 Bibliographic Notes
		References
	Chapter 9 Kidney Exchange
		9.1 Introduction
		9.2 Preliminaries: The Exchange
  Pool
		9.3 Individual Rational Mechanisms
			9.3.1 General Preferences
			9.3.2 Binary Preferences
		9.4 Market Thickness in Static
 Exchange Pools
		9.5 Optimization
		9.6 Collaboration and Free Riding
			9.6.1 Impossibility Results
			9.6.2 A Point System
		9.7 Dynamic Matching
			9.7.1 Matching in Sparse Pools
			9.7.2 Waiting and Matching in Unbalanced Pools
		9.8 Bibliographic Notes
		References
Part Three Theory
	Chapter 10 Noamative Properties for Object Allocation Problems: Characterizations and Trade-Offs
		10.1 Introduction
		10.2 The Basic Model
		10.3 Top Trading Cycles Rules
		10.4 Serial Dictatorship Rules
		10.5 Endowment Inheritance Rules
		10.6 Deferred Accprance Rules
		10.7 Relationships Between Classes of Rules
		10.8 Exercises
		10.9 Bibliographic Notes
		Acknowledgements
		References
	Chapter 11 Choice and Market Design
		11.1 Introduction
		11.2 Modeling Choice Behavior
			11.2.1 General Model of Choice Behavior
				11.2.1.1 Structure on the Set of Alternative
				11.2.1.2 Structure on the Domain of States and Budget Sets
			11.2.2 Combinatorial Models of Choice Behavior
			11.2.3 Faithful Representations of Combinatorial Choice Models
		11.3 Reveealed Preference and Choice Behavior
			11.3.1 Rationalizability and Revealed Preference
			11.3.2 WARP and Rationaizability
		11.4 Combinatorial Choice Behavior
		11.5 Path-Independent Choice
			11.5.1 The Lattice of Maximal Option Sets of a Path-Independent Choice Fuction
			11.5.2 Maximizer-Collecting Rationalization
		11.6 Combinatorial Choice from Priorities and Capacities
		11.7 Choice and Deferred Accpetance
			11.7.1 Stability
			11.7.2 Deferred Acceptance
		11.8 Exercises
		11.9 Bibliographic Notes
		References
	Chapter 12 Combinatorics of Stable Matchings
		12.1 Introduction
		12.2 The Edge Removal Lemma
			12.2.1 The Structure of Non-
Bipartite Stable b-Matchinds
		12.3 Bipartite Stable Matching
s
			12.3.1 The Lattice of Stable Matchings
			12.3.2 Median Stable b-Matchings
		12.4 Applications
			12.4.1 A Poset Generalization
			12.4.2 The Linking Property of Directed Paths
			12.4.3 Listing the Edge-Colorings of Bipartite Graphs
		12.5 Stable b-Matchings
		12.6 Exercises
		12.7 Bibliographic Notes
		Hints for the Exercises
		References
	Chapter 13 Algorithms of Matching Markets
		13.1 
Introduction
		13.2 Preliminaries
			13.2.1 Definitions of Key Notation and Terminology
			13.2.2 Central Computational Problems
		13.3. Stable Marriage with Ties and Incomplete Lists
			13.3.1 NP-hardness of MAX-SMTI
			13.3.2 Kiraly\'s Approximation Algorithm for MAX-SMTI with One-Sided Ties
		13.4 Stable Roommates without Ties: Two Parameterized Algorithms
			13.4.1 Introduction
			13.4.2 Kernelization for EGAL-SRI-DEC
			13.4.3 Bounded Search Tree Algorithms for EGAL-SRI-DEC
		13.5 Selected Open Questions
		13.6 Bibliographic Notes
		Acknowledgements
		References
	Chapter 14 Generalized Mattchings: Contracts and Networks
		14.1 Introduction
		14.2 The Framework
		14.3 Two-Sided Matching with Contracts
			14.3.1 Many-to-Many Matching with Contracts
			14.3.2 Many-to-One Matching with Co
ntracts
		14.4 Supply Chains and Trading Networks
			14.4.1 Supply Chains
			14.4.2 Trading Networks
		14.5 Transfers
			14.5.1 Applications
		14.6 Exercises
		References
	Chapter 15 Complementarities and Externalities
		15.1 Introduction
		15.2 Existence of Stable Matching, Revisited
			15.2.1 Scarf\'s Lemma
			15.2.2 Rounding
		15.3 Couples Matching
			15.3.1 Choice Fuctions versus Orderings
			15.3.2 Soft Capacity Constraints
		15.4 Complementarity via Constraints
			15.4.1 Regional Capacity Constraints
			15.4.2 Multiple-Dimensional Knapsack Constraints
			15.4.3 Proportionality Constraints
		15.5 Order Methods
			15.5.1 Restricting Preferences
			15.5.2 Large Markets
			15
.5.3 Relax the Stability Requirement
		15.6 Open Questions
		15.7 Bibliographic Notes
		Acknowledgements
		References
	Chapter 16 Large Matching Markets
		16.1
 Random Matching Markets and the Puzzle for the Proposing Side
			16.1.1 Saying the Market is \"Large\" is Not Enough
			16.1.2 Random Matching Markets
			16.1.3 Random Matching Markets with Short Preference Lists
			16.1.4 Unbalanced Random Matching Markets
			16.1.5 Small Random Markets
		16.2 Continuum Matching Markets
			16.2.1 Formal Model
			16.2.2 Cutoffs and Demand
			16.2.3 Calculating a Stable Matching
			16.2.4 Generic Uniqueness of Stable Matchings
			16.2.5 Calculating and Optimizing for Welfare
			16.2.6 Random Sampling and Relation to Discrete Economics
		16.3 Exercises
		16.4 Bibliographic Notes
			16.4.1 Other Applications of Random Matching Markets and Rejection Chains
			16.4.2 Additional Applications of Continuum Models
		References
	Chapter 17 Pseudomarkets
		17.1 Introduction
		17.2 Preliminaries: Walrasian Equilibria in Discrete Settings
			17.2.1 Market Clearing and the Existence of Equilibrium
			17.2.2 Cheapest Distribution Selection
			17.2.3 Token Money versus Trade in Endowments
		17.3 Eliciting Agents\' Utilities
			17.3.1 Fixed-Price Pseudomarkets
			17.3.2 Asymototic Incentive Compatibility
			17.3.3 Preference Reporting
		17.4 Efficiency
			17.4.1 Efficiency of Pseudomarkets
			17.4.2 Pseudomarkets\' Efficiency Edge over Ordinal Mechanisms
			17.4.3 Pseudomarket Representation of Efficienct Assignments
		17.5 Fairness, Multiple-Unit Demand, Priorities, and Constraints
			17.5.1 Fairness
			17.5.2 Multi-Unit Demand
			17.5.3 Priorities and Constraints
		17.6 Exercises
		17.7 Bibliographic Notes
		Acknowledgements
		References
	Chapter 18 Dynamic Matching
		18.1 Introduction
		18.2 Dynamic One-sided Allocations
			18.2.1 Priority Protocols in Discretionary Settings
			18.2.2 Buffer-Queues Mechanism with Private Preferences
		18.3 Dynamic Two-Sided Matching
			18.3.1 Dynamic Matching with Fixed Participants
			18.3.2 Dynamic Matching with Evolving Participants
				18.3.2.1 Dynamic Stability
				18.3.2.2 A Simple Model of Dynamic Centralized Design
				18.3.2.3 Other Considerations
		18.4 Bibliographic Notes
		References
	Chapter 19 Matching with Search Frictions
		19.1 Introduction
		19.2 Benchmark: Frictionless Case
		19.3 Search Frictions: Some Modeling Choices
		19.4 Directed Search
			19.4.1 One-to-One Matching
			19.4.2 Many-to-One Matching
			19.4.3 Miscellaneous
		19.5 Random Search
			19.5.1 Ex-Ante Identical Agents
			19.5.2 Heterogeneous Agents
			19.5.3 Sorting
			19.5.4 Identification in Search and Matching Environments
		19.6 Bibliographical Notes
		References
	Chapter 20 Unraveling
		20.1 Introduction
		20.2 Stable Mechanisms Are Not Enough to Prevent Unraveling
		20.3 Market Timing and the Nature of Offers
		20.4 Uncertainty as a Source of Unraveling
			20.4.1 Insurance
				20.4.1.1 Matching Early versus Matching Later
				20.4.1.2 Early-Contracting Equilibrium
			20.4.2 Beyond Insurance
		20.5 Structural Conditions
		20.6 Information Disclosure and Unraveling
		20.7 Bibliographic Notes
		References
	Chapter 21 Investment in Matching Markets
		21.1 Introduction
		21.2 Motivating Example
		21.3 Model
			21.3.1 Stage 1: Investments
			21.3.2 Stage 2: Oairwaise Stable Outcome
			21.3.3 Stable Matchings
			21.3.4 Equibibrium
		21.4 Private Investment Incentives
		21.5 Efficient Investments
			21.5.1 Marginal Priduct and the Value of Rem
atching
			21.5.2 Main Result
			21.5.3 Generality of the Investment Technology
			21.5.4 One-Sided Investments
			21.5.5 Two-sided Under- and Over-
Investment
			21.5.6 General-Purpose Investments
		21.6 Proofs of the Main Results
		21.7 Discussion
			21.7.1 Investment Efficiency and Strategy-Proofness
			21.7.2 Perfect Competition
			21.7.3 Alternative Approach: Bargaining Function Can Depend on Investment Costs
		21.8 Final Remarks
		21.9 Exercises
		Acknowledgements
		References
	Chapter 22 Signaling in Two-Sided Matching Markets
		22.1 Introduction
		22.2 Setting
			22.2.1 Preferences and Information Revelation
				22.2.1.1 Value of a Match
				22.2.1.2 Transferability
				22.2.1.3 Correlation in Preferences
			22.2.2 Matching Technologies
			22.2.3 Information Revelation and Signaling
				22.2.3.1 Preference Signaling
				22.2.3.2 Quality Signaling
		22.3 Lessons from Theoretical Analyses
			22.3.1 Preference Signaling
				22.3.1.1 Example 1: Decentralized Setting
				22.3.1.2 Example 2: Centralized Setting
			22.3.2 Quality Signaling
				22.3.2.1 Example 3: Recommender System
		22.4 Signaling in Practice
			22.4.1 Preference Signaling
				22.4.1.1 AEA\'s Economists\' Job Market
				22.4.1.2 College Admission
				22.4.1.3 Online Dating
				22.4.1.4 Other Labor Markets
			22.4.2 Quality Signaling
		22.5 Concluding Remarks
		22.6 Bibliographic Notes
		Acknowledgements
		References
	Chapter 23 Two-Sided Markets and Matching Design
		23.1 Introduction
		23.2 General Setup
		23.3 Pricing in Two-Sided Markets
			23.3.1 Profit-Maximizing Prices
			23.3.2 Welfare-Maximizing Pricing
			23.3.3 Distortions
		23.4 Unknown Preference Distribution
		23.5 Matching Design
			23.5.1 One-to=One Matching
				23.5.1.1 Efficient Matching Design
				23.5.1.2 Profit-Maximizing Matching Design
			23.5.2 Many-to-Many Matching Design
				23.5.2.1 Threshold Rules
				23.5.2.2 Distortions
		23.6 Conclusions
		23.7 Bibliographical Notes
		References
Part Four Empirics
	Chapter 24 Matching Market Experiments
		24.1 Introductiom
		24.2 Laboratory Experiments
			24.2.1 Induced-Value Method
			24.2.2 Inducing and Eliciting Beliefs
				24.2.2.1 Approaching Common Knowledge: Common Information
				24.2.2.2 Eliciting Beliefs: Scoring Rules
			24.2.3 Using Robots: Better Control and Larger Scale
				24.2.3.1 Truthful Robots
				24.2.3.2 Empirical Robots
		24.3 Lab-in-the-Field Experiments
		24.4 Field Experiments
			24.4.1 Access
			24.4.2 Timing: PhaseiIn design
			24.4.3 Encouragement Design
		24.5 Bibliographic Notes
		Acknowledgements
		References
	Chapter 25 Empirical Models of Non-Transferable Utility Matching
		25.1 Introduction
		25.2 Empirical Model
		25.3 Analysis Using Final Matches and Stability
			25.3.1 One-to-One Matching
				25.3.1.1 Double-Vertical Model
				25.3.1.2 Heterogenous Preferences
			25.3.2 Few-to=One Matching
			25.3.3 Many-to-One Matching
				25.3.3.1 Known Priorities: School Choice
				25.3.3.2 Unknown Priorities: College Admission
		25.4 Analysis Using Reported Preferences
			25.4.1 Truthful Reports
			25.4.2 Manipulable Mechanisms
		25.5 Applications, Extensions, and Open Questions
			25.5.1 Applications
			25.5.2 Extensions
		25.6 Conslusion
		Acknowledgements
		References
	Chapter 26 Structural Estimation of Matching Markets with Transferable Utility
		26.1 Matching with Unobserved Heterogeneity
			26.1.1 Population and Preferences
			26.1.2 Stability
			26.1.3 Separability
			26.1.4 Equilibrium
		26.2 Identification
			26.2.1 Identifying the Joint Surplus
			26.2.2 Generalized Entropy
			26.2.3 The Logit Model
		26.3 Estimation
			26.3.1 The Maximum Likelihood Estimator
			26.3.2 The Moment-Matching Estimator
			26.3.3 Estimating the Logit Model
			26.3.4 The Maximum-Score Method
		26.4 Computation
			26.4.1 Solving for Equilibrium with Coordinate Descent
			26.4.2 Gradient Descent
			26.4.3 Hybrid Algorithms
		26.5 Other Implementation Issues
			26.5.1 Continuous Types
			26.5.2 Using Several Markets
			26.5.3 Using Additional Data
		26.6 Bibliographic Notes
		Acknowledgements
		Appendix A: Reminders on Convex Analysis
		Appendix B: Asymptotic Distribution of the Logit Moment-Matching Estimator
		References
Part Five Related Topics
	Chapter 27 New Solution Concepts
		27.1 Introduction
		27.2 Obvious Strategy-Proofness
			27.2.1 Definition of Mechanisms in Extensive Form
			27.2.2 Definition of Obvious Strategy-Proofness
			27.2.3 Auction Environment
				27.2.3.1 OSP Characterizes the Ascending Auctino
			27.2.4 Discussion
		27.3 Stability under Incomplete Information
			27.3.1 A Setting for Matching with Incomplete Information
			27.3.2 Inference and Stability
			27.3.3 Assortativity of Stable Outcomes
				27.3.3.1 Proof of Proposition 27.13
			27.3.4 Beliefs
		27.4 Exercises
		27.5 Bibliographic Notes
		References
	Chapter 28 Machine Learning for Matching Markets
		28.1 Introduction
		28.2 Artificial Neural Networks
		28.3 Optimal Auction Design
			28.3.1 Preliminaries
			28.3.2 Methodology
				28.3.2.1 Step 1: Design an Artificial Neural Network
				28.3.2.2 Step 2: Formulate a Loss Fuction and Quantify the Violation of Strategy-Proofness
				28.3.2.3 Step 3: Adopt a Training Procedure
			28.3.3 Illustrative Experimental Results
		28.4 Two-Sided Matching
			28.4.1 Preliminaries
			28.4.2 Randomized matchings
			28.4.3 Deferred Acceptance and RSD
			28.4.4 Methodology
				28.4.4.1 Step 1: Design an Artificial Neural Network
				28.4.4.2 Step 2: Formulate a Loss Fuction and Quantify the Violation of Strategy-Proofness and Stability
				28.4.4.3 Step 3: Adopt a Training Procedure
			28.4.5 Illustrative Experimental Results
		28.5 Discussion
		28.6 Bibliographic Notes
		Acknowledgements
		References
	Chapter 29 Contract Theory
		29.1 Introduction
		29.2 Hidden-Action Models
			29.2.1 A Simple Benchmark Model
			29.2.2 A Model with Limited Liability
			29.2.3 A Robust Model
			29.2.4 Applications of Hidden-Action Models
		29.3 Hidden-Information Models
			29.3.1 A Price-Discrimination Model
			29.3.2 Applications of Hidden-Information Models
		29.4 Exercises
		29.5 Bibliographic Notes
		Acknowledgments
		References
	Chapter 30 Secretaries, Prophets, and Applications to Matching
		30.1 Introduction to Sequential Online Decision-Making
		30.2 The Secretary Problem
		30.3 The Prophet Inequality
		30.4 Application: Online Weighted Matching
			30.4.1 A Secretary Model of Online Matching
			30.4.2 Stochastic Model--Matching with Prophets
			30.4.3 Extension: Matching with Prophets on General Graphs
		30.5 Exercises
		30.6 Bibliographic Notes
		References
	Chapter 31 Exploration and Persuasion
		31.1 Motivation and Problem Formulation
		31.2 Connection to Multi-Armed Bandits
			31.2.1 Optimal Exploration for Two-Armed Bandits
		31.3 Connection with Bayesian Persuasion
			31.3.1 Optimal Persuasion for a Special Case
		31.4 How Much Information to Reveal?
		31.5 \"Hidden Persuasion\" for the General Case
		31.6 Incentivized Exploration via \"Hidden Persuasion\"
		31.7 A Necessary and Sufficient Assumption on the Prior
		31.8 Bibilographic Notes
		Acknowledgements
		References
	Chapter 32 Fairness in Prediction and Allocation
		32.1 Introduction
			32.1.1 What is \"Fairness\" in Classification?
				32.1.1.1 Thinking about Fairness Constraints
		32.2 The Need to Choose
		32.3 Fairness in a Dynamic Model
			32.3.1 A Toy Criminal Justice Model
			32.3.2 Interpreting Theorem 32.13
		32.4 Preserving Information Before Decisions
		32.5 Bibliographic Notes
		References
Index