Market design : a linear programming approach to auctions and matching / Martin Bichler
- Author
- Bichler, Martin
- Published
- Cambridge, United Kingdom ; New York, NY, USA : Cambridge University Press, 2018.
- Copyright Date
- ©2018
- Physical Description
- 1 online resource (xi, 283 pages.)
Access Online
- Contents
- Machine generated contents note: 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 -- 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 -- 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 -- 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 -- 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.
- Subject(s)
- ISBN
- 9781316779873 (electronic bk.)
1316779874 (electronic bk.)
View MARC record | catkey: 22343518