Kidney exchange in dynamic sparse heterogenous pools. arXiv preprint arXiv:1301.3509

Kidney exchange pools are currently thin and sparse consisting of many highly sensitized patients. One way to increase matching opportunities for patients is by waiting for many incompatible pairs to join the pool. We analyze an algorithm that periodically finds allocations and study how the period length, as well as the technology, affects the number of matched patients. We find that if only 2-way cycles are conducted, matching online (as a new pair arrives) results in almost the same number of matches as the algorithm finds when the period length is “short”. However, if 3-way cycles are also allowed, we find regimes in which waiting for a short period considerably increases the number of matches that the algorithm finds. Finally, we show that when matching online, by allowing just a single non-simultaneous chain the number of matches will increase significantly. Our theoretical findings are supported by data-driven computational experiments.