Keywords

JEL Classifications

‘Matching’ is the part of economics that focuses on the question of who gets what, particularly when the scarce goods to be allocated are heterogeneous and indivisible; for example, who works at which job, which students go to which school, who receives which transplantable organ, and so on. Studying how particular matching markets succeed at creating efficient matches, or fail to do so, has yielded insights into how markets in general work well or badly.

Because market failures have sometimes been successfully fixed by devising new rules for both centralized and decentralized market organization, matching has been a major focus of the emerging field of market design. Some designs by economists have included labour market clearing houses for doctors and other health-care workers in the United States, both for their first jobs and as they enter specialties. Clearing houses have also been implemented in less traditional markets, which cannot adjust prices or wages to help clear the market, such as the matching of students to schools in New York City and in Boston. And new clearing houses are being implemented for the organization of live-donor kidney exchanges among patients in need of a kidney transplant who have willing donors with whom they are incompatible.

In the next section we review some studies of matching, including some market failures that have been addressed either by introducing appropriate rules to a decentralized market (as in admissions to graduate programmes in American universities), or by introducing a centralized clearing house (as in the markets for new doctors in the United States, Canada, and Britain). The subsequent two sections consider the simple theory behind some clearinghouse designs. Then we return to some of the successful market design applications, which build on the theoretical models, but handle practical problems that are sometimes not yet fully understood in theory.

We focus on three kinds of market failure that sometimes impede efficient matching.

  1. 1.

    Failure to provide thickness; that is, to bring together enough buyers and sellers (or firms and workers, schools and students, and so forth) to transact with each other.

  2. 2.

    Failure to overcome the congestion that thickness can bring, that is, that can result when lots of buyers and sellers are trying to transact. That is, failure to provide enough time, or failure to make transactions fast enough so that market participants can consider enough alternative possible transactions to arrive at satisfactory ones.

  3. 3.

    Failure to make it safe for market participants to reliably reveal or otherwise act on their information.

Some Market Failures and Their Consequences

Unravelling, Congestion and Centralized Clearing Houses

A variety of professional labour markets have suffered from the unravelling of appointment dates: from year to year, appointments were made earlier and earlier in advance of actual employment. Markets that had once been thick, with many employers and applicants on the market at the same time, became thin, as potential employees faced early offers, dispersed in time, to which they had to respond before they could learn what other offers might be forthcoming. That is, applicants often received ‘exploding’ offers that had to be accepted or rejected without waiting to see whether a more desirable offer might be forthcoming. An applicant who accepts such an offer, in the case that acceptances are binding, will never learn of the more desirable offers that might have become available, but if the offer is reasonably desirable rejecting it might be very risky. And, when applicants are quickly accepting offers in this way, employers, when they make offers, have to start taking into account whether the offer is likely to be accepted, since by the time an offer is rejected other desirable applicants may have already accepted offers elsewhere. This often makes unravelling a dynamic process, with offers being made earlier and shorter in duration from year to year. This kind of unravelling has been described in detail in markets for lawyers (Avery et al. 2001), gastroenterologists (Niederle et al. 2006) and many others (see Roth and Xing 1994). A clear example is the market for new doctors (Roth 1984).

The first job for almost all new doctors in the United States and Canada is as an intern or resident at a hospital. In the early 1900s, medical graduates were hired for such jobs near the end of their fourth year of medical school, just before graduation. By the 1930s, hiring was largely completed half a year before graduation, and by the 1940s it had moved to sometimes as much as two years before graduation. That is, in the early 1940s, students were being hired long before they would begin work, at dispersed times, and without much opportunity to consider alternatives, and long before they had sufficient experience to reveal either to employers or to themselves what kinds of medicine they would most prefer and be best able to practise. There was widespread recognition among the participants that the market was often failing to create the most productive matches of doctors to hospitals, both because there was too little opportunity to consider alternatives and because the matching was being done before important information about students became available.

One way in which many markets tried to address this failure was by attempting to establish rules concerning when offers could be made. In the market for new American doctors, the most concerted attempt at this kind of solution began in 1945 with the help of the medical schools, which agreed not to release any information to hospitals about students until a specified date.

However, the market experienced congestion in that hospitals found that they did not always have enough time to make all the offers they would like if their first offer was declined. Over the next few years students were called upon to make increasingly prompt decisions whether to accept offers. In 1945 offers were supposed to remain open for 10 days. By 1949 a deadline of 12 hours had been rejected as too long. Hospitals were finding that, if an offer was rejected after even a brief period of consideration, it was often too late for them to reach their next most preferred candidates before they had accepted other offers. Even when there was a long deadline much of this action was compressed into the last moments, because a student who had been offered a position that wasn’t his first choice would be inclined to wait as long as possible before accepting, in the hope of eventually being offered a preferable position. So hospitals felt compelled to pressure students to reply immediately, and offers conveyed by telegram were frequently followed by phone calls requesting an immediate reply.

Congestion can be a problem in any market in which transactions take some time, but it is especially visible in entry-level professional labour markets in which many workers and jobs become available at the same time (for example, after graduation from university, medical school, law school, and so on).

In the face of congestion, many markets unravel, as employers try to gain more time to make offers by starting to do so earlier (Roth and Xing 1994). But the market for new doctors found a solution in the form of a centralized clearing house. Starting in the early 1950s, the various medical groups organized a centralized clearing house, which remains in use today, having undergone some changes over the years. Nowadays, a medical student applies to hospitals and goes on interviews in the winter of the final year of medical school, and then in February submits an ordered preference list of positions to the centralized clearing house, the National Resident Matching Program (NRMP). At the same time, the residency programmes (the employers) submit an ordered preference list of candidates. Once all the preference lists are collected, the clearing house uses an algorithm to produce a match, and residency programmes and applicants are informed to whom they have been matched. Although this clearing house began as an entirely voluntary one, it has been so successful that today it is virtually the only way that most residencies are filled. As we will see below, that success depends critically on the matching algorithm.

The NRMP, and clearing houses like it, also make very clear the kinds of issues involved for a marketplace to make it safe for participants to reveal their information. In a clearing house in which you are asked to state your preferences, the question is simply: is it a good idea to state your true preferences, or would you do better otherwise? For the NRMP we’ll see that stating true preferences is indeed both safe and sensible. We’ll also discuss clearing houses that failed this test, like the one for placing students into schools in Boston that consequently failed to accomplish their objectives in other ways also, and were redesigned.

Before presenting some formal models that will allow us to start to explain which matching algorithms and clearing houses have been successful and which have failed, it will be helpful to think about several different kinds of matching markets.

Two-Sided and One-Sided Matching Markets

Labour markets, like the market for new doctors, are usually modelled as two-sided markets, in which agents on one side of the market (workers) need to be matched with agents on the other side (employers), and each agent has preferences over possible matches. We’ll see below that this two-sided structure allows strong conclusions to be drawn about the properties of matchings and matching mechanisms.

In many markets this two-sided structure is absent. One way this occurs is when any participant in the market can be matched with any other. For example, if a group of people want to form pairs to be roommates or bridge partners, any one of them can in principle be matched with any other, although not all matchings would be efficient. We encounter markets of this kind when we speak of kidney exchange.

Another way in which markets can be one-sided is if the agents in the market need to be matched to objects, for example when people need to be assigned rooms in a dormitory, or places in a public school that doesn’t itself have preferences or take strategic actions (unlike in a two-sided matching market). That is, such a market matches people to places, but only one side, the people, are active participants in the market. Some markets can also be hybrids, with both two and one-sided properties (as when schools aren’t strategic players, but still have priorities over students).

Below we consider some static models of two and one-sided matching that have proved useful in the design of clearing houses, and in understanding what they do. In the section on design, we’ll also speak about some decentralized design solutions to various market failures, such as unravelling. While there has been some good initial progress on formal models of decentralized markets, and dynamic models in which phenomena like unravelling can play out over time (see for example, Li and Rosen 1998), these areas are still in need of development, and have not yet received the theoretical attention commensurate with their importance in the study of markets generally (though see Niederle and Yariv 2007).

Formal Models of Matching

Two-Sided Matching Models

The workhorse models of two-sided matching come in several varieties. The simplest, presented in detail below, is the ‘marriage model’ in which each firm seeks to hire only a single worker, and wages and other kinds of price adjustment are represented simply in the preferences that workers and firms have for each other (for example, in these models, wages are part of the job description that determines preferences). However the kinds of results we present here generalize to models in which wage and price formation is explicitly included, some pointers to such models are included in the references.

The marriage model consists of two disjoint sets of agents, men = {m1,…, mn} and women = {w1, …, wp}, each of whom has complete and transitive preferences over the agents on the other side (and the possibility of being unmatched, which we model as being ‘matched to yourself’). Preferences can be represented as rank order lists, for example, if man mi’s first choice is w3, his second choice w2 [w3 > mi w2] and so on, until at some point he prefers to remain unmatched, that is P(mi) = w3, w2, …mi…. If agent k (on either side of the market) prefers to remain single rather than be matched to agent j, that is, if k > k j, then j is said to be unacceptable to k. If an agent is not indifferent between any two acceptable mates, or between being matched and unmatched, we’ll say he/she has strict preferences.

An outcome of the game is a matching: μ: M ∪ W → M ∪ W such that w = μ(m) iff μ(w) = m, and for all m and w either μ(w) is in M or μ(w) = w, and either μ(m) is in W or μ(m) = m. That is, a matching matches agents on one side to agents on the other side, or to themselves, and if w is matched to m, then m is matched to w.

A matching μ is blocked by an individual k if k prefers being single to being matched with μ(k), that is, k > k μ(k). A matching μ is blocked by a pair of agents (m,w) if they each prefer each other to the partner they receive at μ, that is, w > m μ(m) and m>w μ(w).

A matching μ is stable if it isn’t blocked by any individual or pair of agents.

A stable matching is Pareto efficient, and in the core, and in this simple model the set of (pairwise) stable matchings equals the core.

Theorem 1 (Gale and Shapley 1962)

A stable matching exists for every marriage market.

Gale and Shapley approached this problem from a purely theoretical perspective, but proved this theorem via a constructive algorithm of the kind that has subsequently turned up at the heart of a variety of clearing houses.

Deferred Acceptance Algorithm, with Men Proposing

(roughly the Gale and Shapley 1962 version).

  • Step 0. If some preferences are not strict, arbitrarily break ties (for example, if some m is indifferent between wi and wj, order them consecutively in alphabetical order. Different agents may break ties differently: that is, tie-breaking can be decentralized by having each agent fill out a strict preference list...).

  • Step 1(a). Each man m proposes to his 1st choice (if he has any acceptable choices).

  • Step1(b). Each woman rejects any unacceptable proposals and, if more than one acceptable proposal is received, ‘holds’ the most preferred and rejects all others. …

  • Step k(a). Any man who was rejected at step k-1 makes a new proposal to its most preferred acceptable mate who hasn’t yet rejected him. (If no acceptable choices remain, he makes no proposal.)

  • Step k(b). Each woman holds her most preferred acceptable offer to date, and rejects the rest. STOP: when no further proposals are made, and match each woman to the man (if any) whose proposal she is holding.

Note that the proof of the theorem now follows from the observation that the matching produced in this way is itself stable. If some man would prefer to be matched to a woman other than his assigned mate, he must, according to the algorithm, have already proposed to her, and she has rejected him, meaning she has a man she strictly prefers, hence they cannot form a blocking pair.

Roth (1984) showed that the algorithm adopted by the medical clearing house in the 1950s was equivalent to the hospital proposing deferred acceptance algorithm. Gale and Shapley observed that which side of the market proposes in a deferred acceptance algorithm has consequences.

Theorem 2 (Gale and Shapley 1962)

When all men and women have strict preferences, there always exists an M-optimal stable matching (that every man likes at least as well as any other stable matching), and a W-optimal stable matching. Furthermore, the matching μ M produced by the deferred acceptance algorithm with men proposing is the M-optimal stable matching. The W-optimal stable matching is the matching μ W produced by the algorithm when the women propose.

Note that the algorithm has been stated as if people take actions in the course of the algorithm, and we can ask whether those actions would best serve their interests. To put it another way, is it possible to design a clearing house in which a matching is produced from participants’ stated rank order lists in such a way that it will never be in someone’s interest to submit a rank order list different from their true preferences? The following theorem answers that question in the negative.

Theorem 3 Impossibility Theorem (Roth – see Roth and Sotomayor 1990)

No stable matching mechanism exists for which stating the true preferences is a dominant strategy for every agent.

However it is possible to design the mechanism so that one side of the market can never do any better than to state their true preferences.

Theorem 4 (Dubins and Freedman, Roth – see Roth and Sotomayor 1990)

The mechanism that yields the M-optimal stable matching (in terms of the stated preferences) makes it a dominant strategy for each man to state his true preferences.

The conclusions of Theorems–3 also hold for a variety of related models (in which firms employ multiple workers, and wages are explicitly allowed to vary; see, for example, Shapley and Shubik 1971; Kelso and Crawford 1982, for notable early models of matching with money, and see Roth and Sotomayor 1990; Hatfield and Milgrom 2005). However, when we look at many-to-one matching models (in which firms employ multiple workers but workers seek just one job), we have to be careful. It turns out that no procedures exist that give firms a dominant strategy, but that a worker proposing deferred acceptance algorithm still makes it a dominant strategy for workers to state their true preferences (see Roth and Sotomayor 1990 for more details and further references). (These results are closely connected to related results in auction theory; see in particular Hatfield and Milgrom 2005; Milgrom 2004.)

When the market for medical residents was redesigned Roth and Peranson (1999), a number of practical complications had to be dealt with, such as the fact that about 1000 graduates a year go through the match as couples who wish to be matched to nearby jobs, and hence have joint preferences over pairs of residency programmes. While this can cause the set of stable matchings to be empty, in practice this has not proved to be a significant problem (see also Roth 2002, on engineering aspects of economic design).

One-Sided Matching Models

Shapley and Scarf’s ‘House’ Markets

Another basic model of matching markets was introduced by Shapley and Scarf (1974). They model a simple barter economy in which each one of n agents owns an indivisible good (which they call a house) and has preferences over all houses in the economy. Each agent has use for only one house and trade is only feasible in houses (that is, there is no money in their model). An allocation μ in this context is a matching of houses and agents so that each agent receives one and only one house. An exchange in this market does not need to be bilateral. An allocation μ is in the core if no coalition (including single agent coalitions) of agents can improve upon it (in the sense that all are weakly better off and at least one is strictly better off) by swapping their own houses. Shapley and Scarf attribute to David Gale the following top trading cycles algorithm (TTC) which can be used to find a core allocation for any housing market:

  • Step 1: Each agent points to the owner of her most preferred house (which could possibly be herself). Since there are finite number of agents there is at least one cycle (where a cycle is an ordered list (i1, i2, …, ik) of agents with each agent pointing to the next agent in the list and agent ik pointing to agent i1). In each cycle the implied exchange is carried out and the procedure is repeated with the remaining agents.

In general, at.

  • Step k: Each remaining agent points to the owner of her most preferred house among the remaining houses. There is at least one cycle. In each cycle the implied exchange is carried out and the procedure is repeated with the remaining agents.

The algorithm terminates when each agent receives a house.

Theorem 5 (Shapley and Scarf 1974)

The TTC algorithm yields an allocation in the core for each housing market.

The core has some remarkable properties in the context of housing markets. The following propositions summarize the most notable of these results.

While exchange is feasible only in houses, a competitive allocation of a housing market can be defined via ‘token money’. There is an important relation between the core and the competitive allocation for this very basic barter economy.

Theorem 6 (Roth and Postlewaite 1977)

There is a unique allocation in the core (which can be obtained with the TTC algorithm) when agents have strict preferences over houses. Moreover the unique core allocation coincides with the unique competitive allocation.

Another remarkable feature of this model is that the top trading cycles mechanism makes it safe for agents to reveal their true preferences.

Theorem 7 (Roth 1982)

The core as a mechanism is strategy-proof when agents have strict preferences over houses. That is, truth-telling is a dominant strategy for all agents in the preference revelation game in which TTC is applied to the stated preferences to produce an allocation.

Moreover, it is essentially the only mechanism that is strategy-proof among those that are Pareto efficient and individually rational (in the sense that an agent never receives a house inferior to her own).

Theorem 8 (Ma 1994)

The core is the only mechanism that is Pareto efficient, individually rational and strategy-proof.

House Allocation Problems

Hylland and Zeckhauser (1979) introduced the house allocation problem which only differs from housing markets in property rights: There are n houses to be allocated for n agents where each agent has use for only one house and has strict preferences over all houses. Unlike in housing markets, no agent owns a specific house. The mechanism known as random serial dictatorship (RSD) is widely used in real-life allocation problems of this sort, such as assigning students to dormitory rooms.

Under RSD agents are randomly ordered (from a uniform distribution) in a list and the first agent in the list is assigned her top choice house, the next agent is assigned her top choice among the remaining houses, and so on. In addition to its popularity in practice, RSD has good incentive and efficiency properties.

Theorem 9

RSD is ex post Pareto efficient and strategy-proof.

Recall that the only difference between house allocation problems and housing markets is the initial property rights, and the core is very well-behaved in the context of the latter. This observation motivates the mechanism core from random endowments (CRE): randomly assign houses to agents with uniform distribution, interpret the resulting matching as the initial allocation of houses, and pick the core of the resulting housing market. It turns out, CRE is equivalent to RSD.

Theorem 10 (Abdulkadiroglu and Sönmez 1998)

For any house allocation problem CRE and RSD yield the same lottery and hence they are equivalent mechanisms.

House Allocation with Existing Tenants

Housing markets and house allocation problems have very different property rights. The former is a pure private ownership economy where each house ‘belongs’ to a specific agent, whereas in the latter no strict subset of the grand coalition has claims on any house. Abdulkadiroglu and Sönmez (1999) introduced the following hybrid house allocation with existing tenants model. There are two kinds of agents: existing tenants each of whom owns a house, and newcomers none of whom has claims on a specific house. In addition to the occupied houses owned by existing tenants, there are also vacant houses. As in house allocation problems no specific person or group has claims on any vacant house. Suppose that the number of newcomers is equal to the number of vacant houses and hence the number of agents is equal to the number of houses. Agents have strict preferences over all houses and each existing tenant is allowed to keep her current house.

Abdulkadiroglu and Sönmez introduced the following you request my house −1 get your turn algorithm (YRMH–IGYT) which generalizes TTC as well as RSD. Under YRMH–IGYT, agents are randomly ordered in a line and initially only the vacant houses are available. The first agent in the line is assigned her top choice provided that it is either her own house or an available house (in which case her own house becomes available) and the process continues with the next agent in the line.

If, however, her top choice is an occupied house, the line is adjusted and the owner of the requested house is moved right in front of the requester. The process continues in a similar way with either the owner of the requested house getting assigned his own house or an available house (making his own house available), or otherwise his requesting an occupied house and upgrading its owner to the top of the line. When the process continues in a similar way there will either be a cycle of existing tenants (as in TTC) who can swap their own houses or a chain (i1, i2, …, ik) of agents where agent i1 is assigned an available house and each of the following agents is assigned the preceding agent’s house.

The resulting mechanism inherits the attractive properties of its ‘parents’.

Theorem 11 (Abdulkadiroglu and Sönmez 1999)

The YRMH–IGYT mechanism is strategy-proof, ex post Pareto efficient, and individually rational (in the sense that no existing tenant receives a house inferior to her own).

Kidney Exchange

Living donors are an important source of kidneys for transplantation. But a patient with a willing living donor may not be able to receive a transplant because of a blood-type or immunologic incompatibility between her and her donor. Recently transplant centres around the world developed the possibility of pairwise kidney exchange in which two such pairs can exchange donors in case the donor in each pair is compatible with the patient in the other. Another interesting option is indirect kidney exchange in which the patient of an incompatible pair receives priority in the deceased donor waiting list if her incompatible donor donates a kidney to that waiting list. However, prior to 2004 only a very few exchanges had been accomplished, in large part because the market wasn’t thick, and no databases were being maintained of incompatible patient–donor pairs. In an effort to organize kidney exchange on a larger scale, Roth et al. (2004) introduced the following kidney exchange model. There are a number of patients each with a (possibly) incompatible donor. For each patient a subset of donors can feasibly donate a kidney and the patient has strict preferences over these donors and his own donor (who may or may not be compatible with him). In addition to ranking all compatible donors, each patient also ranks a ‘waiting list option’ which represents trading his donor’s kidney with a priority in the waitlist. An allocation in this context is a matching of patients and donors such that:

  • each patient is matched with either a donor or the waiting list option, and

  • each donor can be matched with at most one patient while the waiting list option may be matched with multiple patients.

(The donors who remain unmatched are offered to the waitlist in exchange for the equal number of priorities awarded by the allocation). We are only interested in individually rational allocations where patients receive neither a donor nor the waiting list option unless it is indicated to be at least as good as his donor’s kidney. If the waiting list option is ranked inferior to his donor for a patient, that means the patient is not interested in such an exchange. As in the case of house allocation with existing tenants model, an allocation consists of cycles and chains where

  • each patient in a cycle receives a kidney from the donor of the next patient in the cycle, and

  • all but the last patient in a chain receive a kidney from the donor of the next patient in the chain whereas the last patient in the chain receives a priority in the waiting list.

If the waiting list option is infeasible, then the resulting problem is formally equivalent to a housing market and therefore has a unique allocation in the core which can be obtained via the TTC algorithm. In this simpler model an allocation (including the one in the core) consists of only cycles. When the waiting list option is feasible an allocation can also have chains (which are indirect exchanges and their more elaborate versions). In this more general model Roth et al. (2004) introduce a class of top trading cycles and chains (TTCC) algorithms each of which extend the TTC. Among these algorithms Roth et al. (2004) identify one that is Pareto efficient and strategy-proof:

Theorem 12 (Roth et al. 2004)

There exists a TTCC mechanism that is Pareto efficient and strategy-proof.

In practice, as kidney exchanges have become organized on a larger scale in New England and elsewhere (see Roth et al. 2005a, b, 2007), there has been a focus, for logistical reasons, on cycles and chains that are relatively short, typically only involving exchanges among two or three patient–donor pairs.

The deferred acceptance algorithm (for two-sided markets) also has some uses in one-sided allocation problems in which children are to be allocated to schools, if the schools, although not active strategic players, have priorities over students that need to be treated like preferences (Abdulkadiroglu and Sönmez 2003).

Design and Engineering

Introducing a Centralized Stable Match

Of the several dozen markets and submarkets we know of that established clearing houses in response to unravelling in a (two-sided) labour market, those that produce stable matchings have been most successful. Of particular note in this regard are the markets used in the various regions of the British National Health Service. In the 1960s, these markets suffered from the same kind of unravelling that had afflicted the American medical market in the 1940s. A Royal Commission recommended that each region organize a centralized clearing house (see Roth 1991), and the various regions each invented their own matching algorithms, some of which were stable and some of which were not (an example of such unstable algorithms will be given later). Those clearing houses that produced stable matches succeeded, while those that did not most often failed and were abandoned. But over a broad range of markets, the correlation between stability and success in halting unravelling isn’t perfect; some unstable mechanisms remain in use, and some stable mechanism have occasionally failed, as we will discuss later. And there are other differences between markets than the way their clearing houses are designed. This is why, in order to establish that producing a stable outcome is an important feature for the success of a match, controlled experiments in the laboratory can be informative.

The laboratory experiments reported by Kagel and Roth (2002) help to verify the influence of a stable or unstable matching mechanism. After unravelling had begun in a small laboratory market, a clearing house was introduced using either the stable deferred acceptance algorithm or the unstable algorithms that failed in various regions of the British National Health service (Roth 1991). In the lab, as in the field, participants learned to wait for and use the stable algorithm, but learned to arrange their matches early and thus avoid using the unstable algorithm. Note that a laboratory market is quite different from a naturally occurring labour market, but it has the advantage that it allows the effect of the different algorithms to be observed in an environment in which everything else is the same.

Centralized clearing houses that yield stable outcomes have sometimes been introduced to organize markets suffering from failures other than unravelling (and the resulting lack of thickness), but related to congestion or the safety of revealing private information.

Examples of algorithms that produce unstable outcomes, but have been used in a number of market clearing houses, are so called priority algorithms, used for example by some British clearing houses, and also in several school choice problems in the United States. A priority algorithm classifies different matches in terms of priorities, based on the rank orders submitted, and then makes feasible matches in order of priority. In Boston, for example, the centralized system attempted to give as many students as possible their first choice school. The difficulty with the system was that students who did not get assigned to their first choice were much less likely to be assigned to the school they had listed as their second choice than they would have been if they had listed it as their first choice, since those schools often get filled by students who list them as their first choice. This means participants have strong incentives to not report their preferences truthfully, if there is a good chance that they would not be admitted to their true first choice school; it might be wiser to list their second-choice school as their first choice. The newly adopted Boston clearing house fixes this problem using a deferred acceptance algorithm (Abdulkadiroglu et al. 2005, 2006).

Some markets manage to halt unravelling, but still suffer from congestion. The market for clinical psychologists (before it reorganized through a modified deferred acceptance algorithm, see Roth and Xing 1997) and the match of students to New York City high schools before it was redesigned (Abdulkadiroglu et al. 2005, 2006) are good examples. Clinical psychologists tried to run a deferred acceptance algorithm over the phone in the course of a day, ‘match day,’ from 9:00 a.m. to 4:00 p.m. All offers had to remain open until 4 p.m., and students were supposed to hold only one offer at a time. Even though turnaround time in this market was very fast (offers took about five minutes, rejections about one minute), simulating a deferred acceptance algorithm in real time, for a market with about 2000 positions in 500 programmes, takes much longer than the seven hours of match day. (And making the market longer may increase the effects of congestion, if it means that participants can no longer stay by the phone for the whole market, so that the time for an offer to be made and rejected becomes disproportionately longer.) Congestion is an issue whenever a large number of offers have to be made. The system used to assign students to New York City high schools used to be carried out through the mails, and over 30,000 students a year were ‘stranded’ on waiting lists and had to be assigned to a school for which they had expressed no preference. The new New York City clearing house is able to process preferences quickly, and in the four years following its adoption in 2003 fewer than 3000 students had to be assigned each year to a school for which they had expressed no preference.

What Are the Effects of a Centralized Match?

Centralized clearing houses can help make markets thick and uncongested, and avoid unravelling. Studying their effect on various markets can also help us understand how clearing houses and the timing of the market (for example, how far a labour market operates in advance of employment) influence the outcome of the market in other respects. For example, the market for gastroenterology fellows provides us with a natural case study of the effects of a clearing house not only on hiring practices (namely the timing of the market, and the kinds of offers that are made), but also employment opportunities, job placement and the potential impact on wages.

Gastroenterology fellows are doctors who have completed three years of residency in internal medicine, and are now employed in a fellowship that will result in their becoming board certified sub-specialists in gastroenterology. The market in which gastroenterology fellows are hired operated in a decentralized way for many years, and experienced the problems of congestion, unravelling and exploding offers, as described above in connection with the market for medical residents. In 1986, various internal medicine sub-specialties organized a clearing house called the Medical Specialties Matching Program (MSMP), sponsored by and organized along the same lines as the NRMP (which operates the resident match). But in the mid-1990s, gastroenterology fellowship programmes, and applicants, started to defect from the match, and the gastroenterology market again unravelled. A match was successfully re-established only in 2006 (Niederle et al. 2006). In those intervening years, as the market unravelled, the national market broke up into more local markets (Niederle and Roth 2003b). Fellowship programmes, particularly smaller ones, had a larger tendency to hire their own residents than under a centralized match.

A second aspect of the outcome that received prominence in 2002 is the question of whether a match affects wages. An antitrust lawsuit against the NRMP and numerous other defendants was brought in 2002 by 16 law firms on behalf of three former residents seeking to represent the class of all former residents (and naming as defendants a class including all hospitals that employ residents).

Niederle and Roth (2003a) showed empirically that in fact there is no difference in wages between medicine sub-specialties that use a match and those that don’t. The suit was dismissed in 2004 following legislation intended to clarify that the medical match is a marketplace and does not violate antitrust laws.

The theory of the complaint was that a match holds down wages for residents and fellows. Bulow and Levin (2006) present a very stylized theoretical model providing some logical support for this possibility, by comparing a market with impersonal prices (to represent the NRMP) with perfectly competitive prices at which each worker is paid his or her marginal product. Subsequent theoretical papers have shown that the conclusion about wage suppression doesn’t necessarily follow if the model is expanded to include the possibility of firms hiring more than one worker (Kojima 2007), or when the model incorporates the actual procedures by which the medical match is conducted (Niederle 2007). Furthermore, decentralized markets may often fail to achieve stable outcomes (Niederle and Yariv 2007).

Beyond Centralized Matching. Why Do Some Markets Work Well, While Others Do Not?

We have seen that stability is an important feature for a centralized match to remain in use. However, the history of the gastroenterology market shows that producing a stable outcome is not sufficient to guarantee a successful clearing house. For a centralized match to work well, participants need to have incentives to participate in the match. McKinney et al. (2005) observed that the collapse of the gastroenterology fellowship match seems to have been caused by an unusual shock to the supply of highly qualified gastroenterology fellows, a kind of shock that was not observed in other internal medicine sub-specialties that continued to use a match. Furthermore, market conditions seemed to have stabilized, so that a centralized match would work well once again, if it could be successfully reinstated.

However, many gastroenterology fellowship programmes, when they considered reinstituting a match, were concerned that, while they were willing to refrain from making the early offers that had become customary, and wait for the match, their main competitors would continue to make early exploding offers to promising applicants. Such concerns could effectively prevent a successful restart of a centralized clearing house.

This raises the more general question as to why some markets unravel and experience congestion problems in the first place, while others do not. Empirically, most markets that experience congestion also experience that employers (hospitals, federal judges, colleges...) make short-term offers, with a binding deadline, and in which the acceptance of an offer is often effectively binding (Niederle and Roth 2007, for descriptions in the markets for law graduates, and for college admissions, see for example, Avery et al. 2001, 2003, 2007).

On the other hand there are markets that do not unravel, such as the market for graduate school admission. In this market, a policy (adopted by the large majority of universities) states that offers of admission and financial support to graduate students should remain open until 15 April. Furthermore, a student faced with an earlier deadline is explicitly encouraged to accept this offer, and, in case a better one is received before 15 April, to renege on that former acceptance. This of course makes early exploding offers much less attractive to make. Niederle and Roth (2007) explore environments in which either eliminating the possibility of making exploding offers or making early acceptances non-binding helps prevents markets from operating inefficiently early.

These insights were used to help reorganizing the gastroenterology fellowship match. To reduce the concerns of programmes that their competitors would start making exploding offers before the match, a resolution was adopted by the four main professional gastroenterology organizations that stated that acceptances made before the match were not to be considered binding, and such applicants could still change their minds and participate in the match. For an account of the effects of a centralized clearinghouse on the outcomes of a market, and the experience of the gastroenterology fellowship market, see Niederle and Roth (2008).

Directions for Future Research

As economists’ understanding of the matching function of markets increases, and as economists are more often called upon to help design markets, one challenge will be to understand better how decentralized markets work well or badly, and not only in the final transactions.

For example, a common problem in many entry-level labour markets (and in dating and marriage markets) is that participants do not have well formed preferences over potential matching partners, and forming those preferences is often very costly. For example, in the American market for assistant professors, economics departments receive hundreds of applications for any position, but in general interview only about 30 candidates at the annual winter meetings. From among those they interview, they must decide whom to fly out for extended campus visits and seminars, and it is from among this latter set of candidates that they eventually choose to whom to make an offer. Because this is a time-consuming and costly process many departments have to take care to interview applicants who not only have a good chance of being desirable colleagues, but who also have a good chance of accepting an offer if one is made. This often amounts to a coordination problem: not all departments should interview the same applicants. Allowing applicants to credibly submit information about their interest in particular schools can help alleviate this coordination problem, and in 2007 the American Economic Association implemented a signalling mechanism of this sort in the market for economists.

In general, the study of the matching function of markets has directed attention at the design of rules and procedures of both centralized and decentralized markets. The goal of the growing interest among economists in matching and market design is to understand the operation of markets, both centralized and decentralized, well enough so we can fix them when they’re broken.

See Also