House allocation
A dozen years after the Gale and Shapley paper the first issue of the Journal of Mathematical Economics appeared. Lloyd Shapley had more to say about matching arrangements, and in the inaugural issue of the journal he published a paper coauthored with Herbert Scarf about allocating houses.
Matching house buyers with houses is a bit like matching men and women for marriage or students with colleges. The difference is that houses don’t have preference rankings of their potential buyers; only one side of the house allocation problem has rankings.
Also worth noting is that we are not talking about a house market. Shapley and Scarf did not introduce money into their problem. They wanted to find out what a simple exchange could accomplish, without any payments.
In the house allocation problem we have a number of people, each of whom owns a house. In this situation, a matching is any one-to-one assignment of people to houses. A proposed matching is in the core if there is no group of people that can improve their situation by ignoring the matching and exchanging their own houses. (This is an application of the more general concept of the core in cooperative game theory.)
Shapley and Scarf introduced an algorithm that produced a house allocation (matching) that always belongs to the core. This is the top trading cycles algorithm; Shapley and Scarf attributed it to David Gale. A short presentation by Tayfun Sönmez is here. Here comes a simplified presentation, shorn of mathematical notation.
The top trading cycles algorithm
Step 1. Each person points to the owner of her/his favorite house. Eventually, since there is a finite number of people, this reaches the person who started pointing. So there exists at least one cycle. Take a cycle. Each person in the cycle is assigned the house of the person that s/he pointed to and is removed from the allocation problem. If there is no remaining agent, the algorithm terminates. If there is at least one remaining agent, then the algorithm goes to the next step.
Step t (for t > 1). Each remaining person points to the owner of her/his favorite house among the remaining houses. Again, there must exist at least one cycle. Take a cycle. Each person in the cycle is assigned the house of the person that s/he pointed to and is removed from the allocation problem. If there is no remaining agent, the algorithm terminates. If there is at least one remaining agent, then the algorithm goes to the next step.
That’s it. Clearly, with a finite number of people/houses, this algorithm terminates in finite time. Shapley and Scarf showed that:
The top trading cycles algorithm always terminates with a matching that belongs to the core of the house allocation problem.
This is good news. But there is more good news. Other researchers have proven the following result, which shows that trying to manipulate the algorithm to “game the system” will not work. For this, we need one more concept from game theory, strategy proofness.
Direct matching mechanisms and strategy proofness
A direct matching mechanism is a precisely specified procedure that selects one matching for each allocation problem.
Since Alvin Roth and Andrew Postlewaite have shown that the core of the house allocation problem has exactly one allocation, operating the top trading cycle is a direct matching mechanism.
A direct matching mechanism is strategy proof if no participant can ever do better by pretending to have a preference ranking that differs from her/his true one. Roth showed:
The top trading cycles mechanism is strategy proof.
Kidney exchanges
Finally! We are ready to talk about saving lives. Patients with certain end-stage renal (kidney) diseases often face a life of constant dialysis and can benefit tremendously by a kidney transplant; many of them die waiting for a transplant because there is a severe shortage of kidneys for transplantation. Since humans have two kidneys each and can live a normal life with only one healthy kidney, kidneys for transplantation can come from living donors as well as from deceased donors. Furthermore, a recipient of a kidney from a live donor has a better chance of doing well than a recipient of a cadaverous kidney. So donors could step up and save many lives without compromising their own health. Yet, the shortage of kidneys exists.
An economist can be expected to jump in at this point and remark that if only we allowed patients to pay for kidneys, the quantity of kidneys supplied would increase and more renal disease patients would be treated successfully. But societal norms consider paying money for human organs a repugnant transaction.
If at this point you see why I have been telling you in this post and its prequel about various matching “markets” that operate without money, you are correct in surmising that the study of matching markets gave some economists the tools to improve the situation of renal disease patients without running up against the repugnance of society to having an actual market for kidneys. There is a reason this section’s heading is kidney exchanges and not kidney markets.
Why is there any room for the knowledge of matching algorithms to help? Can’t a patient’s own family members be the source of kidneys for transplantation? Very often, a willing and able relative is in fact present, but transplants require the donor and recipient to be biologically compatible.
But suppose you have donor A and patient B, as well as donor C and patient D. A is happy to donate a kidney to B but they are biologically incompatible. The same holds for C and D. But what if A can donate to D and C to B? It turns out society does not view such “donor swaps” as repugnant transactions.
Now you can clearly see the relevance of the matching theory. Alvin Roth (Nobel prize in Economics 2012 in part due to his work in this area), Tayfun Sönmez , and M. Utku Ünver published a paper in 2004 that changed the situation drastically by coming up with a variation of the top trading cycles procedure (we’ll just call it TTCC here; see the paper linked just now for details) and showing that if it were implemented, we could expect a large increase in kidney donations from live donors. With sufficient planning and infrastructure, we could have larger chains of donors and kidneys matched at once (for example, from the donor-patient pairs A-B, C-D, E-F, perhaps biological compatibility constraints allow the donations A-D, C-F, and E-B).
Taking these possibilities into account, the paper offered two important theorems that show that the TTCC algorithm leads to efficient allocations of kidneys (music to the ears of economists far and wide) and also is strategy proof. The paper also offered simulations to show how the TTCC could be expected to behave in realistic situations, using medical information. The simulations showed that large gains could be expected for renal disease patients.
As a result of this research, centralized registries for kidney donors and patients were created in various countries and a large number of patients were successfully treated by live donor kidney transplants. An abstruse-looking subfield of the mathematical subject of game theory has directly led to the saving of hundreds of lives.
Last June I attended a small conference to celebrate the 65th birthday of my doctoral dissertation advisor, William Thomson. Tayfun Sönmez, whose dissertation advisor was also William Thomson (some years after me), gave the last talk and dazzled us with information about partial liver and partial lung transplants that are possible with live donors (I had no idea), along with statistics about the many lives the ideas that came out of the Roth, Sönmez, and Ünver paper, and the authors’ tireless advocacy with doctors and governments around the world, have saved.
To this I can only say Bravo.
ADDED 2015-03-01: Here is an excellent mini-course on this topic by Tayfun Sönmez.
The curious incident of DD on the Web 