The Power of Small Structures in Kidney Exchange

April 24, 2013

**Kidney exchange:**

Several thousand people in the US are affected by kidney failure each year. Kidney transplants are a solution for this. However, what compounds the problem further is that, many times, though there are friends of these patients who are willing to donate them a kidney, they are unable to since they are biologically incompatible with the patient. Kidney exchange centers try to match up such incompatible pairs, such that the donor of the first pair is compatible with the patient of the second and vice versa. This allows the kidneys to be swapped between the two pairs.

Determining compatibility, however, is not an easy task. It requires multiple tests, some of which are expensive. This expense makes it infeasible to first determine compatibility or lack thereof between all pairs, and then match them. Ideally, we would like to conduct only a few tests and be able to match up all the incompatible pairs with one another. How do we choose which pairs to test?

**Theoretical problem statement:**

Kidney exchange motivates the following theoretical problem: Given an underlying graph G(V,E) with each edge in E existing with probability p, we need to choose a subgraph G(V,E') to test (E' \subset E), such that |E'| is small and the expected size of the maximum matching in G(V,E') is maximized. We measure the 'expected size' of matching in G(V,E') since, as mentioned, each edge in E' only exists with probability p. We will deal with a variant of this problem in this talk.

To relate with the kidney exchange problem, each node in G represents an incompatible pair of patient and donor and each edge in set E is a potential compatibility test. The test succeeds (i.e., edge exists) with a known probability p. We need to decide which edges E' to test to maximize the expected size of matching in the graph.

*This is joint work with Avrim Blum, Anupam Gupta and Ariel Procaccia, and shall appear at EC 2013.*