  Relatives and friends of an end-stage renal disease patient who offer to
donate a kidney are often found to be incompatible with their intended
recipients. Kidney paired donation matches one patient and his incompatible
donor with another patient and donor in the same situation for an organ
exchange. Let patient- donor pairs be the vertices of an undirected graph G,
with an edge connecting any two reciprocally compatible vertices. A matching in
G is a feasible set of paired donations. We describe various optimization
problems on kidney paired donation graphs G and the merits of each in clinical
transplantation. Because some matches are geographically undesirable, and the
expected lifespan of a transplanted kidney depends on the immunologic
concordance of donor and recipient, we weight the edges of G and seek a maximum
edge-weight matching. Unfortunately, such matchings might not have the maximum
cardinality; there is a risk of an unpredictable trade-off between the quality
and quantity of paired donations. We propose an edge-weighting of G which
guarantees that every matching with maximum weight also has maximum
cardinality, and also maximizes the number of transplants for an exceptional
subset of recipients, while reducing travel and favoring immunologic
concordance.
