Kidneys and Trading Cycles
https://www.prnewswire.com/news-releases/israel-uae-residents-come-together-for-historic-kidney-transplants-301391996.html
The news article explains the story behind a kidney exchange that involved donors and patients from different countries and religious backgrounds. Kidney disease is a significant medical problem worldwide, and kidney transplants are one way to address end stage kidney disease where all else fails. However, compatibility issues make this difficult to carry out in practice, as it is often the case that the people willing to donate kidneys to loved ones have kidneys which are incompatible with the patient, and the primary reason tends to be blood type differences. As such, the issue is sometimes not about a lack of supply, but the inability to get kidneys of one compatibility group to patients of the same group. This was the case in the article, where two women with daughters who did not match, and one woman whose husband did not match, managed to exchange kidneys in a “trading cycle” of sorts, which gave rise to a perfect matching.
This problem is a natural application of a matching problem. While such a problem is easy on paper in the homeworks we have been assigned (we were simply given a handful of donors and an equal number of patients, with links between compatible pairs), that abstracts much of the human aspect out of the problem. In reality, people would only be aware of their own initial partner to whom they wish to donate, and if the matching produced was not a perfect matching (as was the case in our homework, someone was left without a donor because a constricted set was present), then it is highly likely that the patient without a donor would not want to participate in the matching, which in turn, will cause their donor partner to drop out, which can cause the maximal matching produced to unravel. Also, because donors might wish to drop out of the arrangement as soon as their partner patient receives a kidney, all transplants must occur nearly simultaneously to prevent such complications. This means that a large number of skilled doctors will be needed simultaneously to facilitate these matchings. As such, arrangements such as the one featured in the news article are all the more hard to come by.
In practice, it is possible to address the first issue partially with a national waitlist for kidney donations from deceased individuals. If a maximal matching leaves a patient without a donor but their original partner can donate their kidney to someone in the maximal matching, then we can assign them to the waitlist, where they are guaranteed a kidney at a later date. This would be represented in our matching problems by having an additional node belonging to neither of the 2 classical groups of nodes (patients and donors). After obtaining a maximal matching with the patients and donors available, all remaining donors donate to people on the waitlist, and all patients remaining are sent to the waitlist, represented by these individuals having an edge from their node to the waitlist. In this way, the matching becomes “perfect”, though it does not conform to the classical rule of having 1-1 matchings, since the waitlist has (theoretically) infinite matching capacity. Of course, this does abstract away some other issues from the problem, as is always the case when trying to simplify such networks to mathematical problems. One such issue is that O donors will almost never end up in the waitlist because they can donate to any other blood group (after factoring in Rhesus positivity), and AB blood group donors will likely be overabundant in the waitlist for the converse reason.
One interesting observation for this matching problem is that if we simplify the problem of compatibility down to blood type, then it is likely that such cycles of donors and patients will seldom exceed a certain length, because there are 4 main bloodtype groups, and Rhesus positive/negative variations. One can imagine that if a donor-patient trading cycle contains some integer multiple of every blood type in it, then it is likely that there is some repeating pattern in the cycle. A rigorous proof of this is shown in a paper by Roth, Sönmez, and Ünver in 2015, which showed that the maximum cycle length in this problem is equal to the number of blood types. This puts an upper bound on the number of doctors required at any one time for such arrangements and ensures such arrangements are feasible most of the time when it is possible.