Market Design

Auctions and Matching

by Haeringer

ISBN: 9780262364607 | Copyright 2018

Click here to preview

Instructor Requests

Digital Exam/Desk Copy Print Desk Copy Ancillaries
Tabs
Expand/Collapse All
Contents (pg. vii)
Preface (pg. xv)
1 Introduction (pg. 1)
1.1 Market and Market Design (pg. 1)
1.2 Do We Necessarily Have Prices? (pg. 2)
1.3 More on Markets (pg. 3)
1.4 Market Design: First Example (pg. 6)
2 Simple Auctions (pg. 13)
2.1 Introduction (pg. 13)
2.2 Valuations (pg. 16)
2.3 Payoffs and Objectives (pg. 17)
2.4 Ascending Auctions (pg. 18)
2.5 Second-Price Auction (pg. 25)
2.6 First-Price Auction (pg. 29)
2.7 Revenue Equivalence (pg. 36)
2.8 Reserve Price (pg. 40)
3 An Analysis of eBay (pg. 49)
3.1 Introduction (pg. 49)
3.2 eBay in Detail (pg. 50)
3.3 eBay as a First-Price Auction? (pg. 54)
3.4 Bid Sniping (pg. 54)
3.5 Reserve Price (pg. 59)
4 The Vickrey-Clarke-Groves Auction (pg. 61)
4.1 Introduction (pg. 61)
4.2 The Model (pg. 61)
4.3 The VCG Auction (pg. 63)
4.4 Incentives under the VCG Auction (pg. 67)
4.5 Relation with the Vickrey Auction (pg. 68)
4.6 The Complexity of the VCG Auction (pg. 69)
5 Keyword Auctions (pg. 71)
5.1 Introduction (pg. 71)
5.2 Running Billions and Billions of Auctions (pg. 73)
5.3 The Origins (pg. 74)
5.4 The Google Model: Generalized Second-Price Auction (pg. 76)
5.5 The Facebook Model: VCG for Internet Ads (pg. 91)
6 Spectrum Auctions (pg. 95)
6.1 How Can Spectrum Be Allocated? (pg. 95)
6.2 Issues (pg. 98)
6.3 The Simultaneous Ascending Auction (pg. 104)
6.4 Case Studies (pg. 106)
7 Financial Markets (pg. 113)
7.1 Introduction (pg. 113)
7.2 Treasury Auctions (pg. 113)
7.3 Double Auctions (pg. 119)
7.4 Initial Public Offering (pg. 123)
8 Trading (pg. 127)
8.1 Stock Markets (pg. 127)
8.2 Opening and Closing (pg. 132)
8.3 High-Frequency Trading (pg. 135)
8.4 Alternative Market Designs (pg. 145)
9 The Basic Matching Model (pg. 149)
9.1 The Basic Matching Model (pg. 149)
9.2 Algorithms and Mechanisms (pg. 156)
9.3 Finding Stable Matchings (pg. 159)
9.4 Preferences Over Stable Matchings (pg. 164)
9.5 Incentives with the Deferred Acceptance Algorithm (pg. 167)
10 The Medical Match (pg. 173)
10.1 History (pg. 173)
10.2 The Many-to-One Matching Model (pg. 175)
10.3 Why Stability Matters (pg. 186)
10.4 The Rural Hospital Theorem (pg. 190)
10.5 The Case of Couples and the Engineering Method (pg. 192)
11 Assignment Problems (pg. 197)
11.1 The Basic Model (pg. 197)
11.2 Finding Efficient Assignments (pg. 199)
11.3 Mixed Public-Private Endowments (pg. 212)
12 Probabilistic Assignments (pg. 223)
12.1 Random Assignments (pg. 223)
12.2 Random Serial Dictatorship (pg. 229)
12.3 The Probabilistic Serial Mechanism (pg. 231)
13 School Choice (pg. 239)
13.1 The Many-to-One Assignment Model (pg. 239)
13.2 Competing Algorithms (pg. 245)
13.3 The Problem with the Immediate Acceptance Algorithm (pg. 256)
13.4 Applications (pg. 257)
14 School Choice: Further Developments (pg. 263)
14.1 Weak Priorities (pg. 263)
14.2 Constrained Choice (pg. 276)
15 Course Allocation (pg. 283)
15.1 Preliminaries (pg. 283)
5.2 Bidding for Courses (pg. 284)
15.3 The Harvard Business School Method (pg. 290)
15.4 The Wharton Method (pg. 295)
16 Kidney Exchange (pg. 303)
16.1 Background (pg. 303)
16.2 Trading Kidneys (pg. 305)
16.3 On the Number of Exchanges (pg. 313)
Appendix A: Game Theory (pg. 317)
A.1 Strategic Form Games (pg. 317)
A.2 Extensive Form Games (pg. 319)
A.3 Solving Games (pg. 324)
A.4 Bayesian Games: Games with Incomplete Information (pg. 330)
Appendix B: Mechanism Design (pg. 335)
B.1 Preliminaries (pg. 335)
B.2 The Model (pg. 337)
B.3 Dominant Strategy Implementation (pg. 341)
B.4 Bayesian Mechanism Design (pg. 344)
Appendix C: Order Statistics (pg. 349)
C.1 Expected Highest Valuation (pg. 349)
C.2 Expected Second-Highest Valuation (pg. 351)
C.3 Conditional Expectation of the Highest Valuation (pg. 352)
C.4 Changing the Upper and Lower Bounds (pg. 353)
Notes (pg. 355)
References (pg. 365)
Index (pg. 369)
Contents (pg. vii)
Preface (pg. xv)
1. Introduction (pg. 1)
1.1. Market and Market Design (pg. 1)
1.2. Do We Necessarily Have Prices? (pg. 2)
1.3. More on Markets (pg. 3)
1.3.1. What a Market Needs to Work (pg. 4)
1.3.2. Commodities (pg. 5)
1.4. Market Design: First Example (pg. 6)
1.4.1. Feeding America (pg. 6)
1.4.2. The First Design (pg. 7)
1.4.3. The Problems … (pg. 9)
1.4.4. …and a Solution (pg. 10)
1.4.5. Results (pg. 11)
2. Simple Auctions (pg. 13)
2.1. Introduction (pg. 13)
2.1.1. Auctions: A Definition (pg. 14)
2.1.2. Auctions Are Everywhere (pg. 14)
2.2. Valuations (pg. 16)
2.3. Payoffs and Objectives (pg. 17)
2.4. Ascending Auctions (pg. 18)
2.4.1. The English Auctions (pg. 18)
2.4.2. Bids, Strategies, and Payoffs in the English Auctions (pg. 21)
2.4.3. Ticking Price (pg. 22)
2.4.4. Truthful Bidding (pg. 23)
2.5. Second-Price Auction (pg. 25)
2.5.1. The Essence of the English Auction (pg. 25)
2.5.2. The Vickrey Auction (pg. 26)
2.5.3. English versus Second-Price Auctions (pg. 28)
2.6. First-Price Auction (pg. 29)
2.6.1. Definition (pg. 29)
2.6.2. Optimal Bids in the First-Price Auction (pg. 30)
2.6.3. Dutch Auction (pg. 34)
2.7. Revenue Equivalence (pg. 36)
2.8. Reserve Price (pg. 40)
2.8.1. Optimal Reserve Price (pg. 42)
2.8.2. Reserve Price versus Adding More Bidders (pg. 45)
3. An Analysis of eBay (pg. 49)
3.1. Introduction (pg. 49)
3.2. eBay in Detail (pg. 50)
3.2.1. Proxy Bidding (pg. 50)
3.2.2. Bids and Bid Increments (pg. 51)
3.2.3. Updating Rules (pg. 51)
3.3. eBay as a First-Price Auction? (pg. 54)
3.4. Bid Sniping (pg. 54)
3.4.1. Amazon versus eBay (pg. 55)
3.4.2. Data Analysis (pg. 56)
3.5. Reserve Price (pg. 59)
4. The Vickrey-Clarke-Groves Auction (pg. 61)
4.1. Introduction (pg. 61)
4.2. The Model (pg. 61)
4.3. The VCG Auction (pg. 63)
4.3.1. Computing the Optimal Assignment (pg. 63)
4.3.2. Calculating Prices (pg. 66)
4.4. Incentives under the VCG Auction (pg. 67)
4.5. Relation with the Vickrey Auction (pg. 68)
4.6. The Complexity of the VCG Auction (pg. 69)
5. Keyword Auctions (pg. 71)
5.1. Introduction (pg. 71)
5.2. Running Billions and Billions of Auctions (pg. 73)
5.3. The Origins (pg. 74)
5.3.1. Payoff Flows (pg. 75)
5.4. The Google Model: Generalized Second-Price Auction (pg. 76)
5.4.1. Quality Scores (pg. 76)
5.4.2. Truthtelling under the GSP Auction (pg. 78)
5.4.3. Equilibrium under the GSP Auction (pg. 78)
5.4.4. Assumptions about the Long-Run Equilibria (pg. 79)
5.4.5. Refinement: Envy-Free Equilibrium (pg. 79)
5.4.6. The Generalized English Auction (pg. 88)
5.5. The Facebook Model: VCG for Internet Ads (pg. 91)
5.5.1. Comparing VCG and GSP Auctions (pg. 91)
5.5.2. The Rationale for VCG (pg. 94)
6. Spectrum Auctions (pg. 95)
6.1. How Can Spectrum Be Allocated? (pg. 95)
6.1.1. Lotteries (pg. 95)
6.1.2. Beauty Contests (pg. 96)
6.1.3. Why Run Auctions? (pg. 97)
6.2. Issues (pg. 98)
6.2.1. General Issues (pg. 98)
6.2.2. Collusion, Demand Reduction, and Entry (pg. 99)
6.2.3. Maximum Revenue (pg. 101)
6.2.4. The Exposure Problem (pg. 102)
6.2.5. Winner's Curse (pg. 103)
6.3. The Simultaneous Ascending Auction (pg. 104)
6.4. Case Studies (pg. 106)
6.4.1. The U.S. 1994 PCS Broadband Auction (pg. 106)
6.4.2. Mistakes (pg. 109)
7. Financial Markets (pg. 113)
7.1. Introduction (pg. 113)
7.2. Treasury Auctions (pg. 113)
7.2.1. Outline (pg. 113)
7.2.2. How Treasury Auctions Work (pg. 115)
7.2.3. Analysis (pg. 118)
7.3. Double Auctions (pg. 119)
7.4. Initial Public Offering (pg. 123)
7.4.1. Allocation and Pricing through Contracts (pg. 124)
7.4.2. Auctions for IPOs (pg. 124)
8. Trading (pg. 127)
8.1. Stock Markets (pg. 127)
8.2. Opening and Closing (pg. 132)
8.3. High-Frequency Trading (pg. 135)
8.3.1. Market Structure (pg. 135)
8.3.2. Market Regulation (pg. 137)
8.3.3. Surfing on the Latency (pg. 139)
8.3.4. What Is the Matter with High Frequencies? (pg. 141)
8.3.5. A Flawed Market Design? (pg. 143)
8.4. Alternative Market Designs (pg. 145)
8.4.1. Slowing Down Markets? (pg. 145)
8.4.2. Frequent Batch Auctions (pg. 147)
9. The Basic Matching Model (pg. 149)
9.1. The Basic Matching Model (pg. 149)
9.1.1. Preferences (pg. 150)
9.1.2. Matching (pg. 152)
9.1.3. Stability (pg. 153)
9.2. Algorithms and Mechanisms (pg. 156)
9.2.1. Algorithms? (pg. 156)
9.2.2. Matching Mechanism (pg. 159)
9.3. Finding Stable Matchings (pg. 159)
9.3.1. The Deferred Acceptance Algorithm (pg. 160)
9.3.2. Deferred Acceptance and Stable Matchings (pg. 162)
9.4. Preferences Over Stable Matchings (pg. 164)
9.4.1. Musician-Optimal and Singer-Optimal Matchings (pg. 164)
9.4.2. Proofs (pg. 165)
9.5. Incentives with the Deferred Acceptance Algorithm (pg. 167)
10. The Medical Match (pg. 173)
10.1. History (pg. 173)
10.2. The Many-to-One Matching Model (pg. 175)
10.2.1. Preferences in the Many-to-One Matching Model (pg. 176)
10.2.2. Matchings and Stability in a Many-to-One Matching Model (pg. 179)
10.2.3. Finding Stable Matchings (pg. 182)
10.2.4. One-to-One v. Many-to-One Matchings: Similarities and Differences (pg. 184)
10.3. Why Stability Matters (pg. 186)
10.3.1. A Natural Experiment (pg. 186)
10.3.2. Unraveling in the Lab (pg. 187)
10.4. The Rural Hospital Theorem (pg. 190)
10.5. The Case of Couples and the Engineering Method (pg. 192)
10.5.1. A Very Complex Problem (pg. 192)
10.5.2. When Theory Fails (pg. 193)
10.5.3. Fixing the NRMP (pg. 194)
11. Assignment Problems (pg. 197)
11.1. The Basic Model (pg. 197)
11.1.1. Public versus Private Endowments (pg. 198)
11.1.2. Evaluating Assignments (pg. 198)
11.2. Finding Efficient Assignments (pg. 199)
11.2.1. Serial Dictators (pg. 199)
11.2.2. Trading Cycles (pg. 200)
11.2.3. Implementing Allocation Rules (pg. 205)
11.2.4. Individual Rationality and the Core (pg. 210)
11.3. Mixed Public-Private Endowments (pg. 212)
11.3.1. Inefficient Mechanisms (pg. 213)
11.3.2. Two Efficient Solutions (pg. 217)
12. Probabilistic Assignments (pg. 223)
12.1. Random Assignments (pg. 223)
12.1.1. Preliminaries (pg. 223)
12.1.2. The Birkhoff–von Neumann Theorem (pg. 225)
12.1.3. Evaluating Random Assignments (pg. 227)
12.2. Random Serial Dictatorship (pg. 229)
12.3. The Probabilistic Serial Mechanism (pg. 231)
13. School Choice (pg. 239)
13.1. The Many-to-One Assignment Model (pg. 239)
13.1.1. Preferences versus Priorities (pg. 239)
13.1.2. The Model (pg. 241)
13.1.3. Assignments (pg. 241)
13.1.4. Stability and Efficiency (pg. 242)
13.2. Competing Algorithms (pg. 245)
13.2.1. The Role of Each Side of the Market (pg. 245)
13.2.2. The Deferred Acceptance Algorithm (pg. 246)
13.2.3. The Immediate Acceptance Algorithm (pg. 248)
13.2.4. Top Trading Cycles (pg. 250)
13.3. The Problem with the Immediate Acceptance Algorithm (pg. 256)
13.4. Applications (pg. 257)
13.4.1. The Boston School Match (pg. 257)
13.4.2. The New York City School Match (pg. 259)
14. School Choice: Further Developments (pg. 263)
14.1. Weak Priorities (pg. 263)
14.1.1. The Problem (pg. 263)
14.1.2. Efficiency Loss (pg. 264)
14.1.3. The Student-Optimal Assignment with Weak Priorities (pg. 265)
14.1.4. Restoring Efficiency (pg. 266)
14.1.5. How to Break Ties If You Must (pg. 272)
14.2. Constrained Choice (pg. 276)
14.2.1. Issues (pg. 277)
14.2.2. From Very Manipulable to Less Manipulable (pg. 279)
15. Course Allocation (pg. 283)
15.1. Preliminaries (pg. 283)
15.2. Bidding for Courses (pg. 284)
15.2.1. The Bidding and Allocation Process (pg. 285)
15.2.2. Issues: Nonmarket Prices and Inefficiency (pg. 286)
15.2.3. Deferred Acceptance with Bids (pg. 288)
15.3. The Harvard Business School Method (pg. 290)
15.3.1. The Harvard Draft Mechanism (pg. 290)
15.3.2. Strategic Behavior (pg. 291)
15.3.3. Welfare (pg. 293)
15.4. The Wharton Method (pg. 295)
15.4.1. Approximate Competitive Equilibrium from Equal Incomes (pg. 296)
15.4.2. The Wharton Experiment (pg. 298)
16. Kidney Exchange (pg. 303)
16.1. Background (pg. 303)
16.2. Trading Kidneys (pg. 305)
16.2.1. Trades versus Waiting List (pg. 306)
16.2.2. The Kidney Exchange Algorithm (pg. 306)
16.2.3. Chain Selection Rules (pg. 309)
16.2.4. Efficiency and Incentives (pg. 311)
16.3. On the Number of Exchanges (pg. 313)
Appendix A: Game Theory (pg. 317)
A.1. Strategic Form Games (pg. 317)
A.1.1. Definition (pg. 317)
A.1.2. Pure and Mixed Strategies (pg. 318)
A.2. Extensive Form Games (pg. 319)
A.2.1. Definition (pg. 320)
A.2.2. Strategies (pg. 321)
A.2.3. Imperfect Information (pg. 322)
A.3. Solving Games (pg. 324)
A.3.1. Dominated and Dominant Strategies (pg. 324)
A.3.2. Elimination of Dominated Strategies (pg. 326)
A.3.3. Nash Equilibrium (pg. 328)
A.4. Bayesian Games: Games with Incomplete Information (pg. 330)
A.4.1. Introductory Example (pg. 330)
A.4.2. Definition (pg. 331)
Appendix B: Mechanism Design (pg. 335)
B.1. Preliminaries (pg. 335)
B.2. The Model (pg. 337)
B.2.1. Mechanism (pg. 337)
B.2.2. Implementing Social Choice Functions (pg. 339)
B.2.3. Direct versus Indirect Mechanism (pg. 340)
B.3. Dominant Strategy Implementation (pg. 341)
B.3.1. The Revelation Principle (pg. 341)
B.3.2. The Gibbard-Satterthwaite Theorem (pg. 342)
B.3.3. The Vickrey-Clarke-Groves Mechanism (pg. 343)
B.4. Bayesian Mechanism Design (pg. 344)
B.4.1. Bayesian Incentive Compatibility (pg. 344)
B.4.2. Trading: The Myerson-Satterthwaite Theorem (pg. 345)
Appendix C: Order Statistics (pg. 349)
C.1. Expected Highest Valuation (pg. 349)
C.1.1. Obtaining the Cumulative Density Function (pg. 350)
C.1.2. Obtaining the Probability Density Function (pg. 350)
C.1.3. Calculate the Expectation (pg. 350)
C.2. Expected Second-Highest Valuation (pg. 351)
C.3. Conditional Expectation of the Highest Valuation (pg. 352)
C.4. Changing the Upper and Lower Bounds (pg. 353)
Notes (pg. 355)
Chapter 1 (pg. 355)
Chapter 2 (pg. 355)
Chapter 3 (pg. 356)
Chapter 4 (pg. 357)
Chapter 5 (pg. 357)
Chapter 6 (pg. 357)
Chapter 7 (pg. 358)
Chapter 8 (pg. 358)
Chapter 9 (pg. 358)
Chapter 10 (pg. 359)
Chapter 11 (pg. 360)
Chapter 12 (pg. 360)
Chapter 13 (pg. 360)
Chapter 14 (pg. 361)
Chapter 15 (pg. 361)
Chapter 16 (pg. 362)
Appendix A (pg. 362)
Appendix B (pg. 362)
References (pg. 365)
Index (pg. 369)
1.1. Market and Market Design (pg. 1)
1.2. Do We Necessarily Have Prices? (pg. 2)
1.3. More on Markets (pg. 3)
1.3.1. What a Market Needs to Work (pg. 4)
1.3.2. Commodities (pg. 5)
1.4. Market Design: First Example (pg. 6)
1.4.1. Feeding America (pg. 6)
1.4.2. The First Design (pg. 7)
1.4.3. The Problems … (pg. 9)
1.4.4. …and a Solution (pg. 10)
1.4.5. Results (pg. 11)
2.1. Introduction (pg. 13)
2.1.1. Auctions: A Definition (pg. 14)
2.1.2. Auctions Are Everywhere (pg. 14)
2.2. Valuations (pg. 16)
2.3. Payoffs and Objectives (pg. 17)
2.4. Ascending Auctions (pg. 18)
2.4.1. The English Auctions (pg. 18)
2.4.2. Bids, Strategies, and Payoffs in the English Auctions (pg. 21)
2.4.3. Ticking Price (pg. 22)
2.4.4. Truthful Bidding (pg. 23)
2.5. Second-Price Auction (pg. 25)
2.5.1. The Essence of the English Auction (pg. 25)
2.5.2. The Vickrey Auction (pg. 26)
2.5.3. English versus Second-Price Auctions (pg. 28)
2.6. First-Price Auction (pg. 29)
2.6.1. Definition (pg. 29)
2.6.2. Optimal Bids in the First-Price Auction (pg. 30)
2.6.3. Dutch Auction (pg. 34)
2.7. Revenue Equivalence (pg. 36)
2.8. Reserve Price (pg. 40)
2.8.1. Optimal Reserve Price (pg. 42)
2.8.2. Reserve Price versus Adding More Bidders (pg. 45)
3.1. Introduction (pg. 49)
3.2. eBay in Detail (pg. 50)
3.2.1. Proxy Bidding (pg. 50)
3.2.2. Bids and Bid Increments (pg. 51)
3.2.3. Updating Rules (pg. 51)
3.3. eBay as a First-Price Auction? (pg. 54)
3.4. Bid Sniping (pg. 54)
3.4.1. Amazon versus eBay (pg. 55)
3.4.2. Data Analysis (pg. 56)
3.5. Reserve Price (pg. 59)
4.1. Introduction (pg. 61)
4.2. The Model (pg. 61)
4.3. The VCG Auction (pg. 63)
4.3.1. Computing the Optimal Assignment (pg. 63)
4.3.2. Calculating Prices (pg. 66)
4.4. Incentives under the VCG Auction (pg. 67)
4.5. Relation with the Vickrey Auction (pg. 68)
4.6. The Complexity of the VCG Auction (pg. 69)
5.1. Introduction (pg. 71)
5.2. Running Billions and Billions of Auctions (pg. 73)
5.3. The Origins (pg. 74)
5.3.1. Payoff Flows (pg. 75)
5.4. The Google Model: Generalized Second-Price Auction (pg. 76)
5.4.1. Quality Scores (pg. 76)
5.4.2. Truthtelling under the GSP Auction (pg. 78)
5.4.3. Equilibrium under the GSP Auction (pg. 78)
5.4.4. Assumptions about the Long-Run Equilibria (pg. 79)
5.4.5. Refinement: Envy-Free Equilibrium (pg. 79)
5.4.6. The Generalized English Auction (pg. 88)
5.5. The Facebook Model: VCG for Internet Ads (pg. 91)
5.5.1. Comparing VCG and GSP Auctions (pg. 91)
5.5.2. The Rationale for VCG (pg. 94)
6.1. How Can Spectrum Be Allocated? (pg. 95)
6.1.1. Lotteries (pg. 95)
6.1.2. Beauty Contests (pg. 96)
6.1.3. Why Run Auctions? (pg. 97)
6.2. Issues (pg. 98)
6.2.1. General Issues (pg. 98)
6.2.2. Collusion, Demand Reduction, and Entry (pg. 99)
6.2.3. Maximum Revenue (pg. 101)
6.2.4. The Exposure Problem (pg. 102)
6.2.5. Winner's Curse (pg. 103)
6.3. The Simultaneous Ascending Auction (pg. 104)
6.4. Case Studies (pg. 106)
6.4.1. The U.S. 1994 PCS Broadband Auction (pg. 106)
6.4.2. Mistakes (pg. 109)
7.1. Introduction (pg. 113)
7.2. Treasury Auctions (pg. 113)
7.2.1. Outline (pg. 113)
7.2.2. How Treasury Auctions Work (pg. 115)
7.2.3. Analysis (pg. 118)
7.3. Double Auctions (pg. 119)
7.4. Initial Public Offering (pg. 123)
7.4.1. Allocation and Pricing through Contracts (pg. 124)
7.4.2. Auctions for IPOs (pg. 124)
8.1. Stock Markets (pg. 127)
8.2. Opening and Closing (pg. 132)
8.3. High-Frequency Trading (pg. 135)
8.3.1. Market Structure (pg. 135)
8.3.2. Market Regulation (pg. 137)
8.3.3. Surfing on the Latency (pg. 139)
8.3.4. What Is the Matter with High Frequencies? (pg. 141)
8.3.5. A Flawed Market Design? (pg. 143)
8.4. Alternative Market Designs (pg. 145)
8.4.1. Slowing Down Markets? (pg. 145)
8.4.2. Frequent Batch Auctions (pg. 147)
9.1. The Basic Matching Model (pg. 149)
9.1.1. Preferences (pg. 150)
9.1.2. Matching (pg. 152)
9.1.3. Stability (pg. 153)
9.2. Algorithms and Mechanisms (pg. 156)
9.2.1. Algorithms? (pg. 156)
9.2.2. Matching Mechanism (pg. 159)
9.3. Finding Stable Matchings (pg. 159)
9.3.1. The Deferred Acceptance Algorithm (pg. 160)
9.3.2. Deferred Acceptance and Stable Matchings (pg. 162)
9.4. Preferences Over Stable Matchings (pg. 164)
9.4.1. Musician-Optimal and Singer-Optimal Matchings (pg. 164)
9.4.2. Proofs (pg. 165)
9.5. Incentives with the Deferred Acceptance Algorithm (pg. 167)
10.1. History (pg. 173)
10.2. The Many-to-One Matching Model (pg. 175)
10.2.1. Preferences in the Many-to-One Matching Model (pg. 176)
10.2.2. Matchings and Stability in a Many-to-One Matching Model (pg. 179)
10.2.3. Finding Stable Matchings (pg. 182)
10.2.4. One-to-One v. Many-to-One Matchings: Similarities and Differences (pg. 184)
10.3. Why Stability Matters (pg. 186)
10.3.1. A Natural Experiment (pg. 186)
10.3.2. Unraveling in the Lab (pg. 187)
10.4. The Rural Hospital Theorem (pg. 190)
10.5. The Case of Couples and the Engineering Method (pg. 192)
10.5.1. A Very Complex Problem (pg. 192)
10.5.2. When Theory Fails (pg. 193)
10.5.3. Fixing the NRMP (pg. 194)
11.1. The Basic Model (pg. 197)
11.1.1. Public versus Private Endowments (pg. 198)
11.1.2. Evaluating Assignments (pg. 198)
11.2. Finding Efficient Assignments (pg. 199)
11.2.1. Serial Dictators (pg. 199)
11.2.2. Trading Cycles (pg. 200)
11.2.3. Implementing Allocation Rules (pg. 205)
11.2.4. Individual Rationality and the Core (pg. 210)
11.3. Mixed Public-Private Endowments (pg. 212)
11.3.1. Inefficient Mechanisms (pg. 213)
11.3.2. Two Efficient Solutions (pg. 217)
12.1. Random Assignments (pg. 223)
12.1.1. Preliminaries (pg. 223)
12.1.2. The Birkhoff–von Neumann Theorem (pg. 225)
12.1.3. Evaluating Random Assignments (pg. 227)
12.2. Random Serial Dictatorship (pg. 229)
12.3. The Probabilistic Serial Mechanism (pg. 231)
13.1. The Many-to-One Assignment Model (pg. 239)
13.1.1. Preferences versus Priorities (pg. 239)
13.1.2. The Model (pg. 241)
13.1.3. Assignments (pg. 241)
13.1.4. Stability and Efficiency (pg. 242)
13.2. Competing Algorithms (pg. 245)
13.2.1. The Role of Each Side of the Market (pg. 245)
13.2.2. The Deferred Acceptance Algorithm (pg. 246)
13.2.3. The Immediate Acceptance Algorithm (pg. 248)
13.2.4. Top Trading Cycles (pg. 250)
13.3. The Problem with the Immediate Acceptance Algorithm (pg. 256)
13.4. Applications (pg. 257)
13.4.1. The Boston School Match (pg. 257)
13.4.2. The New York City School Match (pg. 259)
14.1. Weak Priorities (pg. 263)
14.1.1. The Problem (pg. 263)
14.1.2. Efficiency Loss (pg. 264)
14.1.3. The Student-Optimal Assignment with Weak Priorities (pg. 265)
14.1.4. Restoring Efficiency (pg. 266)
14.1.5. How to Break Ties If You Must (pg. 272)
14.2. Constrained Choice (pg. 276)
14.2.1. Issues (pg. 277)
14.2.2. From Very Manipulable to Less Manipulable (pg. 279)
15.1. Preliminaries (pg. 283)
15.2. Bidding for Courses (pg. 284)
15.2.1. The Bidding and Allocation Process (pg. 285)
15.2.2. Issues: Nonmarket Prices and Inefficiency (pg. 286)
15.2.3. Deferred Acceptance with Bids (pg. 288)
15.3. The Harvard Business School Method (pg. 290)
15.3.1. The Harvard Draft Mechanism (pg. 290)
15.3.2. Strategic Behavior (pg. 291)
15.3.3. Welfare (pg. 293)
15.4. The Wharton Method (pg. 295)
15.4.1. Approximate Competitive Equilibrium from Equal Incomes (pg. 296)
15.4.2. The Wharton Experiment (pg. 298)
16.1. Background (pg. 303)
16.2. Trading Kidneys (pg. 305)
16.2.1. Trades versus Waiting List (pg. 306)
16.2.2. The Kidney Exchange Algorithm (pg. 306)
16.2.3. Chain Selection Rules (pg. 309)
16.2.4. Efficiency and Incentives (pg. 311)
16.3. On the Number of Exchanges (pg. 313)
A.1. Strategic Form Games (pg. 317)
A.1.1. Definition (pg. 317)
A.1.2. Pure and Mixed Strategies (pg. 318)
A.2. Extensive Form Games (pg. 319)
A.2.1. Definition (pg. 320)
A.2.2. Strategies (pg. 321)
A.2.3. Imperfect Information (pg. 322)
A.3. Solving Games (pg. 324)
A.3.1. Dominated and Dominant Strategies (pg. 324)
A.3.2. Elimination of Dominated Strategies (pg. 326)
A.3.3. Nash Equilibrium (pg. 328)
A.4. Bayesian Games: Games with Incomplete Information (pg. 330)
A.4.1. Introductory Example (pg. 330)
A.4.2. Definition (pg. 331)
B.1. Preliminaries (pg. 335)
B.2. The Model (pg. 337)
B.2.1. Mechanism (pg. 337)
B.2.2. Implementing Social Choice Functions (pg. 339)
B.2.3. Direct versus Indirect Mechanism (pg. 340)
B.3. Dominant Strategy Implementation (pg. 341)
B.3.1. The Revelation Principle (pg. 341)
B.3.2. The Gibbard-Satterthwaite Theorem (pg. 342)
B.3.3. The Vickrey-Clarke-Groves Mechanism (pg. 343)
B.4. Bayesian Mechanism Design (pg. 344)
B.4.1. Bayesian Incentive Compatibility (pg. 344)
B.4.2. Trading: The Myerson-Satterthwaite Theorem (pg. 345)
C.1. Expected Highest Valuation (pg. 349)
C.1.1. Obtaining the Cumulative Density Function (pg. 350)
C.1.2. Obtaining the Probability Density Function (pg. 350)
C.1.3. Calculate the Expectation (pg. 350)
C.2. Expected Second-Highest Valuation (pg. 351)
C.3. Conditional Expectation of the Highest Valuation (pg. 352)
C.4. Changing the Upper and Lower Bounds (pg. 353)
Chapter 1 (pg. 355)
Chapter 2 (pg. 355)
Chapter 3 (pg. 356)
Chapter 4 (pg. 357)
Chapter 5 (pg. 357)
Chapter 6 (pg. 357)
Chapter 7 (pg. 358)
Chapter 8 (pg. 358)
Chapter 9 (pg. 358)
Chapter 10 (pg. 359)
Chapter 11 (pg. 360)
Chapter 12 (pg. 360)
Chapter 13 (pg. 360)
Chapter 14 (pg. 361)
Chapter 15 (pg. 361)
Chapter 16 (pg. 362)
Appendix A (pg. 362)
Appendix B (pg. 362)
1.1. Market and Market Design (pg. 1)
1.2. Do We Necessarily Have Prices? (pg. 2)
1.3. More on Markets (pg. 3)
1.3.1. What a Market Needs to Work (pg. 4)
1.3.2. Commodities (pg. 5)
1.4. Market Design: First Example (pg. 6)
1.4.1. Feeding America (pg. 6)
1.4.2. The First Design (pg. 7)
1.4.3. The Problems … (pg. 9)
1.4.4. …and a Solution (pg. 10)
1.4.5. Results (pg. 11)
2.1. Introduction (pg. 13)
2.1.1. Auctions: A Definition (pg. 14)
2.1.2. Auctions Are Everywhere (pg. 14)
2.2. Valuations (pg. 16)
2.3. Payoffs and Objectives (pg. 17)
2.4. Ascending Auctions (pg. 18)
2.4.1. The English Auctions (pg. 18)
2.4.2. Bids, Strategies, and Payoffs in the English Auctions (pg. 21)
2.4.3. Ticking Price (pg. 22)
2.4.4. Truthful Bidding (pg. 23)
2.5. Second-Price Auction (pg. 25)
2.5.1. The Essence of the English Auction (pg. 25)
2.5.2. The Vickrey Auction (pg. 26)
2.5.3. English versus Second-Price Auctions (pg. 28)
2.6. First-Price Auction (pg. 29)
2.6.1. Definition (pg. 29)
2.6.2. Optimal Bids in the First-Price Auction (pg. 30)
2.6.3. Dutch Auction (pg. 34)
2.7. Revenue Equivalence (pg. 36)
2.8. Reserve Price (pg. 40)
2.8.1. Optimal Reserve Price (pg. 42)
2.8.2. Reserve Price versus Adding More Bidders (pg. 45)
3.1. Introduction (pg. 49)
3.2. eBay in Detail (pg. 50)
3.2.1. Proxy Bidding (pg. 50)
3.2.2. Bids and Bid Increments (pg. 51)
3.2.3. Updating Rules (pg. 51)
3.3. eBay as a First-Price Auction? (pg. 54)
3.4. Bid Sniping (pg. 54)
3.4.1. Amazon versus eBay (pg. 55)
3.4.2. Data Analysis (pg. 56)
3.5. Reserve Price (pg. 59)
4.1. Introduction (pg. 61)
4.2. The Model (pg. 61)
4.3. The VCG Auction (pg. 63)
4.3.1. Computing the Optimal Assignment (pg. 63)
4.3.2. Calculating Prices (pg. 66)
4.4. Incentives under the VCG Auction (pg. 67)
4.5. Relation with the Vickrey Auction (pg. 68)
4.6. The Complexity of the VCG Auction (pg. 69)
5.1. Introduction (pg. 71)
5.2. Running Billions and Billions of Auctions (pg. 73)
5.3. The Origins (pg. 74)
5.3.1. Payoff Flows (pg. 75)
5.4. The Google Model: Generalized Second-Price Auction (pg. 76)
5.4.1. Quality Scores (pg. 76)
5.4.2. Truthtelling under the GSP Auction (pg. 78)
5.4.3. Equilibrium under the GSP Auction (pg. 78)
5.4.4. Assumptions about the Long-Run Equilibria (pg. 79)
5.4.5. Refinement: Envy-Free Equilibrium (pg. 79)
5.4.6. The Generalized English Auction (pg. 88)
5.5. The Facebook Model: VCG for Internet Ads (pg. 91)
5.5.1. Comparing VCG and GSP Auctions (pg. 91)
5.5.2. The Rationale for VCG (pg. 94)
6.1. How Can Spectrum Be Allocated? (pg. 95)
6.1.1. Lotteries (pg. 95)
6.1.2. Beauty Contests (pg. 96)
6.1.3. Why Run Auctions? (pg. 97)
6.2. Issues (pg. 98)
6.2.1. General Issues (pg. 98)
6.2.2. Collusion, Demand Reduction, and Entry (pg. 99)
6.2.3. Maximum Revenue (pg. 101)
6.2.4. The Exposure Problem (pg. 102)
6.2.5. Winner's Curse (pg. 103)
6.3. The Simultaneous Ascending Auction (pg. 104)
6.4. Case Studies (pg. 106)
6.4.1. The U.S. 1994 PCS Broadband Auction (pg. 106)
6.4.2. Mistakes (pg. 109)
7.1. Introduction (pg. 113)
7.2. Treasury Auctions (pg. 113)
7.2.1. Outline (pg. 113)
7.2.2. How Treasury Auctions Work (pg. 115)
7.2.3. Analysis (pg. 118)
7.3. Double Auctions (pg. 119)
7.4. Initial Public Offering (pg. 123)
7.4.1. Allocation and Pricing through Contracts (pg. 124)
7.4.2. Auctions for IPOs (pg. 124)
8.1. Stock Markets (pg. 127)
8.2. Opening and Closing (pg. 132)
8.3. High-Frequency Trading (pg. 135)
8.3.1. Market Structure (pg. 135)
8.3.2. Market Regulation (pg. 137)
8.3.3. Surfing on the Latency (pg. 139)
8.3.4. What Is the Matter with High Frequencies? (pg. 141)
8.3.5. A Flawed Market Design? (pg. 143)
8.4. Alternative Market Designs (pg. 145)
8.4.1. Slowing Down Markets? (pg. 145)
8.4.2. Frequent Batch Auctions (pg. 147)
9.1. The Basic Matching Model (pg. 149)
9.1.1. Preferences (pg. 150)
9.1.2. Matching (pg. 152)
9.1.3. Stability (pg. 153)
9.2. Algorithms and Mechanisms (pg. 156)
9.2.1. Algorithms? (pg. 156)
9.2.2. Matching Mechanism (pg. 159)
9.3. Finding Stable Matchings (pg. 159)
9.3.1. The Deferred Acceptance Algorithm (pg. 160)
9.3.2. Deferred Acceptance and Stable Matchings (pg. 162)
9.4. Preferences Over Stable Matchings (pg. 164)
9.4.1. Musician-Optimal and Singer-Optimal Matchings (pg. 164)
9.4.2. Proofs (pg. 165)
9.5. Incentives with the Deferred Acceptance Algorithm (pg. 167)
10.1. History (pg. 173)
10.2. The Many-to-One Matching Model (pg. 175)
10.2.1. Preferences in the Many-to-One Matching Model (pg. 176)
10.2.2. Matchings and Stability in a Many-to-One Matching Model (pg. 179)
10.2.3. Finding Stable Matchings (pg. 182)
10.2.4. One-to-One v. Many-to-One Matchings: Similarities and Differences (pg. 184)
10.3. Why Stability Matters (pg. 186)
10.3.1. A Natural Experiment (pg. 186)
10.3.2. Unraveling in the Lab (pg. 187)
10.4. The Rural Hospital Theorem (pg. 190)
10.5. The Case of Couples and the Engineering Method (pg. 192)
10.5.1. A Very Complex Problem (pg. 192)
10.5.2. When Theory Fails (pg. 193)
10.5.3. Fixing the NRMP (pg. 194)
11.1. The Basic Model (pg. 197)
11.1.1. Public versus Private Endowments (pg. 198)
11.1.2. Evaluating Assignments (pg. 198)
11.2. Finding Efficient Assignments (pg. 199)
11.2.1. Serial Dictators (pg. 199)
11.2.2. Trading Cycles (pg. 200)
11.2.3. Implementing Allocation Rules (pg. 205)
11.2.4. Individual Rationality and the Core (pg. 210)
11.3. Mixed Public-Private Endowments (pg. 212)
11.3.1. Inefficient Mechanisms (pg. 213)
11.3.2. Two Efficient Solutions (pg. 217)
12.1. Random Assignments (pg. 223)
12.1.1. Preliminaries (pg. 223)
12.1.2. The Birkhoff–von Neumann Theorem (pg. 225)
12.1.3. Evaluating Random Assignments (pg. 227)
12.2. Random Serial Dictatorship (pg. 229)
12.3. The Probabilistic Serial Mechanism (pg. 231)
13.1. The Many-to-One Assignment Model (pg. 239)
13.1.1. Preferences versus Priorities (pg. 239)
13.1.2. The Model (pg. 241)
13.1.3. Assignments (pg. 241)
13.1.4. Stability and Efficiency (pg. 242)
13.2. Competing Algorithms (pg. 245)
13.2.1. The Role of Each Side of the Market (pg. 245)
13.2.2. The Deferred Acceptance Algorithm (pg. 246)
13.2.3. The Immediate Acceptance Algorithm (pg. 248)
13.2.4. Top Trading Cycles (pg. 250)
13.3. The Problem with the Immediate Acceptance Algorithm (pg. 256)
13.4. Applications (pg. 257)
13.4.1. The Boston School Match (pg. 257)
13.4.2. The New York City School Match (pg. 259)
14.1. Weak Priorities (pg. 263)
14.1.1. The Problem (pg. 263)
14.1.2. Efficiency Loss (pg. 264)
14.1.3. The Student-Optimal Assignment with Weak Priorities (pg. 265)
14.1.4. Restoring Efficiency (pg. 266)
14.1.5. How to Break Ties If You Must (pg. 272)
14.2. Constrained Choice (pg. 276)
14.2.1. Issues (pg. 277)
14.2.2. From Very Manipulable to Less Manipulable (pg. 279)
15.1. Preliminaries (pg. 283)
15.2. Bidding for Courses (pg. 284)
15.2.1. The Bidding and Allocation Process (pg. 285)
15.2.2. Issues: Nonmarket Prices and Inefficiency (pg. 286)
15.2.3. Deferred Acceptance with Bids (pg. 288)
15.3. The Harvard Business School Method (pg. 290)
15.3.1. The Harvard Draft Mechanism (pg. 290)
15.3.2. Strategic Behavior (pg. 291)
15.3.3. Welfare (pg. 293)
15.4. The Wharton Method (pg. 295)
15.4.1. Approximate Competitive Equilibrium from Equal Incomes (pg. 296)
15.4.2. The Wharton Experiment (pg. 298)
16.1. Background (pg. 303)
16.2. Trading Kidneys (pg. 305)
16.2.1. Trades versus Waiting List (pg. 306)
16.2.2. The Kidney Exchange Algorithm (pg. 306)
16.2.3. Chain Selection Rules (pg. 309)
16.2.4. Efficiency and Incentives (pg. 311)
16.3. On the Number of Exchanges (pg. 313)
A.1. Strategic Form Games (pg. 317)
A.1.1. Definition (pg. 317)
A.1.2. Pure and Mixed Strategies (pg. 318)
A.2. Extensive Form Games (pg. 319)
A.2.1. Definition (pg. 320)
A.2.2. Strategies (pg. 321)
A.2.3. Imperfect Information (pg. 322)
A.3. Solving Games (pg. 324)
A.3.1. Dominated and Dominant Strategies (pg. 324)
A.3.2. Elimination of Dominated Strategies (pg. 326)
A.3.3. Nash Equilibrium (pg. 328)
A.4. Bayesian Games: Games with Incomplete Information (pg. 330)
A.4.1. Introductory Example (pg. 330)
A.4.2. Definition (pg. 331)
B.1. Preliminaries (pg. 335)
B.2. The Model (pg. 337)
B.2.1. Mechanism (pg. 337)
B.2.2. Implementing Social Choice Functions (pg. 339)
B.2.3. Direct versus Indirect Mechanism (pg. 340)
B.3. Dominant Strategy Implementation (pg. 341)
B.3.1. The Revelation Principle (pg. 341)
B.3.2. The Gibbard-Satterthwaite Theorem (pg. 342)
B.3.3. The Vickrey-Clarke-Groves Mechanism (pg. 343)
B.4. Bayesian Mechanism Design (pg. 344)
B.4.1. Bayesian Incentive Compatibility (pg. 344)
B.4.2. Trading: The Myerson-Satterthwaite Theorem (pg. 345)
C.1. Expected Highest Valuation (pg. 349)
C.1.1. Obtaining the Cumulative Density Function (pg. 350)
C.1.2. Obtaining the Probability Density Function (pg. 350)
C.1.3. Calculate the Expectation (pg. 350)
C.2. Expected Second-Highest Valuation (pg. 351)
C.3. Conditional Expectation of the Highest Valuation (pg. 352)
C.4. Changing the Upper and Lower Bounds (pg. 353)
Chapter 1 (pg. 355)
Chapter 2 (pg. 355)
Chapter 3 (pg. 356)
Chapter 4 (pg. 357)
Chapter 5 (pg. 357)
Chapter 6 (pg. 357)
Chapter 7 (pg. 358)
Chapter 8 (pg. 358)
Chapter 9 (pg. 358)
Chapter 10 (pg. 359)
Chapter 11 (pg. 360)
Chapter 12 (pg. 360)
Chapter 13 (pg. 360)
Chapter 14 (pg. 361)
Chapter 15 (pg. 361)
Chapter 16 (pg. 362)
Appendix A (pg. 362)
Appendix B (pg. 362)

Guillaume Haeringer

Guillaume Haeringer is Professor of Economics at the Zicklin School of Business at Baruch College. 


Instructors Only
You must have an instructor account and submit a request to access instructor materials for this book.
eTextbook
Go paperless today! Available online anytime, nothing to download or install.

Features

  • Highlighting
  • Bookmarking
  • Note-taking