Kidney failure is a life-threatening health issue that affects hundreds of thousands of people worldwide. In the US alone, the waitlist for a kidney transplant has over 100,000 patients. This list is growing: demand far outstrips supply.
A recent innovation, kidney exchange, allows patients to bring an (incompatible) donor to a large pool where they can swap donors with other patients. As of 2012–2013, roughly 10% of US kidney transplants occurred through a variety of kidney exchanges. Outside of the US, many countries (the UK, the Netherlands, Portugal, Israel, ...) are fielding exchanges.
This codebase includes: structural elements of kidney exchange like "pools", "hospitals", and "pairs", a couple of kidney exchange graph generators, a couple of kidney exchange solvers (max weight, failure-aware, fairness-aware, individually rational), and a dynamic kidney exchange simulator.
If you use this codebase, please cite one of our recent papers like:
John P. Dickerson, Ariel D. Procaccia, and Tuomas Sandholm. 2014. Price of Fairness in Kidney Exchange. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems (AAMAS-2014). Paris, France (pp. 1013–1020).
NOTE: This is not the code used in the UNOS Kidney Paired Donation Pilot Program (KPDPP). The solvers here are meant to be accessible research code for the community and do not use branch-and-price, hopefully resulting in greater ease of use (at the cost of scalability). Forks and pull requests welcome!
To use any of the solvers that inherit from CPLEXSolver, you will need to add cplex.jar to lib/. This will allow compilation; to run, you'll also need a VM argument like
-Djava.library.path=/path/to/CPLEX_Studio/cplex/bin/your-architecture/
IBM offers a free academic license for CPLEX as well as a 90-day free trial available on their website.
FutureMatch: Combining Human Value Judgments and Machine Learning to Match in Dynamic Environments. John P. Dickerson and Tuomas Sandholm. Working Paper.
Multi-Organ Exchange: The Whole is Greater than the Sum of its Parts. John P. Dickerson and Tuomas Sandholm. AAAI-2014. Link
The Price of Fairness in Kidney Exchange. John P. Dickerson, Ariel D. Procaccia, Tuomas Sandholm. AAMAS-2014. Link
The Empirical Price of Fairness in Failure-Aware Kidney Exchange. John P. Dickerson, Ariel D. Procaccia, Tuomas Sandholm. AAMAS-2014 Workshop on Healthcare and Algorithmic Game Theory. Link
Failure-Aware Kidney Exchange. John P. Dickerson, Ariel D. Procaccia, Tuomas Sandholm. EC-2013. Link
Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. John P. Dickerson, Ariel D. Procaccia, Tuomas Sandholm. AAAI-2012. Link
Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. John P. Dickerson, Ariel D. Procaccia, Tuomas Sandholm. AAMAS-2012. Link
Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. David J. Abraham, Avrim Blum, Tuomas Sandholm. EC-2007. Link
Increasing the Opportunity of Live Kidney Donation by Matching for Two and Three Way Exchanges. S. L. Saidman, Alvin Roth, Tayfun Sönmez, Utku Ünver, Frank Delmonico. Transplantation, 2006. Link
These are admittedly me-centric references! Make sure to click around: Ross Anderson, Itai Ashlagi, Avrim Blum, John Dickerson, David Gamarnik, David Parkes, Ariel Procaccia, Al Roth, Tuomas Sandholm, Ankit Sharma, Tayfun Sönmez, Pingzhong Tang, Utku Ünver.
If you are interested in other social choice problems, make sure to check out PrefLib, a reference library of preference data assembled by Nicolas Mattei and Toby Walsh.