Skip to content
Kidney paired donation optimization code
Java
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.settings
lib
src/edu/cmu/cs/dickerson/kpd
.classpath
.gitignore
.project
LICENSE
README.md

README.md

Kidney Exchange

What is kidney exchange?

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.

What is this code?

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!

External Dependencies

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.

Related Research

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.

You can’t perform that action at this time.