Mix and match: A strategyproof mechanism for multi-hospital kidney exchange

• 成果类型: Article
• 署名作者: Ashlagi, Itai; Fischer, Felix; Kash, Ian A.; Procaccia, Ariel D.
• 署名单位: Massachusetts Institute of Technology (MIT); University of Cambridge; Microsoft; Microsoft United Kingdom; Carnegie Mellon University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2013.05.008
• 发表日期: 2015
• 页码: 284-296
• 关键词: Approximate mechanisms without money; kidney exchange

摘要

As kidney exchange programs are growing, manipulation by hospitals becomes more of an issue. Assuming that hospitals wish to maximize the number of their own patients who receive a kidney, they may have an incentive to withhold some of their incompatible donor-patient pairs and match them internally, thus harming social welfare. We study mechanisms for two-way exchanges that are strategyproof, i.e., make it a dominant strategy for hospitals to report all their incompatible pairs. We establish lower bounds on the welfare loss of strategyproof mechanisms, both deterministic and randomized, and propose a randomized mechanism that guarantees at least half of the maximum social welfare in the worst case. Simulations using realistic distributions for blood types and other parameters suggest that in practice our mechanism performs much closer to optimal. (C) 2013 Elsevier Inc. All rights reserved.