Matching mechanisms in theory and practice

TABLE OF CONTENTS

ABSTRACT

ACKNOWLEDGEMENTS

1. INTRODUCTION

2. PRACTICAL PROBLEMS
2.1 Coordination and market failures
2.1.1 The labor market for medical interns
2.1.2 School choice
2.1.2.1 The New York City (NYC) High School Match
2.1.2.2 The Boston Public School Match (BPS)
2.2. Double coincidence of wants: kidney exchange

3. THEORETICAL FRAMEWORK
3.1 The marriage problem
3.1.1 A hypothetical model of the marriage market
3.1.2 Important matching properties
3.2 Gale-Shapley (GS) deferred-acceptance algorithm
3.2.1 A formal description of the assignment mechanism
3.2.2 Weak optimality of the GS stable matching algorithm
3.3 Alternative matching mechanisms
3.3.1 Top trading cycles mechanism
3.3.2 Priority mechanisms
3.3.3 Linear programming mechanism

4. INCENTIVES AND STRATEGIC BEHAVIOUR
4.1 Dominant strategies
4.1.1 Definitions and terminology
4.1.2 Stability and incentives
4.1.3 Strategy choice under incomplete information
4.2 Practical implications of stability and strategy-proofness
4.2.1 Relative performance of matching algorithms in laboratory experiments
4.2.2 Strategy-proofness of the Gale-Shapley algorithm: a fictitious example

5. CONCLUSIONS

REFERENCES

APPENDIX
A.1 Algorithms (own source)
A.1.1 Gale-Shapley algorithm (GS)
A.1.2 Top trading cycles algorithm (TTC)
A.1.3 Boston priority algorithm (BOS)

ABSTRACT

Matching is the part of economics that deals with the question of who gets what, e.g. who gets which jobs, who goes to which university, who receives which organ or who marries whom. During the second part of the last century, many markets have been discovered to have failed in providing the necessary conditions for efficient matches. These market failures have partly evolved on ethical or institutional grounds, but are more generally attributed to congestion or coordination problems caused by the inability of the market to make it safe for participants to act on their private information. For this reason, a variety of allocation mechanisms have been developed and subsequently tested in field and laboratory experiments for possible implementation in real-world applications.

This work attempts at giving a condensed review of different matching mechanisms and the performance of algorithms that have been implemented for solving the problems in their respective environments. The theoretical properties of these mechanisms as described in the increasingly vast literature on matching design will be used as a benchmark to compare their relative performance in terms of overall efficiency. The results yield some basic insights in the varying success of the competing algorithms in practice, indicating that both the quality of theoretical predictions and the actual performance of the algorithms decrease with the complexity of market environments. In particular, they show that imperfections of markets such as information asymmetry and incentive problems can have far-reaching consequences with respect to the effective working of matching procedures.

ACKNOWLEDGEMENTS

The author is indebted to Prof. Alvin E. Roth, Department of Economics, Harvard University, and Prof. M. Utku Ünver, Department of Economics, Boston College, for nicely providing academic papers and giving expert advice. I would also express thanks to Donja Darai, research assistant at the chair of Prof. Armin Schmutzler, Socioeconomic Institute of the University of Zurich, for supervising this work.

1. INTRODUCTION

Matching is an important function of markets that focuses on the allocation of scarce goods to individuals or of individuals to institutions. While it is inherently difficult to find the optimal way of allocating heterogeneous and indivisible objects to individuals with varying preferences and needs, matching processes can be further complicated by political or ethical constraints. In modern markets, money is predominantly used as a medium of compensation which allows the efficient allocation of goods through the signaling effect of market prices (Roth, 2007). Nevertheless, monetary exchange can be illegal on ethical and institutional grounds, involving the consideration of alternative allocation mechanisms. Examples of this sort abound in various important environments such as political decisions, public school choice or organ donations, all of which are predominantly arranged without monetary transfers. In these markets, difficulties arise of finding a “double coincidence of wants”, which have been experienced in prehistoric barter economies due to the absence of an efficient means of exchange such as money. As a consequence, the opportunities for mutually beneficial transactions are drastically reduced with growing size and complexity of the market, leading thus to the failure of the market to produce efficient matches (Roth et al., 2007).

According to Niederle et al. (2008), three categories of market failure can be distinguished:

(1) Lack of thickness, i.e. the inability of the market to pool a sufficient number of buyers and sellers for carrying out transactions;
(2) Congestion problems arising when market thickness prevents transactions from taking place^[1]. Put another way, market participants are not given enough time to consider enough possible alternatives for arriving at a satisfactory transaction.
(3) Failure to overcome the uncertainty that precludes market participants from reliably revealing their private information or effectively acting on their preferences.

The first approach to solve these matching problems was in use since 1951 by means of an algorithm that had been developed for the assignment of medical interns to hospitals in the United States (Schummer & Vohra, 2007). However, the major breakthrough came with the remarkable paper “College Admissions and the Stability of Marriage” by David Gale and Lloyd Shapley in 1962, in which they proposed a formal solution to the two-sided matching problem. For this purpose, Gale & Shapley (1962) introduced an algorithm for finding a “stable” matching, in which no agent is ever matched to an unacceptable partner and no two agents on opposing sides of the market who are not matched to each other would both prefer to be (Roth, 2008). Since then, there has been growing literature about matching mechanisms in theory and practice regarding also the optimal design of one-sided and hybrid markets, respectively.

The design of matching markets emerges as an important part of economics, which evolves from the study of possible reasons for the failure of a number of both centralized and decentralized market organizations in the past^[2]. In the context of market design, a vast majority of failed market institutions has been successfully reorganized by relying on distinct versions of the stable Gale-Shapley algorithm adapted to their respective environments. In most cases, these centralized clearinghouses allow for a substantial improvement not only in the coordination between individuals and institutions, but also in the effective allocation of objects to individuals. Hence, the rate of efficient assignments of interns to hospitals, students to schools and kidney transplants to patients has significantly increased in the last decades (Niederle et al., 2008)

The present work compares different matching mechanisms in terms of both their theoretical advantages and their actual performance in real-world applications of matching problems. It is organized as follows: Chapter 2 evaluates the difficulties that arise in some practical environments of matching mechanisms after their implementation. By describing the development of an efficient market for kidney exchange as well as some effectively implemented solutions to school choice problems, progress is highlighted which has been made so far. Chapter 3 provides a short overview on the theoretical properties of the most widely used matching mechanisms by focusing on one-to-one matching environments in two­sided markets. Chapter 4 resumes by analyzing the strategic behavior of agents and their potential incentives to circumvent the centralized matching procedure. Finally, the Pareto- efficiency of the described matching mechanisms is evaluated by introducing a fictitious example in a simple environment, which examines the robustness of each algorithm to some arbitrary deviation of an agent from her theoretically supported strategy. Chapter 5 concludes by summarizing the results and trying an outlook on potentially useful applications of matching mechanisms in future.

2. PRACTICAL PROBLEMS

2.1 Coordination and market failures

2.1.1 The labor market for medical interns

There is a wide range of real-world applications of practical matching problems, many of which have been investigated in laboratory studies (Chen & Sönmez, 2006). The first well- known applications of matching mechanisms in practice trace back to the National Resident Matching Program (NRMP) in the United States and the markets for entry-level physicians in various regions of the British National Health Service. The internship is an optional form of postgraduate medical education that offers students a focused insight into clinical medicine, while constituting an attractive supply of relatively cheap labor for hospitals (Roth, 1984a). For this reason, competition among hospitals for new interns grew considerable starting from the first introduction of the internship in 1990 until around 1945, and hospitals began to engage in a race to sign employment contracts with medical students as early as possible. This caused a steady advancement of the appointment date that was costly both for hospitals and students: while hospitals were forced to appoint medical interns without knowing their final grades, students found themselves bothered with the need for premature decisions regarding desirable appointments. In theoretical economy, this situation may be modeled as a multiple- agent Prisoner's Dilemma since all hospitals actually preferred a later appointment date compared with that resulting under the competitive behavior of hospitals. Faced with the negative externality produced on part of these inefficiencies, medical schools collectively intervened by fixing the appointment date to a point before which they would not release any information about their students (Roth, 1984a). Despite the standardization of the appointment dates in 1945, agents on both sides of the market still had an incentive to wait until the last minute in the hope of eventually being offered a more preferable position. However, students who ultimately received their preferable position were unhappy if they had already accepted an early offer under pressure, whereas hospitals whose candidates rejected them in the last minute were unhappy if their preferred waiting-list candidates had already accepted another position (Roth, 1991). Despite various attempts were made to resolve this inconvenience primarily by shortening the time during which students had to decide about accepting or rejecting offers, the market remained chaotic in the years 1945-1951. Only by the time it was recognized that the serious problems in the last stage of the matching process could not been resolved by compressing them into an ever shorter time period, a centralized clearinghouse was successfully proposed in 1952 (Roth & Sotomayor, 1990). The substitution of the chaotic last-minute recontracting process by a centralized matching procedure led to a high rate of voluntary participation, which induced about 95% of the students to be offered and ultimately accept the positions they were matched with. Despite minor complications that arose with a growing number of married couples obtaining positions outside of the centralized match in the late 1970s, overall participation rates have been kept on a high level, and the centralized market is still in operation (Roth, 1990).

In various regions of the British National Health Service, the decentralized markets for new physicians at the same time encountered very similar problems. These markets experienced “unraveling” of hiring decisions to one and a half years ahead of graduation or employment of medical students in the late 1960s (Kagel & Roth, 2000). Motivated by the U.S. example, the introduction of centralized matching procedures based on pre-registration rules was recommended by a Royal Commission on Medical Education from 1965-68. Employers and employees still contacted each other in a decentralized way, with students ranking the hospital programs they had applied to in order of their preferences^[3], and hospitals similarly ranking the applicants after the interviews. These preference rankings were then submitted to a central clearinghouse that arranged an assignment of students to hospitals and finally informed the parties on both sides of the result (Roth & Sotomayor, 1990). Although the procedures themselves were roughly uniform as in the U.S. experience, the algorithms implemented to determine the matchings from submitted preference rankings differed across the various regions. Roth (1990) identifies eight matching schemes in the British market that can be analyzed in terms of their stability. Two of them are stable algorithms since they always produce stable outcomes, but the six remaining schemes are unstable in the sense that they will produce instabilities for certain preference sets. Whereas both of the stable matching algorithms succeeded in halting the unraveling of appointment dates, four of the six unstable algorithms have been abandoned (Roth, 1991). Despite the relatively small sample size, this is a strong indication of the relationship between stability and the survival of matching algorithms. This relationship has been proposed beforehand by the “stability hypothesis” of Roth (1984a), which states that unstable algorithms may cause incentives for both students and consultants^[4] to circumvent the formal match by coordinating with each other before participating into the centralized clearinghouse. The hypothesis maintains that the most common form of unstable matching algorithms, which tries to make as many first priority matches of students with hospital positions as possible, would be particularly prone to failure (Kagel & Roth, 2000). In fact, in each region of the National Health Service where mutual assignments between students and hospitals were made by defining a priority for each match, the centralized clearinghouses thus organized were all abandoned. This is surprising at first sight because participation in the centralized clearinghouse is compulsory and students have to abide by the final outcome produced by the matching algorithm in the United Kingdom (Roth, 1991). All the same, some students and consultants seemed to anticipate and act on the instabilities that may occur under the unstable matching scheme. In particular, students who were unlucky with their first match experienced in this way were likely to prearrange their matches before participating in the formal application process next year. This worked to the disadvantage of both students and hospitals that were unable to realize their mutual interests in becoming matched with each other. These unstable matching schemes were abandoned primarily due to the vulnerability and subsequent failure of the underlying priority mechanisms. For example, the Newcastle scheme was abandoned in 1981 when 80 percent of overall submitted preferences merely exhibited a first choice, which indicated that matches had been effectively arranged in advance (Kagel & Roth, 2000). As a remedy, the abandoned schemes were partially substituted by stable matching algorithms based on the deferred- acceptance mechanism by Gale & Shapley (1962). After having been adapted to local market conditions, these matching algorithms were successful in halting the unraveling and thus remain in use similarly to their stable counterparts in the United States.

2.1.2 School choice

In many countries, the public school system has been a monopoly for centuries, which was designed by a democratic bureaucracy for satisfying the goals of legislatures and educational institutions (Smith & Meier, 1999). Following the American economist Milton Friedman (1955) who had first opened the debate on school choice, policy makers in different nations such as France, Canada, Great Britain, Chile and the United States recognized the growing need for educational reforms. The term school choice describes a variety of programs directed at “giving parents the power and opportunity to choose the school their child will attend” (Center for Education Reform, 2009). Under the traditional schooling system, children are assigned to public schools by the district where they live, irrespective of the school desirability or quality for the children. Although in principle there are many private alternatives to public choice available, only about 10% of parents afford to choose that option in the United States depending on their wealth (Schneider et al., 1997). School choice policies are thus designed to improve the quality of education by expanding choice particularly for parents without such means, allowing them to select schools also outside their residential districts. Advocates of school choice claim that public schools should be granted autonomy to the extent that they would be free to meet the educational demands of students and their parents. From their point of view, governments should imitate private markets by giving parents better information about options they should have over the public schooling services. These market-like reforms are aimed at treating parents and students like customers by increasing voluntary involvement of parents in their children's education. However, there is little consensus among scholars about how the anticipated change in the behavior of school choice agents would affect the formation of social capital and educational welfare in general (Smith & Meier, 1999).

Probably the most important concerns of school choice ensue from the fact that it is impossible to assign each student to her top choice school. As a consequence, the design of a rigorous student assignment mechanism has become a central issue in the educational literature. Since many of the real-life school choice programs lack explicit procedures, they suffer from selective interpretation and evasive action by students and their parents. Despite being rigorous, such procedures may still suffer from serious shortcomings e.g. by causing students with high priorities at certain schools to lose their priorities unless they list these schools at the top (Abdulkadiroglu & Sönmez, 2003). Moreover, these procedures may give agents incentives to manipulate the outcome of the student assignment mechanism by misrepresenting their true preferences. Strategically sophisticated behavior on part of some students and their parents is confusing to less sophisticated agents who rely themselves on truthful preference revelation, which often leads to an inefficient allocation of school seats.

The school choice problem is closely related to other real-life applications such as the assignment of dormitory rooms or on-campus housing facilities to students (Hylland & Zeckhauser, 1979, Abdulkadiroglu & Sönmez, 1998). However, these problems can be solved by a popularly used design mechanism known as Random Serial Dictatorship (RSD). This mechanism first orders the students with a lottery and then assigns the first student her top choice, the next student her top choice among the remaining school seats, and so on. In contrast, with school choice the priority ordering of a student is determined rather by state and local laws than selected on a random basis. For example, students living in the attendance area of a school and siblings of students already attending a school must be given priority at that school (Abdulkadiroglu & Sönmez, 2003). Thus a mechanism other than RSD, which is to produce efficient outcomes when students are given different priorities at different schools, must be applied to school choice. In the mechanisms design literature, this flexibility requirement is often encountered in context with the related college admissions problem (Gale & Shapley, 1962). The key difference between college admission and school choice is that in the latter schools are merely “objects” to be consumed by the students, whereas in college admissions, schools behave like agents having preferences over the students. However, the distinctive features of school choice can be bypassed when school priorities are simply treated as school preferences, hence enabling the design of an appealing student assignment mechanism based on the college admissions approach. As noted in the previous section, this category of models has been successfully applied in the organization of the U.S. and British entry-level markets (Roth, 1991). In the following, two separate cases of practical market design are presented with respect to the important difference between school choice and the college admissions approach.

2.1.2.1 The New York City (NYC) High School Match

New York City provides education for over a million of students and is thus the largest public school system in the country (Abdulkadiroglu et al., 2005a). Until recently, the school system consisted of over 30 community districts, and students were allowed to apply for a maximum of five out of more than 500 programs^[5]. Schools had restricted autonomy to decide whether to accept their applicants, place them on a waiting list, or reject them. Applicants were then informed about the decisions of their listed schools and required to accept at most one offer and one wait-list. This procedure was repeated twice with the result that students who were still unassigned after the third step were either assigned to schools in their residential area or allocated through an administrative process. In fact, 30'000 out of almost 100'000 students were left without being assigned a school of their choice, because the number of offers and acceptances made during the application process did not suffice to clear the market. Students and their parents who realized that this process was vulnerable to congestion had to behave in a strategically sophisticated manner. In particular, students who ran a substantial risk of being rejected by their first-choice school might have done better to play safe and list one of their lower-choice schools for which they had higher priority. Moreover, numerous schools seemed to conceal capacity from the administration for places to be filled later with students they preferred. When the New York City Department of Education (NYCDOE) recognized that the procedure was affected by serious inefficiencies resulting from strategic behavior of both students and schools, it decided to introduce a new matching system (Abdulkadiroglu et al., 2005a). Since NYC schools withholding capacity were strategic players similar to students, they represented a two-sided market in which both students and schools have preferences above each other. Therefore, it was most appropriate to implement a stable assignment mechanism because this would eliminate strategic incentives on both sides of the market. The medical match discussed in Roth (1984a, 1991) employs an applicant-proposing deferred- acceptance algorithm, which satisfies the stability requirement in the sense that no school and student not matched to one another would both prefer to be (Gale & Shapley, 1962). Based on the previous experience with the medical match, NYCDOE selected a student-proposing deferred-acceptance algorithm, which gives students straightforward incentives to state their true preferences and is thus best for their welfare. The application procedure was further improved by allowing students to rank 12 instead of five choices, and by abandoning the possibility of some students receiving multiple offers at the expense of leaving other students without a single offer (Abdulkadiroglu et al., 2005a). The implementation of the new matching scheme in the years 2003-2004 proved to be rather successful as the number of students who were matched to a school on their initial choice list increased by more than 20’000 or about 38% compared to the previous year (NYCDOE, 2004). In addition, nearly one third of students having applied for the admissions process received their stated first choice in the first year of operation, which corresponds to an increase of nearly 30%.

2.1.2.2 The Boston Public School Match (BPS)

Unlike with NYC schools, the student priorities of public schools in Boston are set by a central administration. As a consequence, students are allocated to over-demanded school seats by a system of priorities with the goal of giving as many students as possible their first- choice school (Abdulkadiroglu et al., 2005b). First in priority are students who have older siblings already attending a specific school, and second priority is given to students who live in the walking distance of the school. Further priorities are assigned via a lottery generating random numbers once for each student. Since most popular schools would be filled in the first round of the assignment process, students who fail to get their first choice are likely to be crowded out of their secondary choices. This induces many parents to “game” the system by lying about their first choice because ranking a less desirable school first will increase the chances of getting a slot there (Cook, 2003). The old Boston mechanism belongs to the class of most common matching techniques called priority mechanisms which are traditionally applied in school choice. It works as follows:

Step 1.- Each school considers the students who ranked it as their first choice and assigns seats in order of the student’s priority at that school until either the school is filled up or all the first-choice assignments are made.

Step k.- Each school with still available seats considers the remaining students who ranked it as their kth choice and assigns seats in order of the students’ priority at that school until either the school is filled up or all the kth choice assignments are made.

The procedure terminates when all the students are assigned a spot or no more submitted choices are left unconsidered. Students who remain without assignments at the end of the procedure are assigned to the closest school that still has available spots. Strategic behavior under this class of matching procedures is motivated by the fact that students once assigned to their first-choice places cannot be displaced by other students even if they have higher priority (Abdulkadiroglu et al., 2005b). Ranking an over-demanded first-choice school at the top is thus costly for a student unless her priority there is high enough for getting the match^[6].

However, the persistent uncertainty and frustration of parents with school choice plans will possibly be eliminated by making it a dominant strategy for students and their parents to state preferences truthfully in the application procedure. This can be achieved by implementing a student-proposing deferred-acceptance algorithm of the sort which has recently been adopted by NYC high schools (Abdulkadiroglu et al., 2005a):

Step 1.- After each student has “proposed” to her first choice, each school tentatively assigns its seats to its proposers one at a time following their priority ordering at that school. Any remaining proposers are rejected.

Step k.- After each student who was rejected in the previous step has “proposed” to her next remaining choice, each school considers the students it has been holding together with its new proposers and tentatively assigns its seats to those students in order of priority. Again, any remaining proposers are rejected.

Because the assignments made in each step of the deferred-acceptance algorithm are only temporary, students with higher priorities may be considered in subsequent steps. Hence, no student will run the risk of losing a seat to a lower-priority student while receiving a less preferred assignment. This important characteristic of the deferred-acceptance algorithm, which is also known as stability condition studied first by Gale & Shapley (1962), is the critical difference to the old Boston mechanism. Moreover, the outcomes produced by the student-optimal stable mechanism are preferred to any other stable matching, which implies that this mechanism is dominant-strategy incentive-compatible^[7] (Roth, 1982). However, there may be unstable matchings that are Pareto superior to the matchings produced by the Gale- Shapley stable assignment algorithm. This implies a trade-off between stability and Pareto- optimality on a one-sided market like BPS where schools are passive “objects” to be consumed by the students and priorities are set by a central administration. Therefore, it might be appealing just to maximize the welfare of students by allowing them to trade their priorities at different schools in return for getting a preferable school seat (Abdulkadiroglu et al., 2005b). Such a virtual exchange of priorities would be achieved through applying an extended version of Gale’s “top trading cycles mechanism” ^[8].described in Shapley & Scarf (1974). Even though the top trading cycles (TTC) mechanism and its versions are also Pareto-efficient and strategy-proof in a moderately simple environment, it suffers from a major drawback. Namely, the TTC mechanism is unstable with respect to the college admissions problem, meaning that students may be unwilling to abide with their final assignment. In contrast, the Gale-Shapley stable assignment mechanism produces only stable matchings and thus eliminates justified-envy in the context of school choice (Abdulkadiroglu & Sönmez, 2003). Students who are dissatisfied with their final match as produced by the TTC algorithm may try to appeal against the status quo in the hope of being assigned a preferable slot through an appropriate downstream decision. In late 2003, the Boston School Committee started to evaluate the computerized process used for student assignment and compared the two alternative mechanisms regarding their potential to reduce preference manipulation under the old system (Abdulkadiroglu et al., 2005b). Since stability has become a crucial issue in the recent debate on school choice policies, the Boston School Committee voted to replace the existing priority mechanism through a locally adapted version of the stable Gale-Shapley algorithm. The new matching procedure, which has been overwhelmingly supported by economists, came into operation in the school year 2006-2007 (Abdulkadiroglu et al., 2006).

2.2. Double coincidence of wants: kidney exchange

Two-sided matching mechanisms have provided an attractive opportunity to enable mutually beneficial transfers of commodities for which there exists no appropriate means of exchange. Modern economies usually rely on money as an efficient means of exchange leading to a socially desirable allocation of goods. The underlying price mechanism has a signaling effect that conveys the necessary information about the characteristics of the good from the seller to the buyer. However, in some countries the commercial sale and purchase of certain goods is forbidden by the state or a legal authority on ethical grounds.

This is most apparently the case with bodily commodities such as live organs for which no market exists because a monetary and objective valuation of these commodities is morally disputable or even impossible. Indeed, the purchase and selling of human organs was declared felony under the National Organ Transplant Act (NOTA) of 1984, and the Uniform Anatomical Gift Act of 1987 in the United States (Roth et al., 2004). The legal restriction on access to organs has developed into a serious problem for patients suffering under End Stage Renal Disease (ESRD). This is a disease which becomes fatal unless it is treated with dialysis or kidney transplantation, the latter being the preferred treatment. The feasibility and success of kidney transplantation critically depends on two genetic characteristics, namely the ABO blood-type and the human lymphocyte antigen (HLA) type (Delmonico, 2004).

There are four blood types: A, B, AB and O. Basically, whereas type O kidneys can be transplanted into any patient, type AB kidneys can only be transplanted into the same blood- type patients. Both, type A and type B kidneys can be transplanted into either the same blood- type patients or type AB patients. As a consequence, type O patients can only receive kidneys from type O donors. Even in the absence of blood-type complications however, the feasibility of kidney transplantation can be restricted by incompatible HLA types. Since HLA is a combination of six proteins, there are different degrees of HLA mismatch between the donor and the recipient of a graft (i.e., transplanted organ). The likelihood of graft survival decreases with the degree of HLA mismatch. Prior to transplantation, the recipient is therefore tested for the presence of antibodies against HLA in the donor’s kidney. A positive crossmatch test is commonly regarded as a contraindication, which effectively rules out transplantation (Gruessner & Benedetti, 2007).

Traditionally, the first option for a patient is to identify a healthy willing donor such as a relative or a spouse in order to arrange a live transplant. If the transplant is not feasible due to immunological incompatibilities, the patient usually enters a waiting list, while the donor is sent home (Roth et al., 2004). As a consequence, most patients end on the queue for receiving a kidney transplant from a deceased donor. The number of patients on the waiting list of the United Network for Organ Sharing (UNOS) has therefore steadily increased from roughly 20’000 to over 65’000 between 1990 and 2005 (Fig. 1). Longer waiting times imply both greater morbidity and mortality of patients on the queue for a cadaveric kidney, thereby reducing the proportion of successful cadaveric transplants relative to transplants from live donors (Stegall et al., 2004). To counteract this problem, theoretical economists began to look for a suitable remedy to increase the opportunity of live donation towards the turn of the century. Live donation is an option for healthy people who have two functioning kidneys and can remain healthy with one (Roth et al., 2005a). This opportunity is also attractive from a practical point of view, because kidneys from live donors have a survival rate that lasts on average nearly twice as long as that from cadaveric grafts (Haederle, 2009).

illustration not visible in this excerpt

Figure 1: Number of live kidney transplants, total number of kidney transplants and number of persons on the waiting list for a cadaveric kidney (Source: Becker & Elias, 2002).

Two additional possibilities to improve the welfare of incompatible patient-donor pairs and the patients on the queue have been identified by Roth et al. (2004), known as paired kidney exchange and indirect exchange. The first method is based on two patient-donor couples, for each of whom the donor is biologically incompatible with the intended recipient, but such that a crosswise transplant from the donor in each couple to the patient in the other couple is medically feasible (Roth et al., 2005b). Conversely, the indirect or list exchange involves a live donation from an incompatible patient-donor couple to the cadaver queue in return for the patient in the couple receiving high priority on the queue (Zenios et al., 2001). While the standard priority for wait-list candidates is determined by a point system including factors such as blood-type, HLA antigen-match, the time spent on the waiting list and region where the kidney is harvested, high priority can be implemented by awarding the intended recipient an appropriate number of bonus points (Roth et al., 2004). The list exchange increases not only the kidney supply by an additional live donation, but also the welfare of both the patient in the couple and the recipient of the live kidney compared with having longer waiting times for a suitable cadaver transplant. However, list exchanges have been partly objected on account of the harm that they cause to blood-type O candidates, whose welfare would be negatively affected due to prolonged waiting times on the queue (Ross & Zenios, 2004).

There is no such disadvantage with paired kidney exchange, which not only improves the welfare of the intended recipients in the couples, but also of other patients on the queue by relieving the demand on cadaveric kidney supply. However, paired kidney exchange requires that all surgeries are conducted simultaneously because the incentives for a donor to donate a kidney might disappear once her intended recipient left the surgery with a new transplant (Roth et al., 2005a). Thus, a simple two-way exchange involving two patient-donor pairs requires four simultaneous surgeries. In the more complicated case of three-way exchanges, the donor in one couple gives his kidney to the patient in the second couple, whose donor kidney is transplanted into the patient in a third couple, whose donor kidney goes again to the first couple. However, as logistic constraints increase proportionally with scale, three-way exchanges already involve six surgeries to be carried out simultaneously. According to simulation results by Roth et al. (2004), there would be substantial welfare gains from larger scale exchanges due to an increased number of feasible live donations. But these benefits have to be compared with the substantial costs arising from the need to solve the incentive problem.

Of course, the need for appropriate incentives strictly depends on the donor’s preferences. Some donors may only want to donate a kidney to a person close to them, such as their relatives, spouse or friend. Recently however, the benefits of recruiting potentially altruistic donors, who have no connection with the intended recipient, have been considered both for paired and indirect exchanges (Haederle, 2009). In 2006, the Alliance for Paired Donation reported the first nonsimultaneous, extended altruistic-donor (NEAD) chain that has accomplished a length of 10 patients meanwhile. A NEAD chain is initiated by an altruistic (i.e. undirected) volunteer, who donates his kidney to the patient in an incompatible patient­donor pair, whose donor kidney goes to the patient in the next pair, and so on (Gordon, 2009). According to Rees et al. (2009), the chain eventually terminates when the donor kidney in the last incompatible patient-donor pair is donated to an unmatched recipient on the cadaveric waiting list. Nondirected donations may shorten the waiting times of unmatched candidates on the wait list for deceased-donor kidneys and therefore improve the welfare of patients without any potential donors. Moreover, donor chains allow for greater flexibility because not all surgeries must be performed simultaneously in the same hospitals. Presently, about one-third of the 14’000 transplantations annually performed in the U.S. are attributed to nondirected donations from suitable live donors (Hayward, 2009).

During the last years, the UNOS has started several pilot projects to establish efficient kidney exchange systems in different regions of the US. The first and most elaborated of these projects is the New England Program for Kidney Exchange (NEPKE), which was founded in 2004 through the collaboration between the kidney transplant centers of New England and the New England Organ Bank^[9]. NEPKE was formed with the goal to optimize live donor kidney exchanges by combining a database of incompatible patient-donor pairs with a computerized matching program designed by the economists Alvin Roth from the Harvard Business School, Tayfun Sönmez from Boston College and Utku Ünver from the University of Pittsburgh, respectively (NSF, 2005). The program maximizes the number of achievable transplants by searching the database for possible donor-recipient pairings who may be compatible. Prior to the assembly of massive computer databases as initiated in New England from 2005, only five kidney exchanges were reported to have been performed in the 14 regional transplant centers (Roth et al., 2005a). Meanwhile, the computerized donor tracking system has developed into a kidney exchange clearinghouse, such that the different kinds of exchanges are efficiently organized. A clearinghouse helps to elicit the information needed for efficient allocation of all participants in the exchange program, thereby overcoming the incentive problems that are typical for decentralized markets (Roth et al., 2007). As noted by Roth & Ünver (2008), the success of a national clearinghouse for paired donations would depend on its capacity to attract the participation of both the transplant centers and potentially incompatible patient­donor pairs.

The idea of establishing a national kidney exchange clearinghouse traces back to the “roommate problem” investigated by Abdulkadiroglu & Sönmez (1999). They refer to the original study of markets with indivisible goods by Shapley and Scarf (1974), who modeled a Barter economy with n agents, where each agent owns a house and trade is only feasible in houses. In the “housing market” of Shapley and Scarf (1974), the houses are a collectively owned good that has to be distributed among the agents by using the Pareto-efficient TTC mechanism, which is also individually rational and strategy-proof^[10]. On the other hand, the “housing allocation problem” introduced by Hylland and Zeckhauser (1979) refers to the situation where there exists an initial distribution of privately owned houses becoming available for reallocation. In this case, the TTC algorithm reduces to a well-known real-life mechanism called random serial dictatorship (Abdulkadiroglu & Sönmez, 2003). When preferences are strict, random serial dictatorship produces efficient outcomes provided that the market only consists of empty houses and newcomers wishing to rent a house. However, there may be mixed cases with newcomers, vacant houses and houses already occupied by existing tenants. As with the “housing market” of Shapley and Scarf (1974), existing tenants may lack the incentives to participate in a centralized market procedure, because this would require them to give up their house without being guaranteed to get a house that is at least as good as their own. These participation constraints prevent the agents from exhausting the possible gains from trade, which implies that the outcome produced by the random serial dictatorship will no longer be Pareto-efficient for at least some random priority orderings. In order to bypass the major deficiency of this real-life mechanism, Abdulkadiroglu and Sönmez (1999) proposed a more generalized form of the TTC algorithm that they called you request my hose -1 get your turn (YRMH-IGYT). Their study is based on a university campus environment, where a set of rooms is allocated to a set of students by a centralized housing office. Some of the students are existing tenants who already occupy a room, and the others are newcomers applying for a vacant room. For any given set of strict preferences of the students over the rooms, a random ordering of students is chosen by a lottery. The mechanism proceeds as follows: The first student is assigned his top choice, the second student his top choice among the remaining rooms, and so on. As long as only vacant rooms are requested by the agents, the procedure works exactly like the random serial dictatorship producing efficient outcomes on a market without existing tenants (Abdulkadiroglu & Sönmez, 1998). However, when someone requests the room of an existing tenant who is yet unassigned, the remainder of the ordering is modified by moving the existing tenant to the top of the line (right in front of the requester), and the procedure goes on. According to Abdulkadiroglu & Sönmez (1999), the outcome of the YRMH-IGYT will be fully equivalent to the matching that is produced by the top trading cycles mechanism from random ordering.

Based on the YRMH-IGYT algorithm, Roth et al. (2004) developed a modified version of the TTC mechanism that can be applied to the kidney transplant environment. Here, the existing tenants correspond to the patients with donors, the newcomers to the patients without donors, and the vacant rooms to the cadaver kidneys not being tied to any specific patient. Each incompatible patient-donor pair represents an agent with strict preferences over other agents based on blood and tissue compatibility, age of donor, and the patient’s priority on the cadaveric wait-list (Roth et al., 2005a). Considering only live exchange between incompatible patient-donor pairs, this problem reduces to the “housing market” of Shapley and Scarf (1974). If however list exchange is included, the TTC method described by David Gale may be insufficient for achieving efficient kidney exchange because the cycles are likely to be replaced by corresponding “w-chains” at some point of the TTC procedure. Consequently, Roth et al. (2004) invented a new class of procedures called top trading cycles and chains (TTCC), which they identified to be Pareto-efficient and strategy-proof (Fig. 2).

Up to date, the overall number of patients on the waiting lists for receiving a kidney transplant in the United States amounts to roughly 80’000^[11]. Though much progress towards efficient kidney exchange has been made in recent years, some aspects that are typical of a barter economy seem to have survived the technological innovations of the kidney exchange system. The relevant deficiency affecting the market for kidneys in this context is the need for a “coincidence of wants”, which occurs due to the fact that the agents are far from being perfectly informed about each other’s preferences and compatibility. A kidney clearinghouse may significantly ameliorate this problem by establishing a market that is sufficiently thick for the successful identification of double and triple coincidences of wants (Roth et al., 2007). Therefore, the authors advocate the organization of a centralized clearinghouse by using national databases for achieving the maximum number of feasible kidney transplants. However, the status quo has been attacked by some popular economists such as Nobel laureate Gary S. Becker who have brought forward arguments in favor of a market for organs. Becker and Elias (2002) suggest that the considerable shortage of both cadaveric and live organs would be substantially alleviated by allowing the financial remuneration of the respective organ donations. Although the main stream of doctors and scientists still objects commercial trading of organs^[12], the opening of a market for kidney exchange will remain a widely discussed subject in the future.

[...]

^[1] This kind of market failure is closely connected to the costly problem of unraveling that has been experienced by labor markets in which offers are made increasingly early and occur dispersed within a more and more compressed time period (Roth, 1984a).

^[2] Provided that money can be used as a means of exchange, a market failure can be defined by the inability of the market to clear through the traditional adjustment of prices and wages.

^[3] As is typical for internship applications, preferences of medical school graduates were rather influenced by the reputation of hospitals then by the salaries offered for these positions.

^[4] Senior physicians and surgeons called consultants are responsible for supervising the filling of the positions, which belong to the health service rather than to the hospital itself (Roth, 1991).

^[5] For a detailed description of the NYC school programs, see Abdulkadiroglu et al. (2005a).

^[6] Moreover, listing an over-demanded school second is a strategic mistake because this means simply giving away that choice at the additional expense of reducing the probability of getting any lower listed choice (Abdulkadiroglu et al., 2006).

^[7] “Dominant-strategy incentive compatibility” is synonymously used with “strategy-proofness” to denote the feature of giving the students straightforward incentives to reveal their true preferences.

^[8] The top trading cycles mechanism and its working will be discussed in Sect. 3.3.1

^[9] Source: NEPKE, found the 29 May 2009 on https://www.nepke.org/about.htm

^[10] Truthful preference revelation is a dominant strategy under any strategy-proof mechanism when agents have strict preferences (Roth, 1982).

^[11] Source: UNOS, found the 29 May 2009 on http://www.unos.org/data/default.asp?displayType=usData

^[12] See for example Roth (2007).