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.

What? Mathematical Economics can save lives, that’s what

But it will take us more than one post to get to it; meanwhile, there is fun to be had learning about stable matches, so please read on

As I am preparing upcoming graduate lectures on market design, I thought I would build a little conceptual scaffolding here for everyone (lots of math is behind what I will discuss, but fear not, I will spare you the math, except for some very fun bits).

The story is about saving lives, but the field of economics which achieves this remarkable feat is called market design, and is an outgrowth of game theory. It has also achieved other worthy aims, such as matching residents to hospitals and students to public school in ways that were better than they used to be.

What is there to design in a market, you ask? All sorts of details. Elementary economics (admit it, you have heard of supply and demand, and have probably even seen the typical graph where supply and demand intersect at the market equilibrium) sweeps all the details under the carpet. One of the assumptions that helps in doing so is that the commodity traded in the market is homogeneous and divisible. This allows the smoothly drawn supply and demand curves of all Econ 101 courses ever to represent something that could correspond to a real market.

But what if we are talking about indivisible things that are to be traded? And what if “traded” is the wrong word? For instance, what if we are trying to match men and women for marriage in the traditional sense of one man and one woman only? What if we are trying to match medical interns to hospitals for training, or employees to employers?

Enter clever mathematicians, starting with David Gale and Lloyd Shapley (Shapley shared the 2012 Nobel prize in economics with Alvin Roth for this and other contributions). In a short but meaty paper published in 1962, they looked at the marriage problem, in which there are men and women to be matched, one-to-one. After they found an algorithm that matches men and women well, in a way to be made clear soon, they moved on to show that this algorithm would also work to match students with colleges.

In the marriage problem, there are equal numbers of men and women. Each woman has a preference ordering over all the men and each man over all the women. A match in this case is a set of marriages. A set of marriages is unstable if under it there is a woman and a man who are not married to each other but prefer each other to the spouses that this set of marriages has assigned them. A set of marriages is stable if this situation does not arise. The big result of Gale and Shapley is:

No matter how large is the common number of men and women and what their rankings of each other are, there always exists a stable set of marriages.

Better yet, they proved this by showing an algorithm that always succeeds in finding a stable match. This has come to be known as the deferred acceptance algorithm and it has spurred much of the theoretical development in this area. It is also fun to explain and requires no advanced math whatsoever, so for better or worse here it goes.

Deferred Acceptance Algorithm (with men proposing)

Start by having each man propose to his favorite woman. Each woman who received more than one proposal rejects all but the one that is from her favorite man among those who proposed to her. But she does not accept his proposal yet; she holds on to it in case a better proposal comes along.

In the second stage, the rejected men now propose to their second-ranked women. Once again, each woman who receives a proposal chooses her favorite among the new proposers and the man whose proposal she is holding on from the previous stage, if any. Again, she rejects all the others and keeps the favorite on hold.

The algorithm proceeds with identical stages until it terminates when there are no more proposals made. Then each woman is matched to the man whose proposal she is holding at that time. So the algorithm ends having matched all men to all women. It’s easy to see why it must terminate: a man who has been rejected by a woman is not allowed to propose to her again. Since there is a finite number of women, eventually this process must end. The moment the last woman has received her proposal, the process ends and each woman is married to the man whose proposal she is holding at this time.

Gale and Shapley proved that the set of marriages (simply called matching from now on) produced by the deferred acceptance algorithm is stable.

What if women proposed first?

We can reverse the roles of men and women and have women start every stage of the deferred acceptance algorithm by proposing to their favorite men who have not yet rejected them. Naturally, this also leads to a stable matching, as there was nothing in the logic of the situation that depends on which side gets to make the proposals.

So for the existence of stable sets of marriages it does not matter which side starts proposing. But it matters for the men and the women! We can make this crystal clear by a little terminology and a theorem.

Terminology: let us call the M-optimal matching the one where no man prefers another stable matching to it; and similarly for the W-optimal matching.

When the deferred acceptance algorithm starts with men proposing, it terminates with an M-optimal stable matching and when it starts with women proposing, it terminates with a W-optimal matching.

So the interests of men and women are precisely opposed to each other in a specific sense.

Gale and Shapley also adapt the procedure to the case of college admissions. Here, of course, the two sides are not equal in number. However, if we assume that each college has a quota of students that it can accept, due to its capacity constraint, and we give the first move to the applicants, a slight modification of the deferred acceptance algorithms works just fine in producing a stable assignment of students to colleges. (The only thing needing to be modified is the “holding” list, which now has a number of slots, instead of just one as in the marriage case.) Also:

Every applicant is at least as well off under the assignment given by the deferred acceptance algorithm as s/he would be under any other stable assignment.

But you may be a little tired of reading by now. I will continue in Part II, where I will finally fulfill my promise to talk about saving lives.

NOTE: a comment made it clear that I needed to clarify the deferred acceptance algorithm, namely how exactly it terminates; I have made a correction to this effect. 2015-02-28