Design and analysis of multi-hospital kidney exchange mechanisms using random graphs

• 成果类型: Article
• 署名作者: Toulis, Panos; Parkes, David C.
• 署名单位: Harvard University; Harvard University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2015.01.001
• 发表日期: 2015
• 页码: 360-382
• 关键词: Kidney exchange; Random graphs; mechanism design; Maximum matching; integer programming; Incentive compatible design

摘要

Kidney exchanges enable transplants when a pair of a patient and an incompatible donor is matched with other similar pairs. In multi-hospital kidney exchanges pairs are pooled from multiple hospitals, and each hospital is able to decide which pairs to report and which to hide and match locally. Modeling the problem as a maximum matching on a random graph, we first establish that the expected benefit from pooling scales as the square-root of the number of pairs in each hospital. We design the xCM mechanism, which achieves efficiency and incentivizes hospitals of moderate-to-large size to fully report their pairs. Reciprocal pairs are crucial in the design, with the probabilistic uniform rule used to ensure incentive alignment. By grouping certain pair types into so-called virtual-reciprocal pairs, xCM extends to handle 3-cycles. We validate the performance of xCM in simulation, demonstrating its efficiency and incentive advantages over the Bonus mechanism (Ashlagi and Roth, 2014). (C) 2015 Elsevier Inc. All rights reserved.