Issue No. 19/2013
CTN Newsletter n.19 - March 2013
Index
- Editorial
- From theory to application: Matching Markets under Distributional Constraints: Theory and Practical Design
- CTN New & Announcements
- New papers on coalition and network theory
- CTN Members' seminars
Editorial
Sergio Currarini, Fondazione Eni Enrico Mattei and Ca' Foscari University of Venice
Dear All,
We have just come back from this year’s annual CTN meeting in Warwick, beautifully organized by Bhaskar Dutta. The three excellent keynote lectures were given by Herve Moulin (on fair division), Fuhito Kojima (on matching) and Sanjeev Goyal (on intermediated exchange). Fuhito is also contributing to the present issue of the newsletter in the section “From Theory to Application”, with a very instructive survey of matching theory applied to doctors’ allocation. The contributed sessions taught us about a wide array of applications and developments of network and coalition theory, ranging from matching in school admission, to the role of complementarities and peer effects in network formation and in social behaviour, to diversity and segregation, to voting and democracy.
Turning now to the (immediate) future, we have some exciting announcement to help you organize your Summer period. There will be two special sessions dedicated to CTN at the upcoming PET Conference in Lisbon (5-7 July), organized by Ana Mauleon (on Coalition Formation and Matching) and Vincent Vannetelbosch (on Networks). And there are a few events that, although not directly sponsored by CTN, are very close in topic and spirit. Among these, the 6th Maastricht Behavioral and Experimental Economics Symposium (Maastricht, Netherlands, 3 June 2013 (organiser: Arno Riedl), the Barcelona GSE Summer Forum (Barcelona, Spain, 10-26 June 2013 - session organisers: Inés Macho-Stadler, Carmen Beviá), the26th European Conference on Operational Research - EURO XXVI (Rome, Italy, 1-4 July 2013) and, last but not least, the13th SAET Conference on Current Trends in Economics (Paris, France,22-27 July 2013 - Programme Committee: Myrna Wooders; Session Organisers. Michel Grabisch, Jean-Jaques Herings, Agnieszka Rusinowska, Francis Bloch).
Well, this should keep all of us busy for the Summer, and I hope will give most of us the chance to cross paths again soon, and keep the CTN family united. All the best to all,
Sergio Currarini
From theory to application
Matching Markets under Distributional Constraints: Theory and Practical Design
Fuhito Kojima, Department of Economics, Stanford University
Market design is a rapidly growing field of economics. In a somewhat stylized caricature, most existing economic theory took market institutions as given and focused on describing how they work. Market design, by contrast, studies "What would an optimal institution look like?" Using insights from game theory and mechanism design, as well as empirical, experimental and case studies, researchers and practitioners in market design have helped design many practical market institutions.
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.
Visit the new section on the CTN website
CTN News & Announcements
SAVE THE DATE: 19th CTN Workshop
Brussels, Belgium, 30-31 January 2014
More information soon
CTN partners are also involved in the scientific organisation of the following events:
6th Maastricht Behavioral and Experimental Economics Symposium
Maastricht, The Netherlands, 3 June 2013
http://www.fdewb.unimaas.nl/meteor-seminar-et/M-BEES-2013/
Barcelona GSE Summer Forum
Barcelona, Spain, 10-26 June 2013
http://www.barcelonagse.eu/summer-forum.html
Seventh International Conference “Game Theory and Management” (GTM 2013)
St. Petersburg, Russia, 26-28 June 2013
http://www.eng.som.pu.ru/gtm2013/
26th European Conference on Operational Research (EURO XXVI)
Barcelona, Spain, 10-26 June 2013
http://euro2013.org/
13th Public Economic Theory Annual Conference (PET13)
Lisbon, Portugal, 5-7 July 2013
http://www.accessecon.com/pubs/pet13/default.aspx?page=content&linkID=1073&menu=2/
SING 9 meeting
Vigo, Spain, 8-10 July 2013
http://sing9.uvigo.es/
13th SAET Conference on Current Trends in Economics
Paris, France,22-27 July 2013
http://www.saet.uiowa.edu/event-13.shtml
Visit the CTN Members' seminars web pages
CES: http://centredeconomiesorbonne.univ-paris1.fr/bandeau-haut/seminaires/
CORE: http://www.uclouvain.be/en-43617.html
FEEM: http://www.feem.it/getpage.aspx?id=82&sez=Events&padre=21&tab=1
GREQAM: http://www.greqam.fr/spip.php?rubrique13&lang=fr
Maastricht: http://www.fdewb.unimaas.nl/meteor-seminar-et
MOVE: http://www.movebarcelona.eu/index.php/events/upcoming-events
Vanderbilt: http://www.vanderbilt.edu/econ/seminars-and-research/index.html
Warwick: http://www2.warwick.ac.uk/fac/soc/economics/forums/
About the CTN Newsletter
The CTN Newsletter is prepared with the contribution of all the CTN Partner Institutions. Please send comments and questions to: silvia.bertolin@feem.it.
The next issue will be published in September 2013