Algorithmic Game Theory (Lecture 10: Kidney Exchange and Stable Matching)

This lecture concludes with a case study on kidney exchange, a mechanism design application without monetary transfers. Incompatible patient-donor pairs are matched via algorithms (initially top trading cycles, later maximum cardinality matchings) to maximize successful transplants. Challenges include simultaneous surgeries and hospital incentives for truthful reporting. The lecture also covers stable matching, the Gale-Shapley algorithm, and its strategic properties. This segment introduces the critical issue of kidney failure and the concept of living donors, highlighting the complexities of kidney transplants due to compatibility issues like blood and tissue types. It sets the stage for exploring solutions to overcome these compatibility barriers. This segment introduces the innovative concept of kidney exchange, where incompatible patient-donor pairs swap donors to enable successful transplants. It explains how this seemingly simple idea can save lives by creating a system of reciprocal organ donation. This segment discusses the development of nationwide kidney exchange programs, emphasizing the creation of a "thick market" to maximize matches and save lives. It highlights the success of these programs and the significant number of transplants performed due to algorithmic matching. This segment delves into the practical limitations of long cycles in kidney exchange, focusing on the logistical and ethical issues of simultaneous surgeries. It explains why shorter cycles are preferred to minimize risks and ensure fairness. This segment discusses a crucial shift in modeling patient preferences, moving from a total ordering to a binary preference model. This reflects a more realistic representation of how patients and doctors assess kidney compatibility, leading to more efficient matching algorithms. This segment defines optimal solutions in kidney exchange as maximum cardinality matching, focusing on pairwise exchanges due to logistical simplicity and the minimal added benefit of longer exchanges. It highlights the practical use of two- and three-way exchanges in current algorithms, contrasting with the theoretical model's limitation to pairwise exchanges for simplification. This segment addresses the scenario of a patient having multiple incompatible donors. It explains the mechanism used to handle this situation, emphasizing the incentive compatibility of reporting all compatible donors to maximize the chances of a successful transplant. The discussion clarifies that only one donor will donate, even if multiple are compatible. This segment delves into the challenges of designing a mechanism that is both incentive compatible (DSIC) and maximizes surplus (maximum matching). It explains the difficulty of achieving both goals simultaneously, especially in the absence of monetary incentives, and sets the stage for the introduction of a novel mechanism. This segment presents an impossibility result demonstrating that it's impossible to simultaneously maximize the number of successful kidney exchanges (surplus maximization) while ensuring hospitals always have a dominant strategy to report all information truthfully (dominant strategy incentive compatibility). The discussion explores the real-world implications of this result, acknowledging the trade-off between surplus maximization and incentive compatibility and the need to find a balance between these two competing goals. This segment introduces a mechanism for kidney exchange that aims to achieve both DSIC and surplus maximization. It describes the process of constructing an undirected graph based on reported compatibilities and finding a maximum cardinality matching. The discussion highlights the need for a tie-breaking rule when multiple maximum matchings exist. This segment presents a deterministic DSIC mechanism that uses a priority system to resolve ties among maximum matchings. It explains how the priority system works, relating it to existing hospital practices, and outlines the iterative process of committing to match nodes based on their priority. The segment concludes by mentioning the proof of DSIC as an exercise for the viewer. This segment uses a clear example with two hospitals (H1 and H2) to illustrate the challenges of incentivizing hospitals to report all patient-donor pairs to a kidney exchange, even those they could match internally. It highlights the trade-off between maximizing the number of successful transplants and ensuring hospitals truthfully report all potential matches. The example demonstrates how internal matching can lead to fewer overall matches if not all pairs are reported. This segment addresses the issue of non-uniqueness in maximum matchings, differentiating between cases where different matchings match the same set of nodes and cases where different matchings leave different nodes unmatched. It emphasizes the need for a consistent tie-breaking rule to ensure fairness and incentive compatibility. This segment explores the uniqueness and incentive compatibility properties of the Gale-Shapley algorithm. It proves that the algorithm always produces the same stable matching, regardless of the order of proposals, and that this matching is optimal for the proposing side (men in the male-proposing version). It also discusses the algorithm's strategy-proofness for the proposing side and lack thereof for the other side, highlighting the strategic implications for participants. This segment provides a detailed proof of the correctness of the Gale-Shapley algorithm. It demonstrates that the algorithm always terminates with a perfect matching and that this matching is stable. The proof addresses the two key properties: the perfect matching property and the stability property, showing why the algorithm's output satisfies both. This segment introduces the stable matching problem, defining the key components: two sets of nodes (e.g., men and women), ranked preference lists for each node, and the concept of a stable matching. It clearly explains the definition of stability, emphasizing that a stable matching is a perfect matching where no unmatched pair would mutually prefer to be together over their current matches. This segment introduces the Gale-Shapley algorithm, a constructive proof demonstrating the existence of stable matchings. It outlines the algorithm's steps, showing how it iteratively proposes and accepts matches based on preference lists, and states the algorithm's key properties: termination in polynomial time, resulting in a perfect and stable matching.