Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- 1 Introduction and Examples
- 2 Mechanism Design Basics
- 3 Myerson's Lemma
- 4 Algorithmic Mechanism Design
- 5 Revenue-Maximizing Auctions
- 6 Simple Near-Optimal Auctions
- 7 Multi-Parameter Mechanism Design
- 8 Spectrum Auctions 97
- 9 Mechanism Design with Payment Constraints 113
- 10 Kidney Exchange and Stable Matching
- 11 Selfish Routing and the Price of Anarchy
- 12 Over-Provisioning and Atomic Selfish Routing
- 13 Equilibria: Definitions, Examples, and Existence
- 14 Robust Price-of-Anarchy Bounds in Smooth Games
- 15 Best-Case and Strong Nash Equilibria
- 16 Best-Response Dynamics
- 17 No-Regret Dynamics
- 18 Swap Regret and the Minimax Theorem
- 19 Pure Nash Equilibria and PLS-Completeness
- 20 Mixed Nash Equilibria and PPAD-Completeness
- The Top 10 List
- Hints to Selected Exercises and Problems
- Bibliography
- Index
10 - Kidney Exchange and Stable Matching
Published online by Cambridge University Press: 05 August 2016
- Frontmatter
- Dedication
- Contents
- Preface
- 1 Introduction and Examples
- 2 Mechanism Design Basics
- 3 Myerson's Lemma
- 4 Algorithmic Mechanism Design
- 5 Revenue-Maximizing Auctions
- 6 Simple Near-Optimal Auctions
- 7 Multi-Parameter Mechanism Design
- 8 Spectrum Auctions 97
- 9 Mechanism Design with Payment Constraints 113
- 10 Kidney Exchange and Stable Matching
- 11 Selfish Routing and the Price of Anarchy
- 12 Over-Provisioning and Atomic Selfish Routing
- 13 Equilibria: Definitions, Examples, and Existence
- 14 Robust Price-of-Anarchy Bounds in Smooth Games
- 15 Best-Case and Strong Nash Equilibria
- 16 Best-Response Dynamics
- 17 No-Regret Dynamics
- 18 Swap Regret and the Minimax Theorem
- 19 Pure Nash Equilibria and PLS-Completeness
- 20 Mixed Nash Equilibria and PPAD-Completeness
- The Top 10 List
- Hints to Selected Exercises and Problems
- Bibliography
- Index
Summary
This lecture is our last on mechanism design, and it covers some of the greatest hits of mechanism design without money. Kidney exchanges, the case study covered in Section 10.1, have been deeply influenced by ideas from mechanism design over the past ten years. These exchanges enable thousands of successful kidney transplants every year. Stable matching and the remarkable deferred acceptance algorithm (Section 10.2) form the basis of modern algorithms for many assignment problems, including medical residents to hospitals and students to elementary schools. This algorithm also enjoys some beautiful mathematical properties and incentive guarantees (Section 10.3).
Case Study: Kidney Exchange
Background
Many people suffer from kidney failure and need a kidney transplant. In the United States, more than 100,000 people are on the waiting list for such transplants. An old idea, used also for other organs, is deceased donors; when someone dies and is a registered organ donor, their organs can be transplanted into others. One special feature of kidneys is that a healthy person has two of them and can survive just fine with only one of them. This creates the possibility of living organ donors, such as a family member of the patient in need.
Unfortunately, having a living kidney donor is not always enough; sometimes a patient-donor pair is incompatible, meaning that the donor's kidney is unlikely to function well in the patient. Blood and tissue types are the primary culprits for incompatibilities. For example, a patient with O blood type can only receive a kidney from a donor with the same blood type, and similarly an AB donor can only donate to an AB patient.
Suppose patient P1 is incompatible with her donor D1 because they have blood types A and B, respectively. Suppose P2 and D2 are in the opposite boat, with blood types B and A, respectively (Figure 10.1). Even though (P1, D1) and (P2, D2) have probably never met, exchanging donors seems like a pretty good idea, with P1 receiving her kidney from D2 and P2 from D1. This is called a kidney exchange.
- Type
- Chapter
- Information
- Twenty Lectures on Algorithmic Game Theory , pp. 128 - 144Publisher: Cambridge University PressPrint publication year: 2016