Matching is generally considered to be an integral part of markets and institutions. The ability to match one market participant to another smoothly, such as a willing buyer to a willing seller, is crucial to a well functioning market. This idea was explored by David Gale and Lloyd Shapley (hereafter GS) in a, now classic, 1962 paper “Collage Admission and the Stability of Marriage’. In this they proposed the ‘deferred acceptance algorithm’, which has contributed greatly to the advancement of ‘Matching theory’. The problem constructed to explain the algorithm was a simple model of two-sided matching, the marriage of a man and a woman. GS proposed that their algorithm resulted in a “stable” matching, in which no man or woman is matched to an unacceptable mate and that no man and woman, who are not paired to each other, would both prefer to be. The process began with one set of agents making proposals in order of preference (men offering marriage proposals) to another set of agents, the receivers (women receiving the proposal). Those agents that receive more than one proposal than accept the most preferred offer and reject the rest. However the acceptance is not immediate and deferred until the end of the algorithm. In the meantime, the process continues until there are no rejected agents who are able to make more proposals. It is only at this point that all proposals held are finally accepted resulting in a matching.
This insight by GS that there existed a process when preferences by agents are strict, there always exists for each side of the market a stable matching that is optimal for agents on each side was ground-breaking. By stable we mean a matching when no set of agents that can organise a matching among themselves that they all prefer and am matching is optimal when for a set of agents if there is no stable matching that all agents in the set prefer. Both properties are seen as extremely desirable within a market and consequently resulted in the application of the deferred acceptance algorithm in several ‘failed’ markets in which matching effectively is problematic. The algorithm has been built upon by Alvin Roth to great effect in both the market for matching new doctors to hospitals and the matching of children to public schools in Boston and New York.
It was first in a 2004 paper “Kidney Exchange” that Roth, along with Tayfun Sӧnmez and M. Utku Ünver, discussed the inefficiency of the existing kidney transplant system in the USA and proposed that a centralised exchange system, using matching theory, could be structured to facilitate the transplantation of many more kidneys than was already possible. They paper emphasised the inefficiency of the current kidney transplant system claiming that ,using data from the United Network for Organ Sharing , there are over 55,000 patients on the waiting list for cadaver kidneys in the USA, of whom 15,000 had been waiting more than three years. Furthermore in 2002 there were over 8,000 transplants of cadaver kidneys performed; while about 3,400 patients died while on the waiting list, and another 900 became too ill to be eligible for transplantation. There were also over 6,000 transplants of kidneys from living donors in the same year, a number that has been increasing annually.
The figures they claimed highlighted the failure of the existing market in kidney exchange because of the substantial shortage in the supply of kidneys, relative to demand. Roth has described this characteristic of a market as a lack of thickness, which is a failure of a market to bring together an ample amount of potential buyers and sellers to produce satisfactory outcomes for both. He claimed that this was due to existing process of if a kidney patient brought forward a donor and testing revealed incompatibly between the two, then the donor was just sent home. No medical record of the donor was kept thus inhibiting the opportunity of a compatible patient receiving that kidney. Thickness along with safety (incentives for agents to reveal confidential information) and overcoming congestion (giving market participant enough time to make satisfactory choices if faced with a variety of alternatives) are the three criteria, Roth claims, which must exist in a market for it to function properly. Moreover when creating a market, all three must be adhered to in order for the market to be sustained over a period of time.
Roth, Sӧnmez and Unver noticed that in a small number of cases, there had been exchanges between two or more incompatible patient-donor pairs. One being a paired exchange, which involved two patient-donor couples for each of whom a transplant within the pair was infeasible but such that the patient in each couple could feasibly receive a transplant from the donor in the other couple. The other being an indirect exchange, this involved an exchange between one incompatible pair and the cadaver queue. In this exchange, the patient in the couple receives high priority on the queue in return for the donation of the pair’s donor’s kidney to someone else in the queue. Both exchange system were declared ethically acceptable and improved the welfare of couples involved.
In the 2004 paper, they built on these concepts and gave consideration into which type of exchange system would prove most efficient. Roth, Sӧnmez and Unver modeled patient-donors pairs as agents and gave them strict preferences over compatible kidneys and allowed exchanges among any number of agents. They excluded list exchange, as used in the “housing market” example of Shapley and Scarf (1974) from Gale’s method of Top Trading Cycles (TTC) which produced efficient, core allocations. They called this set of procedures top trading cycles and chains (TTCC) and identified a version which would be Pareto efficient and incentive compatible.
The distribution of the paper to numerous Kidney surgeons resulted in Roth et al. (2004) convening with Frank Delmonico, the medical director of the New England Organ Bank. The resulting discussion regarding the system proposed in the paper, led to the creation of the New England Program for Kidney Exchange (NEPKE) in 2004. This united the fourteen kidney transplant centers, with regards to data and medical records, in the region to allow incompatible patient-donor pairs to find exchanges with other such pairs.
The discussion between Delmonico and Roth et al (2004) also allowed for some modifications of the original proposals presented in the latter’s paper. To solve one feature of the incentive problem and for other reasons, all surgeries were to be done simultaneously as to avoid complications if part of a patient-donor suddenly became unwilling. A two way exchange between agents would involve four synchronized surgeries, a three way exchange would involve six and so on. Despite evidence suggesting that large exchanges would be infrequent, it posed difficulties to the program. Discussions with surgeons concluded that while two-way exchanges would be feasible, there would be constraints to a three-way exchange or more (due to the difficulty in performing six simultaneous or more surgeries). Therefore it was decided that the New England system’s matching software would initially only attempt to find two-way matches, while keeping record of any potential three-way exchanges the software found.
The extent, to which ‘Matching theory’ has improved the kidney transplant system, since the NPKE’s inauguration, has been huge. Since 2005, the number of Kidney Paired Donations has increased each year with 3 matches/7 transplants in 2006; 4/10 in 2007; 4/9 in 2008; 6/16 in 2009; and 5/12 through May 2010. This has in turn resulted in the number of transplant centers working with NEPKE increasing from 14 to 21 in 2010, with the NPKE running searches for matches every two weeks. Furthermore the success of the program has led to the consideration of a national kidney exchange clearinghouse by the United Network for Organ Sharing (UNOS).
However Roth has stated there further challenges still remain to total kidney exchange, related to thickness, congestion and incentives. To address thickness, progress has been made with the passing of legislation in the US Senate in 2007 to remove potential legal obstacles to a national system. But expanding the market to allow compatible patient-donor pairs to exchange with each other would also help the thickness problem. With regards to congestion, the reduction in the time it takes for the testing of compatibility between patients and donors would aid massively. While the growth in co-operation between transplant centers has resulted in a new incentive issue. This being how the system should be organised to give centers’ incentive to always inform the central exchange of all incompatible patient-donor pairs.
Overall the use of ‘Matching theory’ by Alvin Roth has helped transform the kidney transplant system in the US, specifically New England, by addressing the main problem of a lack of thickness in the market prior to 2004. The designation of a system in which incompatible patient-donor pairs could interact with another pair and result in an efficient market transaction is one example of many, which have shown the growing importance of the field of Market Design, to both consumers and producers across a variety of market interactions.
 National Bureau of Economic Research (2013) NBER Working Group Descriptions: Market Design
 Nobelprize.org (2013) The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012
 Roth, A.E. (2008) Deferred acceptance algorithms: history, theory, practice, and open questions: International Journal of Game Theory
 Gale, D. and L.S. Shapley (1962) “College Admissions and the Stability of Marriage” The American Mathematical Monthly, 69(1): 9-15.
 Roth, A.E. (2007) The Art of Designing Markets: Harvard Business Review, October: 118-126
 Roth, A.E. Sӧnmez, T. and Unver, M.U. (2004) Kidney Exchange: The Quarterly Journal of Economics, May 2005: 457-488
 Roth, A.E. (2007b) What have we learned from Market Design?: National Bureau Of Economic Research, Working Paper 13530
 Roth, A.E. Sӧnmez, T. and Unver, M.U. (2005) A Kidney Exchange Clearinghouse in New England: American Economic Association, May 2005: 376-380
 Al Roth's Game Theory, Experimental Economics, and Market Design Page (2013)