Noble Matching

by on October 15, 2012 at 8:59 am in Uncategorized | Permalink

In honor of the Nobel prizes to Al Roth and Lloyd Shapley, here is a primer on matching theory. Matching is a fundamental property of many markets and social institutions. Jobs are matched to workers, husbands to wives, doctors to hospitals, kidneys to patients.

The field of matching may be said to start with the Gale-Shapley deferred choice algorithm. Here is how it works, applied to men and women and marriage (n.b. the algorithm can also work for gay marriage but it’s a little easier to explain and implement with men and women). Each man proposes to his first ranked choice. Each woman keeps her top-ranked suitor but defers accepting the proposal. Each woman also rejects her lower ranked suitors. Each rejected man proposes to his second ranked choice. Each woman rejects again any lower-ranked suitors, which may include previous suitors who have now become lower-ranked. The process repeats until no further proposals are made; each woman then accepts her top-ranked suitor and the matches are made.

A similar process works when proposal receivers may accept more than one suitor, not that useful for marriage in most of the United States but very useful for when students are applying to schools and each school accepts many students.

Now what is good about this algorithm? First, Gale and Shapley proved that the algorithm converges to a solution for a very wide range of preferences. Second, the algorithm is stable in the sense that there is no man and no woman who would rather be matched to each other than to their current match. There are of course, men who would prefer to marry other women and there are women who would prefer to marry other men but no mutually preferable match is possible. Thus, the algorithm produces a stable match.

The application to men and women is somewhat fanciful, although Match.com should clearly adopt this idea!, but the application to students and schools is very real. Gale and Shapley concluded their paper by writing:

It is our opinion, however, that some of the ideas introduced here might usefully be applied to certain phases of the admissions problem.

Indeed, this is exactly what has happened. Students in New York and in Boston are now matched to schools using versions of this algorithm. Even before Gale and Shapley the algorithm had been used, without much theorizing, by doctors allocating residents to hospitals and since Gale-Shapley and Roth the idea has been used much more extensively all over the world .The algorithm, by the way, has been picked up and extended by computer scientists notably including Knuth.

I said above that the men propose to the women–this matters because when the women propose to the men you also get a stable match but it may be a somewhat different match and in general it is better to be the one proposing. Matching becomes more difficult when, as in modern times, both men and women may propose. Fortunately, in many problems, such as with students and schools, the proposers and receivers can be fixed.

Another question is whether the algorithm can be strategically manipulated. In an Impossibility Theorem with much the same flavor as Arrow’s Theorem and the Gibbard-Satterthwaite theorem, Roth and Roth and Sotomayor proved that there is always some possibility for manipulation but the G-S algorithm can be said to minimize the opportunity for strategic manipulation; in particular for the proposers, men or say students applying to schools. it is a dominant strategy to reveal one’s true preferences.

The importance of a stable matching algorithm can be seen in what happens when such algorithms are not used. In trying to allocate residents to hospitals, for example, what typically happens when a stable algorithm is not used is unraveling and chaos. Unraveling occurs when offers are made earlier and earlier in an attempt to get a jump on the competition. Prior to the currently used National Residency Matching Program, for example, hospitals were making offers to residents up to two years in advance! All kinds of chaos arose as hospitals would make exploding offers, accept now or the offer explodes! Such offers would inevitable lead to recriminations and backing out of the offers as better matches were sought.

What Roth has done is extend the Gale-Shapley algorithm to more complicated matches and to actually design such algorithms to solve real problems. In the 1970s, for example, the medical residency algorithm began to run into trouble because of a new development, the dual career couple. How to match couples, both doctors, to hospitals in the same city? By the 1990s assortative matching in the marriage market was beginning to derail matching in the doctor-hospital market! Roth was called in to solve the problem and moved from being a theorist to a market designer. Roth and Peranson designed the matching algorithm that is now used by Orthodontists, Psychologists, Pharmacists, Radiologists, Pediatric surgeons and many other medical specialties in the United States.

Most famously, Roth has worked on improving kidney allocation. I first wrote about this in 2004 (see also these posts):

Your spouse is dying of kidney disease. You want to give her one of your kidneys but tests show that it is incompatible with her immune system. Utter anguish and frustration. Is there anything that you can do? Today the answer is yes. Transplant centers are now helping to arrange kidney swaps. You give to the spouse of another donor who gives to your spouse. Pareto would be proud. Even a few three-way swaps have been conducted.

But why stop at three? What about an n-way swap? Let’s add in the possibility of an exchange that raises your spouse on the queue for a cadaveric kidney. And let us also recognize that even if your kidney is compatible with your spouse’s there may be a better match. Is there an allocation system that makes all donors and spouses better off (or at least no worse off) and that maximizes the number of beneficial swaps? In an important paper (Warning! Very technical. Requires NBER subscription.) Alvin Roth and co-authors describe just such a mechanism and show that it could save many lives. Who says efficiency is a pedestrian virtue?

Since that time we have seen many such swaps including this record of 60 people and 30 kidneys. Truly a noble match.

Minor editing Oct. 23.

Niels October 15, 2012 at 10:17 am

Wouldn’t it make sense implementing a similar matching scheme for the annual Econ Job market?

david October 15, 2012 at 10:42 am

Designing the algorithm well requires some honesty as to what the motives of the parties are…

economist1 October 15, 2012 at 4:47 pm

I was just thinking the same thing- seems to be that the problem is that people hoard offers and don’t free them up for other better matches. Improving the matching using this research would be a huge improvement.

david October 15, 2012 at 10:54 am

An incentive-compatible, individually-rational allocation system that is ‘socialist’ (that gives the principal discretion over the extent to which the agent’s advantages garner them rewards, by leveraging a principal’s monopoly on external rent) would be a revolution in economics. Not least because one wouldn’t even have to wait for governments to take it up; under private information, it beats the price system.

Hadur October 15, 2012 at 11:13 am

There is no great stagnation in odious puns, I see

V October 15, 2012 at 11:45 am

The residency matching system turned out to be a terrible idea in practice as it allowed hospitals to collude on fixing brutal working conditions and terrible pay (what is the incentive to improve on either when better working conditions or incentives cannot be offered to participants?) so not sure why MR is endorsing it. In fact, the system was the subject of an antitrust lawsuit which seemed destined for success and for which Congress passed a hurried exemption at the behest of the hospital lobby.

Speaking as one who went through the residency matching process and residency, I would not wish that process on anyone else’s field and I consider it disappointing that the principle would be recognized by this year’s Nobel.

The Kidney matching algorithm might have much more societal value (seems to anyway from my cursory review) though I doubt there is real data that shows the overall needle moving (ie number of matches and transplants) since most of the matches would have been found under the old system. Still a cool sounding idea….

david October 15, 2012 at 11:55 am

Wikipedia suggests Roth et al were involved in the effort to redesign a 1952-vintage algorithm that had been weighted in favour of hospitals, in theory for one which is more equitable.

Millian October 15, 2012 at 12:36 pm

“The residency matching system turned out to be a terrible idea in practice as it allowed hospitals to collude on fixing brutal working conditions and terrible pay (what is the incentive to improve on either when better working conditions or incentives cannot be offered to participants?) so not sure why MR is endorsing it.”

“Speaking as one who went through the residency matching process and residency”

I see your problem. You seem to be incapable of recognising that other people, apart from yourself, have valid interests.

V October 15, 2012 at 3:55 pm

David– The new algorithm Roth et al. designed is better but given it perpetuates a model based on the central planner fallacy, I find it dubious that it would deserve a Nobel.

Miilian–Whose interests exactly are served by the residency matching system other than large academic hospital providers who are amongst the most inefficient and subsidized institutions in society? Definitely not patients (who get crappy and potentially dangerous care from residents who are overworked and clearly, not for physicians.

I see your problem. Snark is more important to you than logic.

david October 15, 2012 at 6:53 pm

The market here fails, and necessarily so, because there is no contractual enforcement of commitment. So pricing fails. Yet we would generally find it difficult to enforce commitments here, for the same reason we have no-fault divorces.

AID October 15, 2012 at 4:53 pm

There is an incentive to defect, though. If a hospital improves their working/learning conditions, then people will rank them more highly, and they can then get more desirable residents.

AC October 15, 2012 at 6:27 pm

Yeah, the problem is the dynamics around monopoly (if you don’t go through residency, you can’t be a doctor, giving hospitals enormous bargaining power), not the match system itself. The match just produces the least-crappy possibility given these constraints.

David October 16, 2012 at 9:13 am

Is collusion required for the resident matching system to work?

The “chaos” that Tabarrok describes seems like just a competitive marketplace. By instituting the matching system, it seems like the system gets less competitive, but the hospitals have to collude to adhere to the matching program and not act “chaotically”.

Is there a feature to Roth’s algorithm whereby everyone’s best option is to match, or would some people and institutions be better off not matching if they could get away with it?

jason braswell October 15, 2012 at 11:59 am

I’m a little unclear on the algorithm still.

Do women who reject unacceptable proposals in the first round *know* that there will be subsequent proposals? That is, do they know that they are someone’s second choice?

Although it seems unlikely with a large enough group, it’s possible that some woman is a first choice for some men but is nobody’s second choice, no? If a woman were aware of this, proposals in the first round that might otherwise be unacceptable might become acceptable.

Alex Godofsky October 15, 2012 at 12:25 pm

“Unacceptable” is defined as “not the best I have seen”.

Enrique October 15, 2012 at 12:48 pm

What about Gale? Why doesn’t he get to share in this year’s prize?

Economiser October 15, 2012 at 12:51 pm

Nobel recipients must be alive at the time of winning the award. Gale died a few years ago unfortunately.

Enrique October 15, 2012 at 3:25 pm

Thanks. I was not aware of Gale’s passing in 2008

kurt October 15, 2012 at 12:50 pm

So you don’t make people worse off, but what about envy? If previously you could only allocate 20%, but then you match and get 90%, those 10% left out are not going to be happy! Especially if the allocation is by force, not voluntarily.

Robert Reichardt October 15, 2012 at 1:12 pm

I think you missed the student to school matching being used in Denver.
Look at the links under SchoolChoice Transparency Committee
http://www.aplusdenver.org/work/reports

Jr October 15, 2012 at 2:05 pm

Actually, I do not think the Gale-Shapely algorithm works for gay marriage. For one thing with gay marriage how do you make the distinction between those who make proposals and those who don’t?

Secondly the “gay marriage problem”, usually called the roommate problem, might not have any stable solution so any algorithm is going to do worse than Gale-Shapely does for the usual marriage problem.

Alex Tabarrok October 15, 2012 at 2:43 pm

Jr makes a good point. I had in mind a fixed set of proposers and receivers but I have edited slightly to clarify.

mw October 15, 2012 at 2:26 pm

“why not n way?” because there are only 3 common blood types
http://www.youtube.com/watch?v=4tdOY-HHC7s

RR October 15, 2012 at 4:19 pm

“not that useful for marriage in …most…. of the United States “. Subtle dig at Utah ?

whatsthat October 15, 2012 at 5:48 pm

“Even before Gale and Shapley the algorithm had been used, without much theorizing, by doctors allocating residents to hospitals and since Gale-Shapley and Roth the idea has been used much more extensively all over the world”

That, to me, is the most important line.

Mario Rizzo October 15, 2012 at 6:52 pm

Maybe it is a matter of taste. But as useful as some of this may be for worthy causes like kidney donor matching, I view these as purely technical contributions that do not rise to the level of Nobel prizes. But I understand the committee has got to find people every year. But this is one prize that will be soon forgotten.

david October 15, 2012 at 8:09 pm

I suspect the Nobel committee is signalling its approval of overt non-price market engineering as much as anything.

srp October 15, 2012 at 11:08 pm

I disagree that this prize isn’t a great one. This award will be remembered because it is about an actual well-defined piece of economic science that directly makes systems work better for those involved. And there are important insights about how the “coincidence of wants” among diverse participants can be institutionally tracked down.

It’s kind of funny that Shapley won for work other than the Shapley Value just as Allais won for work other than the Allais Paradox. In this case, though, it makes sense.

TGGP October 16, 2012 at 2:00 am

That kind of dismissive attitude toward applied work sounds like it could come from a “pure” mathematician, but incomprehensible to those who head to the private sector to solve customers’ problems. When next year’s Econ Nobel is announced, I’ll be sure to reply to whatever comment you make by pointing out that Roth’s award was more richly deserved. :)

no name October 16, 2012 at 2:29 pm

You’re right, instead we should award the Nobel prize to such ‘scholars’ as you, Prof. Rizzo, whose academic contributions are limited to tiring screeds against the imagined specter of ‘paternalism.’

I’m more excited about this prize than the last few. The work being recognized here is work that I’d hold up to those who attempt to feebly criticize our discipline. It takes what internet commenters like to characterize as abstract, meaningless theory and shows how it can be used to inform solutions to real-life matching problems, similarly to how number theory informed cryptography.

If you paid attention to how economists have reacted to the prize, you’d notice how excited everyone is about this prize.

YSK October 15, 2012 at 10:59 pm

While it is commendable that the Nobel prize went to work with practical applications, it is important to note that the applications are very limited. For example, the much praised matching between residents/hospitals fails as soon as a little complexity gets is.

freethinker October 16, 2012 at 10:30 am

The Nobel Foundation seems to think that only the economists who work on problems pertinent to the American economy alone are worthy of the Nobel Prize. I am eagerly looking forward to someone explaining how the contributions of this year’s prize are relevant to poor economies where most people live.

Tom October 16, 2012 at 5:01 pm
freethinker October 16, 2012 at 7:47 pm

YSK says: “While it is commendable that the Nobel prize went to work with practical applications, it is important to note that the applications are very limited”. If this is so with reference to the American context, how relevant will these ideas be in a poor economy?

Eric L October 18, 2012 at 12:43 am

(n.b. the algorithm can also work for gay marriage but it’s a little easier to explain and implement with men and women)

Wait, what? When this was covered in a C.S. theory class my professor gave us the proof that there isn’t any guarantee that stable pairings even exist in the gay marriage case, let alone an algorithm guaranteed to find one:

Consider four people, Adam, Bob, Carl, and Doug. Adam’s first choice is Bob, Bob’s first choice is Carl, and Carl’s first choice is Adam. Doug is everyone else’s last choice. So what pairing do you get? No matter who you pair with Doug, that person is someone else’s first choice, and they prefer anyone over Doug, so no pairing is stable.

Is there some relaxed objective for that sort of case that the algorithm is supposed to meet?

overnight fluoxetine October 24, 2012 at 2:04 am

david, I am totally agree with your thoughts. Keep doing these type of work.

Comments on this entry are closed.

Previous post:

Next post: