PRIMAL-DUAL BASED WEIGHTS AND OTHER KIDNEY EXCHANGE MECHANISMS

Abstract

Kidney exchanges are a recent innovation in mechanisms for kidney transplants. They match patients who have a willing but incompatible donor to other patients and donors in similar circumstances by first pooling the patients and donors and then matching compatible patients and donors. In this paper we implement and analyze a variety of algorithms used for this matching process, using datasets from current and past patients and donors. We analyze the impact on utility of several variations on the matching process, including allowing transplants to occur asynchronously, allowing patients to bring multiple donors, and allowing compatible donors to join the exchange. We also propose a primal-dual method of calculating optimum weights for the matching graph based on the dual values of previous matchings with the same distribution of blood types and PRA levels. Additionally, we experimentally show that this method produces optimal weights for matching.