Saving Lives with Matching Algorithms
So far in class we’ve been introduced to basic matching, where preferences over objects are not considered. Needless to say, there are many possible factors to take into consideration as we learn about larger applications of matching algorithms. But something we have been exposed to thus far is eligibility. For example, an algorithm that matches TA’s to potential office hour slots depends on the eligibility (or better yet, availability) of their schedule to permit a particular time slot. The notion of eligibility here is not complicated, since there can be only one reason for a TA to be ineligible (that they are busy), but in other contexts it can make finding a perfect match a much more nuanced process.
Imagine that instead of matching people to objects, you were matching people to other people. You would then have to make assignments based on the compatibility of two people, which makes finding the matches significantly more difficult. The matching problem discussed below is a perfect example of this complication:
For The Alliance for Paired Kidney Donation, finding a donor for a patient in need of a transplant was complicated greatly by the fact that they must have compatible blood types; a donor with blood type A is not helpful to someone with blood type B. This means that it is not enough to find a patient and a donor; they would need to find the right patient for the right donor. Alvin Roth, recipient of the Nobel Prize in Economic Sciences (2012) and the creator of a matching algorithm that did just this, used this notion of compatibility to match patients with donors in an efficient way. He assembled a set of patient-donor pairs and chained them together such that if the patient-donor pairs (x , y) and (a, b) were not eligible within those pairs, but y was compatible with a and b with x, then patient x could get donor b‘s kidney, and patient a could get y‘s.
This application is helpful to think about not only because it saved the lives of countless patients, but also because it expands the notion of eligibility in matching algorithms beyond the “yes or no” quality that we take into consideration for our assignments.
Resources: https://paireddonation.org/about-us/algorithm/