A canonical problem in graph theory is that of matching – pairing people (or nodes) based on mutual preference. The classic example of this – framed, unfortunately, in a cis-heteronormative way – is known as the marriage problem. Assuming knowledge of the whole population, men have a ranked-order list of appropriate female partners and women similarly make a ranked-order list of appropriate male partners. The question then, is can we, as an all-knowing mathematician, make a matching in which no non-matched (opposite sex) pair would prefer to be with each other than with the partners they are matched with?
The mathematical solution to “stable marriage matching” is elegant, and worth at some point a post of its own. But for the moment, I was recently struck by the economic implications of this problem. That is, I had always considered it from the vantage point of the all-knowing observer, with the implicit understanding that such scope of vision is what makes the solution possible.
Roth’s 2008 article, What have we learned from market design?, brings a new perspective to the market failures that can result from the lack of such global coordination. Because it’s such an interesting story, I include below a long excerpt describing the history of today’s residency-matching program for medical school graduates:
The first job American doctors take after graduating from medical school is called a residency. These jobs are a big part of hospitals’ labor force, a critical part of physicians’ graduate education, and a substantial influence on their future careers. From 1900 to 1945, one way that hospitals competed for new residents was to try to hire residents earlier than other hospitals. This moved the date of appointment earlier, first slowly and then quickly, until by 1945 residents were sometimes being hired almost two years before they would graduate from medical school and begin work.
When I studied this in Roth (1984) it was the first market in which I had seen this kind of “unraveling” of appointment dates, but today we know that unraveling is a common and costly form of market failure. What we see when we study markets in the process of unraveling is that offers not only become increasingly early, but also become dispersed in time and of increasingly short duration. So not only are decisions being made early (before uncertainty is resolved about workers’ preferences or abilities), but also quickly, with applicants having to respond to offers before they can learn what other offers might be forthcoming. Efforts to prevent unraveling are venerable, for example Roth and Xing (1994) quote Salzman (1931) on laws in various English market from the 13th century concerning “forestalling” a market by transacting before goods could be offered in the market.
In 1945, American medical schools agreed not to release information about students before a specified date. This helped control the date of the market, but a new problem emerged: hospitals found that if some of the first offers they made were rejected after a period of deliberation, the candidates to whom they wished to make their next offers had often already accepted other positions. This led hospitals to make exploding offers to which candidates had to reply immediately, before they could learn what other offers might be available, and led to a chaotic market that shortened in duration from year to year, and resulted not only in missed agreements but also in broken ones. This kind of congestion also has since been seen in other markets, and in the extreme form it took in the American medical market by the late 1940’s, it also constitutes a form of market failure (cf. Roth and Xing 1997, and Avery, Jolls, Roth, and Posner 2007 for detailed accounts of congestion in labor markets in psychology and law). Faced with a market that was working very badly, the various American medical associations (of hospitals, students, and schools) agreed to employ a centralized clearinghouse to coordinate the market. After students had applied to residency programs and been interviewed, instead of having hospitals make individual offers to which students had to respond immediately, students and residency programs would instead be invited to submit rank order lists to indicate their preferences. That is, hospitals (residency programs) would rank the students they had interviewed, students would rank the hospitals (residency programs) they had interviewed, and a centralized clearinghouse — a matching mechanism — would be employed to produce a matching from the preference lists. Today this centralized clearinghouse is called the National Resident Matching Program (NRMP).