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’[3]. 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[4].
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[5]. 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[6].
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.
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[8]. 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)[9].
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.
References
[1]
[2]
[3]
[4] Gale, D. and L.S. Shapley (1962) “College Admissions and the Stability of Marriage” The American Mathematical Monthly, 69(1): 9-15.
[5] Roth, A.E. (2007) The Art of Designing Markets: Harvard Business Review, October: 118-126
[6]
[7] Roth, A.E. (2007b) What have we learned from Market Design?: National Bureau Of Economic Research, Working Paper 13530
[8]
