Stable matches and saving lives by designing exchanges: Part I

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