Matching Markets under Distributional Constraints: Theory and Practical Design
This article focuses on one branch of market design, matching theory. Matching theory studies matching two types of agents, as well as matching (allocating) objects to agents. The theory has been applied to match medical residents to hospital residency programs, to place students to public schools, and to match kidney disease patients to kidney donors. The significance of these works has been recognized in 2012, as the Nobel prize in economics was awarded to Alvin E. Roth and Lloyd Shapley, two of the pioneers of matching theory and its applications to practical market design.
In market design, an emphasis is often placed on attention to details (see Roth Econometrica 2003, for example). Experience with design suggests that the standard theory is a useful guide, but specific features of a market often make it impossible to apply the theory directly. Need accommodate specific features often suggests generalizing or modifying theory appropriately. In this article, I will focus on one such feature, namely a "distributional constraints," following the author's works (Kamada and Kojima 2013 mimeo, 2012 AER Papers and Proceedings).
Although absent in the standard matching theory, many matching markets are subject to distributional constraints. In medical residency, for instance, there is often a concern that certain medical specialties attract too many applicants while others do not attract enough (in the U.S., there is a so-called R.O.A.D. to success -R for radiology, O for ophthalmology, A for anesthesiology, and D for dermatology-, which are very popular among medical students, while other specialties such as family medicine often suffer from shortage). Out of this concern, regulations on the number of doctors in certain specialties are imposed or proposed around the world. Constraints may exist in public schools, in which multiple school programs share one building, so there is a bound on the total number of students in these programs in addition to each program's capacity. School districts often try to regulate socioeconomic balance of student body, which is yet another form of distributional constraint.
One concrete example of distributional constraints is found in the matching market for Japanese medical residents. In 2008, the Japanese government introduced a "regional cap" in the matching market. This is a regulation that, for each of the 47 prefectures comprising the country, restricts the number of residents assigned in residency programs within the prefecture. The purpose of this policy is to regulate the geographical distribution of doctors, which would otherwise be "concentrated too much in urban areas" at the expense of rural areas, as viewed by some, especially those in rural areas.
The detail of the implementation of this policy is of interest from our viewpoint. Since the introduction of the regional caps, the Japanese medical community uses a modified version of the celebrated deferred acceptance (DA) mechanism by Gale and Shapley (the DA mechanism was in use before 2008). Specifically, in the modified mechanism, which we call the Japan Residency Matching Program (JRMP) mechanism, the capacity of each hospital is reduced so that the total number of the reduced capacities is equal to the regional cap. Then the deferred acceptance algorithm is implemented with respect to the reduced capacities instead of the original capacities.
A problem with this policy is that good properties of the deferred acceptance algorithm are lost. First, the outcome can be inefficient, even in the constrained sense: That is, there may be an outcome that is preferred to the JRMP mechanism's outcome by every doctor and hospital, which does not violate regional caps. Moreover, the outcome may not be stable, in the sense that there may be a pair of an unsatisfied doctor and hospital who prefer to be matched to each other rather than accepting the outcome prescribed by JRMP. These problems arise because the JRMP mechanism decides the reduced capacities for hospitals in a rigid manner. With rigid capacities, some popular hospitals may be artificially constrained from accepting applicants, while other unpopular hospitals in the same region may leave some seats unfilled. In such a case, the capacities assigned to the region may be wasted, resulting in excessive inefficiency and instability.
Similar problems are prevalent in different contexts. One of the largest examples we are aware of is graduate school admission in China, which places about 450,000 students to master's programs every year. In China, master's programs are categorized as either academic or professional and, because of its Marxist past (according to pundits in China), many people have viewed academic masters programs to be superior. However, with the change in its economy, the government began to encourage more students to enroll in professional masters programs. To do so, in 2010 the Chinese government started restricting the number of admission to academic master's programs. More specifically, the government decided to reduce the number of available seats of each academic master's program by about 20-25 percent by 2015 (a reduction of 5 percent per year). This policy is isomorphic to JRMP's regional cap in the sense that a rigid capacity restriction is imposed on each hospital (regard the set of academic and professional masters programs as separate regions). Not surprisingly, the Chinese graduate school admission procedure suffers from inefficiency and instability just like the JRMP mechanism does.
Yet another context in which distributional constraints appear is college admission. In Ukraine, government provides a limited number of "state-financed" seats in public universities, meaning that students matched to state-financed seats do not have to pay tuition. As is easily seen, the constraint is mathematically isomorphic to the last two examples (regard the set of state-financed seats as one region and the set of privately financed seats as another). And the problem with the Ukrainian college admission system is also similar to the last two examples. Namely, government decides the number of state-financed seats and that of privately financed seats in each college, and then a matching procedure assigns students to these college-specific state-financed or privately financed seats. This means that a mismatch of supply and demand could happen for state-financed seats in some colleges, given the rigidity of the number of state-financed seats in each college.
Real-life mechanisms have many varieties, and such is the case with respect to our problem of distributional constraints. Of particular interest is the U.K. medical match. Their matching procedure has two rounds; in the first round, a doctor is assigned to one of the country's 25 regions. Then, in the second round, the region's authority assigns students to programs within the region. A similar two-round mechanism is employed in the matching procedure of new teachers to schools in Scotland as well. These mechanisms are different from the last examples, but they also suffer from inefficiency and instability problems. This is because a student's match to a region is finalized before a student's final destination has been confirmed, so it is possible that she ends up being matched to a place she prefers less to an alternative in another region that also prefers to accept her. So a rigidity of the mechanism, though in a different guise, again plagues the matching outcome.
As we have seen, distributional constraints appear in many different contexts, and how policy makers try to achieve the constraint also varies. Unfortunately, we have also observed that all of the mechanisms above fail to achieve desirable properties such as efficiency and stability. Fortunately, the author found an alternative mechanism which achieves both efficiency and stability in the joint work with Yuichiro Kamada. This mechanism, called the flexible deferred acceptance (FDA) algorithm, assign seats to hospitals in the region in a flexible way in response to how many doctors apply to specific hospitals. That way, the FDA algorithm eliminates the mismatch that plagued the existing mechanisms such as the JRMP mechanism, which rigidly assigned seats to hospitals. Of course, an attention should be given to details in constructing the mechanism: In fact, an intuitive-looking way to adjust capacities (which some policy makers suggested in response to our proposal of FDA) results in the loss of good incentive properties, resulting in doctors having incentives to misreport preferences.
The distributional constraint is an interesting example of real-life features that needs to be addressed with care: A simplistic application (modification) of the existing theory can result in undesirable outcomes, suffering from inefficiency and instability. Yet once the theory is modified appropriately, it guides one to find a mechanism that solves these drawbacks. This type of research seems to be quite characteristic of recent advance of matching theory and market design: For instance, applications of matching theory to school choice resulted in a number of papers that focus on "indifferences" in priority of schools over students (Erdil and Ergin 2008, Abdulakiroglu, Pathak, and Roth AER 2009); special biological properties of blood types proved to be important for a kidney exchange mechanism's asymptotic performance (Roth, Sonmez, and Unver AER 2007), the size of some labor and school matching markets helps matching mechanisms to perform well in terms of efficiency and incentives (Roth and Peraonson AER 1999, Kojima and Pathak AER 2009, Che and Kojima Econometrica 2010), just to name a few examples. I envision that fruitful interactions between theory and practice of this kind will be key to further advancement of research in market design.
About the Author
Fuhito Kojima holds a Ph.D. in Economics at Harvard University. Since 2009 he is Assistant Professor at the Department of Economics, Stanford University. His current research focuses on: analysis of matching/ assignment mechanisms in large economies, practical market design for schools.
Contact: fkojima@stanford.edu