key: cord-0831203-9enz32xe
authors: Kojima, Fuhito; Odahara, Hiroaki
title: Toward market design in practice: a progress report
date: 2021-10-04
journal: Jpn Econ Rev (Oxf)
DOI: 10.1007/s42973-021-00103-w
sha: 682f7a5339b51b62daee2eaf208bfd9502f82159
doc_id: 831203
cord_uid: 9enz32xe

In recent years, many developments have been made in matching theory and its applications to market design. This paper surveys some selected topics from this research area and describe our own work. We also describe the newly established University of Tokyo Market Design Center (UTMD), which works as a vehicle for practical implementation.

During our lifetime, we face a lot of "matching problems." Job market is a matching problem between recruits and employers such as firms, while school/college entrance is a matching problem between children/students and schools/colleges, for instance. For a parent of small children, hunt for a slot in a nursery school/daycare may be a daunting matching problem. Assignment of medical resources such as vaccines is a large-scale and high-stake matching problem that is attracting a lot of attention in the face of global pandemic. This paper was prepared for the Nakahara prize lecture in 2021. We received helpful comments from Yuichiro Kamada, Shingo Maeda, Akira Matsushita, Daisuke Moriwaki, Yusuke Narita and Yasutora Watanabe. Nanami Aoi provided excellent research assistance. Kojima gratefully acknowledges financial support by JSPS KAKENHI Grant-In-Aid 21H04979.

doctors, we assume that each hospital has a preference relation over the set of subsets of doctors. Although in principle the preferences can be quite arbitrary, throughout this paper we assume that hospital preferences satisfy a condition called responsiveness (to its preferences over individual doctors). This condition requires that the hospital has a well-defined capacity (i.e., the maximum number of doctors who can be hired) and a linear order over the doctors plus the outside option such that the hospital's optimal choice from any set of applicants to it is to admit its most preferred acceptable doctors (with respect to the aforementioned linear order over individual doctors) up to its capacity. 1 Thanks to the responsiveness assumption, it turns out that only the ranking over acceptable partners matters for our analysis. Given this observation, we denote preferences by writing an ordered list over acceptable partners. For instance, the expression ≻ i ∶ A, B represents the preference relation of doctor i such that she prefers hospital A most, hospital B second, and the outside option third, and finds all other hospitals to be unacceptable to her.

A matching is a function that specifies each doctor's outcome, i.e., the hospital she is assigned to or the outside option. For example, if doctor i matches with hospital A, B does not match with any doctor, and j does not match with any hospital in matching , we write A matching is individually rational if (i) no doctor or hospital is matched with an agent on the other side of the market who is unacceptable to her, (ii) no doctor is matched with more than one hospital, and (iii) no hospital is matched with more doctors than its capacity. Given a matching , a blocking pair is a pair of a doctor and a hospital who prefer to be matched with each other (while possibly rejecting some or all of their partners at ) rather than staying matched according to . We say that a matching is stable if it is individually rational and there is no blocking pair to it.

A mechanism is a function from the set of preference profiles to the set of matchings. A mechanism is said to be strategy-proof if reporting the true preferences is one of the best responses to every possible report by others. Strategy-proofness is regarded as an important property for a mechanism's success. However, it is known that strategy-proofness and stability are incompatible to each other. More specifically, there is no strategy-proof mechanism that produces a stable matching for all possible preference profiles (Roth 1982) . Given this negative result, it is standard in the literature to require incentive compatibility for doctors only. A mechanism is

strategy-proof for doctors if truthful preference reporting is a best response for each doctor to every possible report by others. In this problem, the following (doctor-proposing) deferred acceptance algorithm proposed by Galeand Shapley (1962) plays a crucial role: • Step 1: Each doctor applies to her first choice hospital. Each hospital rejects its least-preferred doctors in excess of its capacity and all unacceptable doctors among those who applied to it, tentatively keeping the remaining doctors in reserve.

In general, for any t = 1, 2, …

• Step t: Each doctor who is not tentatively kept by a hospital applies to her next highest choice (a doctor does not apply to any hospital if she has been rejected by all hospitals acceptable to her). Each hospital considers these doctors and doctors who are tentatively kept from the previous step together, and rejects its leastpreferred doctors in excess of its capacity and all unacceptable doctors, tentatively keeping the remaining doctors in reserve.

This algorithm terminates at the first step in which no rejection occurs (clearly, it terminates in a finite number of steps). Galeand Shapley (1962) show that the matching produced by this algorithm is stable for any input. This algorithm plays a crucial role throughout, and we discuss it many times, so we refer to it as DA for brevity (the hospital-proposing version of the deferred acceptance algorithm can be defined in an analogous manner, but in this paper we use DA to refer to only the doctor-proposing version of the algorithm). Even though there exists no strategy-proof mechanism that produces a stable matching for all possible inputs, DA is strategy-proof for doctors (Dubins and Freedman 1981; Roth 1982) . This result has significant implications for social implementation. In matching between children and childcare centers, for instance, strategyproof mechanisms provide more reliable data on parents' true preferences than non-strategy ones, enabling government agencies to provide appropriate childcare services based on the true demands of parents. 2 In personnel allocation between employees and divisions within an organization, strategy-proof mechanisms may alleviate the risk of discord among employees due to strategic "gaming" and promote the development of careers that employees really want.

In the following sections, we will describe our own effort in practical market design. Our work in this domain is closely related to a new research center in The University of Tokyo, named the University of Tokyo Market Design Center (UTMD). This section describes it briefly.

One of the authors, Fuhito Kojima, spent much of his academic career in the United States after finishing his BA in Japan in 2003, spending time in Harvard as a PhD student (2003) (2004) (2005) (2006) (2007) (2008) , then in Yale as a postdoc (2008) (2009) , and finally in Stanford as a faculty member (2009 ( -2020 ( , with a sabbatical year at Columbia in 2011 ( -2012 . When he was discussing a possible move to The University of Tokyo, the idea of establishing a new research center emerged. It seemed that a research institution in this field is still rare in Japan (with notable exceptions such as one in Keio University), and it seemed to be a good idea to establish a new institution in The University of Tokyo, given his expertise as well as some of the faculty members there. The idea eventually came to fruition, and the center was established in the fall of 2020, at the same time as Kojima's tenure at Tokyo began.

When the center began, the center had three core faculty members involved (Hitoshi Matsushima, Michihiro Kandori, and Kojima), with Kojima as the director and Kandori and Matsushima as vice directors, but since then the center has expanded substantially. As of this writing in the summer of 2021, it has over 30 researchers affiliated with the center in different degrees of commitments. In addition to the original three members, we now have a new tenure-track assistant professor, Shunya Noda, and one non-tenure track lecturer, Yutaka Kayaba, whose responsibilities involve works at both the Economics Department and the center, two researchers whose main affiliation is with UTMD, Kenzo Imamura and Hiroaki Odahara, two administrative assistants, and about ten research assistants who are students in The University of Tokyo and elsewhere.

The center has two main missions. The first is to advance basic research in market design, which is perhaps obvious given that the center is part of a research university. The second is to advance practical implementation of research, something which may distinguish this center from typical research institutions in universities.

Given the nature of the center, UTMD is collaborating with a number of groups outside academia. In the first year since its establishment, UTMD has received requests for consultation from about 40 institutions on how to solve problems through market design, and we have began collaboration with some of them. Some of the joint works are academically oriented, while others have more focus on actual implementations of mechanisms that are deemed to be desirable. In addition to longterm industry-academia collaborations, we are also working to promptly apply our market design knowledge to urgent issues. For example, we worked on solving the challenges of the vaccination system for COVID-19 in collaboration with UTokyo Economic Consulting Inc. (UTEcon). 3 Given its missions, UTMD needs not only purely academic researchers, but also people who can combine academic insights with practical knowledge while interacting and coordinating with the outside world. One of the authors of this paper, Odahara, is playing this role. He received BA and MA both from the University of Tokyo's Economics Department, and then worked in VisasQ Inc., a startup firm that provides a matching platform for spot consultation. During his career at VisasQ, Odahara experienced a lot of mediating between experts and firms which wanted expertise. Currently Odahara is fully affiliated with UTMD and is in charge of much of the daily operations of the center. This is how the new center looks like at this moment, but our center is still in its infancy, so the optimal arrangement of collaboration would evolve over time. We consider our endeavor a kind of "learning by doing" undertaking, with the center's operations being learned during our daily activities. In the next section, we will describe some of the projects that UTMD is doing right now.

UTMD is working to solve a variety of social issues using market design insights. In this section, we describe some of the efforts by UTMD.

We are trying to help solve the shortage of childcare in Japan. This is a joint project with the GovTech Development Center and the AI Lab at CyberAgent, a technology firm based in Tokyo, Japan, and our team is partnering with several municipal governments such as Tama City and Shibuya City in Tokyo. Our team includes the authors of this article and Yuichiro Kamada from UTMD, as well as Daisuke Moriwaki, Yoshihiro Takenami, Yoji Tomita, and Shota Yasui from CyberAgent. We begin by describing the institutional detail based on Kamada and Kojima (2021) .

Childcare services are heavily subsidized and regulated in many countries, and Japan is no exception. At the same time, unlike some countries such as Sweden, a slot at a daycare is not guaranteed for parents in the Japanese system. The supply of slots at daycare centers is limited, leaving a significant number of applicants unmatched and thus making allocation of slots at daycares an especially big concern for parents.

In Japan, daycare services are heavily subsidized, with the fees determined by each municipal government at a low level. Given the low fee, it is no surprise that the demand for daycare services exceed supply in many municipalities, especially in urban areas. 4 The problem of daycare shortage has become highly politicized in recent years. Most notably, a blog post in 2016 titled "Didn't Get a Slot in Day Care. Drop Dead, Japan!!!" by an anonymous mother became viral and resulted in a big protest movement. Prime Minister Abe addressed the blog post in the parliament (Osaki 2016) and later executed policies to increase childcare capacity by over 300,000 slots in the subsequent five years (Prime Minister's Office 2017). Increasing the supply of slots at daycares in a fair manner continues to be among the very top agenda items for many politicians to this day; For instance, mayors of all ten most populous municipalities present solving the daycare problem as a major political agendas. Despite such attention, as of April 2020, there are still 12439 children on waiting lists (Ministry of Health, Labour and Welfare 2020).

Several features of this market suggest that it is a prime target for social implementation by a market design approach. First, as already pointed out, the daycare market entails excess demand. To manage the excess demand, municipal governments assign daycare seats using an algorithm (parents submit forms stating ordinal preferences over daycare centers). Moreover, almost all seats at daycare centers are allocated at the beginning of the academic year (only a small number of seats are allocated in the middle of the academic year, typically to fill vacancies created during the year). This feature makes it a good approximation to treat each year's allocation as a single static problem, just as is assumed in most matching theory research. Another interesting fact is that municipal governments follow formal assignment rules.

Although the main focus in popular debate is often on the amount of resources and government budget devoted to childcare, it is often hard to devote more and more resources given the limit of available resources. Even under such limitations, we argue that a smart design of daycare slot allocation could improve the outcome for many families, as we describe below.

The first problem is perhaps obvious to the reader of this article, but it is nevertheless very important. Simply, childcare allocation is very costly. An applicant typically needs to fill out paper forms by hand and submit it by mail or in person at city hall. The city official needs to read it and type it into an electric system, typically as entries in a spreadsheet program such as Microsoft Excel. Then, following pre-specified allocation rules, city officials go through the spreadsheet and enter the outcome for each applicant by hand.

Obvious room for improvement exists here. Because the allocation of seats follows a pre-specified procedure, this is an area in which a computer-based algorithm performs very well. In fact, many matching algorithms such as DA are known to run extremely fast and, with thousands of applicants, those algorithms could decide the allocation in less than a couple of seconds even in a typical laptop computer. This is a significant improvement in efficiency, as allocation by human hand may take multiple officials spending several days to weeks to complete it.

Fortunately, automation in this area has emerged in recent years. Fujitsu, for example, provides a number of municipal governments the matching service using a certain variation of the deferred acceptance algorithm. 5 Although we do not know the exact number of municipalities using their system, several municipal governments we are working with told us that they have recently adopted computer-based matching services such as Fujitsu's. Other firms, including our partner CyberAgent, are also working to automate the daycare allocation process. See, for instance, the press release for our joint work with Tama City and Shibuya City which describes the effort to improve the efficiency of the matching procedure. 6 Although computer algorithms offer a vast speed improvement over systems based on human hands, there remain computational problems. One of the major issues in the daycare application is the existence of siblings. Parents of siblings with ages suited for daycare services typically want all of them in one daycare center or at least centers close to one another. This is a form of preference complementarity, a subject well studied in the context of medical match in which some job applicants are couples who seek two jobs close to each other. It is well-known that a stable matching does not necessarily exist in the presence of couples (Roth 1984) , and finding a stable matching is computationally difficult even when one exists. Kojima et al. (2013) show that, however, in markets with many participants such as the NRMP, with high probability a stable matching exists and can be found by the existing algorithm used in NRMP (Roth and Peranson 1999) . Stable matching with siblings in childcare allocation, in a similar vein, suffers from possible non-existence of a stable matching, but existing algorithms, including those which our team employs, usually finds a stable matching. The problem has not been resolved completely, however. For example, there can be multiple stable matchings, and there is no guarantee that the present matching algorithms find the "most desirable" stable matching. 7 We envision that algorithms to find all stable matchings such as may be useful for studying this issue, but at this point this is rather speculative. 7 To our knowledge, there is no consensus onwhat "the most desirable stable matching" means in the presence of couples (in the labormarkets) or siblings (in the daycare assignment problem). We suspect that the criterionto judge desirability of different stable matchings may depend on applications.

In Japan, daycare centers serve children aged between 0 and 5 as of the beginning of a new academic year. And the allocation of slots in daycare centers is done by the municipality. 8 For our purpose, three aspects of this market are especially important. First, the assignment rules are based on reported preferences as well as priorities, where the latter are determined by applicant characteristics such as whether parents have fulltime jobs and whether the parent is a single parent. Second, the national regulations set out teacher-child ratios that require there to be at least one teacher for every three children of age 0 while the ratios are one teacher for every 6 children for ages 1 and 2, 20 children for age 3, and 30 children for ages 4 and 5 (Cabinet Office of Japan 2017). 9 Such a constraint is clearly not the traditional capacity constraint as percapita resources needed to care for children varies across child age groups. Hence, we need to consider the matching problem based on a more general upper bound constraint. Third, even though the true constraint itself is not a capacity constraint, most municipalities treat the number of seats at each daycare center for each age as fixed and non-transferable across different ages, thus effectively setting an artificial capacity constraint.

One might think that implementing non-capacity constraints is unrealistic from the administrative point of view. Quite the contrary, faced with great pressure to improve daycare allocation, some municipalities have been experimenting with making the allocation "more flexible" by relaxing the artificial capacity constraint in one way or another. Specifically, they have introduced policies to have daycare centers with excess supply of seats for certain ages admit more children of ages with excess demand, although in an ad hoc manner. 10 Such policies could be quite effective if designed and implemented well. In fact, due to a variety of institutional features, it turns out that even highly demanded daycare centers often have some vacancies for older children while having excess demand for younger children. For example, Suzuki (2018) points out that about 190,000 seats (across all ages and including both accredited and non-accredited daycares) were vacant in 8 In this paper, we focus on Ninka Hoiku En, which would be roughly translated to accredited daycare centers. This focus involves certain omission of details, for non-acredited daycare centers also exist in Japan. However, they are not necessarily significant in scale except for certain urban areas; as much as 93.5% of the children who are in the daycare system attend accredited ones in 2016 ( Ministry of Health, Labour and Welfare 2017). Possible reasons include that non-accredited centers are more expensive (typically they are not subsidized publicly, at least as much as accredited ones) and that they are generally regarded as of lower quality on average (Asai et al. 2015) . Thus, this paper focuses on only accredited daycare centers. 9 The national regulation also imposes certain age-dependent space-child ratio requirements, and there are other exceptions and variations in rules. However, we ignore these in our analysis. While municipalities are allowed to place more stringent regulations than those imposed by the national government, many municipalities including Yamagata, on which our simulations are based, follow the national regulation on teacher-child ratios. We conducted simulations under specifications including both teacher-child ratio and space-child ratio and verified that the main conclusions we report in this draft are robust. 10 Municipalities with such policies include populous cities such as Yokohama, Kawasaki, Saitama, and Sendai. See Okumura (2018) for details. Japan as of 2017, and attributes a significant part of this figure to the excess supply of seats for older children. As of April 2020, children of ages 1 and 2 account for only 35.0% of the total number of children served but 77.2% of the total number of children on waiting lists ( Ministry of Health, Labour and Welfare 2020).

In a general matching problem such as daycare service, stable matching as defined in Sect. 2 may not exist.

We consider a situation in which four children i 1 , i 2 , i 3 , i 4 wish to attend one daycare center s and ≻ s ∶ i 1 , i 2 , i 3 , i 4 . Let children i 1 and i 3 consume 1/2 of the daycare center's resources, and children i 2 and i 4 consume 1/4 of the resources. In this case, the combinations that the daycare center can accept are i 1 , i 2 , i 4 , i 1 , i 3 , i 2 , i 3 , i 4 , and their subsets. If s selects children according to its priority order as long as its capacity is not violated, the resulting matching is given as follows:

However, is not stable because s, i 3 is a blocking pair ( i 3 ≻ s i 4 and s ≻ i 3 ∅ ). On the other hand, the matching is not stable either because s, i 4 is a blocking pair ( i 4 ≻ s ∅ and s ≻ i 4 ∅ ). Proceeding in this manner, one can check that there is no stable matching in this market. ◻

Given the nonexistence of a stable matching, we focus on matchings that satisfy the following properties. A matching is said to be feasible if it satisfies the constraints on the allocation, such as weighted capacity. A matching is fair if there exist no applicants i and j such that i prefers j's assignment to i's assignment, and i has a higher priority than j at j's assignment. We focus on a matching that satisfies individual rationality, feasibility, and fairness. In Example 1, and ′ are both individually rational and feasible. On the other hand, is not fair while ′ is. Kamada and Kojima (2021) define the student-optimal fair matching (SOFM) as the matching that is individually rational, feasible, and fair and that achieves the most desirable outcome for all applicants (among all individually rational, feasible, and fair matchings). There is often a conflict of interests among the applicants, but SOFM requires the best match for all applicants. It turns out that an SOFM always exists in the matching problem of daycare centers considered in this paper.

Of all the matchings satisfying the three properties mentioned above, the number of the applicants assigned a daycare slot is the largest in the SOFM. Meanwhile, more children may be assigned to a daycare slot by ignoring one of the properties. In Example 1, the matching , which is not fair, accepts more children

To find out what algorithm is truly desirable, we are examining the applicants' actual rankings and data on daycare centers, as well as working closely with local government officials.

We analyze an algorithm that determines to which workplace a worker is assigned. In this problem, we impose constraints that reduce the bias of each group, such as regions and offices.

In this section, we illustrate our effort in design of job markets. Specifically, we discuss medical residency match in Japan, based on Kamada and Kojima (2015) . The Japanese government introduced a centralized matching mechanism for medical residents in 2003, and the initial mechanism was the doctor-proposing DA. However, government faced criticism that too many medical residents are placed to urban areas under DA and, as a flip side of the coin, doctor shortages in rural areas was worsened. In response, government introduced a regulation, the "regional maximum quota" policy. Under regional cap, for each of the 47 regions (prefectures) of the country, the number of medical residents assigned in that region must be no larger than the regional maximum quota specified for that region. Although the regional cap constraints are imposed on each of the 47 prefectures of Japan, the most severe constraints were imposed on large metropolitan areas such as Tokyo, Kyoto, and Osaka. For instance, the total numbers of positions advertised by hospitals in Tokyo and Osaka in 2008 were 1,582 and 860, respectively, and the new regional maximum quotas for these prefectures were set at 1,287 and 533. The prefecture of Kyoto received an even larger proportional reduction of positions, which offered 353 positions in 2008 but received the regional maximum quota of 190, which is almost a 50 percent decline. 11 In total, 34 out of the country's 47 prefectures are subject to binding regional maximum quotas, that is, their regional maximum quotas are smaller than the total numbers of advertised positions in 2008.

Japanese medical match is not the only real-life problem subject to constraints. Quite the contrary, policies that are formally equivalent to it abound. Chinese graduate admission is a case in point. The admission is regulated by a government decree which places a maximum quota on academically oriented masters programs (the motivation for this policy is to increase the number of masters students in professionally oriented programs). In Ukraine and Hungary, some seats in colleges are state-sponsored and subject to the state's budget constraint, making the "region" of all the state-sponsored seats bound by a maximum quota constraint (Biro et al. 2010; Kiselgof 2012) . Furthermore, firms faced with a staffing problem may have constraints on individual divisions as well as a group of divisions. Here, there is a natural isomorphism to the medical match under regional cap constraints, once we associate each division group with a region. We will describe the staffing problem in further detail in Sect. 4.2.2.

Although there are many matching problems with constraints in practice, existing solutions used in those markets suffer from design flaw. Specifically, they lack efficiency or stability or both. To illustrate this point, we present the following example taken from Kamada and Kojima (2015) , using the Japanese mechanism as a concrete case (other constrained matching markets suffer from similar drawbacks).

The Japan Residency Matching Program (JRMP) mechanism-sometimes simply called "the Japanese mechanism"-is the mechanism in use in Japan now, and it is also perhaps the most common mechanism in practice when faced with regional maximum quotas. The mechanism is identical to the doctor-proposing DA except one point: instead of the actual hospital capacity, the mechanism uses an exogenously given artificial capacity, called the target capacity. The artificial capacity at each hospital is no larger than the hospital's real capacity and, for each region, the sum of the artificial capacities across hospitals in that region does not exceed the regional maximum quota.

To illustrate the problems with the Japanese mechanism, we consider the following toy example. There is just one region, and its regional maximum quota is 10. There are two hospitals in this region, A and B, and each hospital has the capacity of 10. There are ten medical residents, i 1 , … , i 10 . Both of hospitals A and B prefer i 1 to i 2 to ... to i 10 to the outside option, while doctors i 1 , i 2 , and i 3 prefer A to the outside option to B and all other doctors prefer B to the outside option to A. Now consider the JRMP mechanism. In this example, we assume the target capacities for each hospital is 5, which is similar to practice in Japan. At the first step of the JRMP mechanism, medical residents i 1 , i 2 and i 3 make applications to hospital A while all other medical residents apply to hospital B. Hospital A rejects no one in this round since the number of doctors applying to it in this step does not exceed its target capacity and all the applicants are acceptable to it. By contrast, hospital B rejects i 9 and i 10 while accepting the others since the number of doctors making applications to it is larger than the target capacity although it is no larger than B's real capacity. Because doctors i 9 and i 10 find A to be unacceptable, the JRMP mechanism terminates at this point. The outcome of this algorithm is given by the following matching:

We consider another matching ′ defined by, Matching ′ is feasible because it still satisfies the regional maximum quota. Moreover, every agent is weakly better off with i 9 , i 10 , and B being strictly better off than at

. Hence we conclude that the JRMP mechanism results in an inefficient matching in this environment.

In this problem, we note that the outcome of the JRMP mechanism is unstable in a certain sense as well. This is because, for example, hospital B and doctor i 9 constitute a block, and the regional maximum quota is not binding at . Therefore, even if i 9 is re-matched with B, the total number of doctors in the region is 9, less than the regional maximum quota of 10. Although we refrain from providing a formal definition of stability under constraints here (see Kojima (2015, 2017) for a formal definition and analysis), it seems fair to say that the outcome of the JRMP mechanism violates any reasonable stability concept. ◻

As mentioned earlier, Kamada and Kojima (2015) study other examples such as graduate school admission in China, medical match in the United Kingdom, and teacher matching in Scotland. They find that all these environments are isomorphic to the problem with regional maximum quotas, and mechanisms used in these markets fail efficiency and stability.

The problem with the existing mechanisms is that, although they are seemingly natural variations of known mechanisms like DA, they lost good properties of the original mechanism as a result of modifications. Part of the problem appears to be that the modifications are rather ad hoc, without (much) consideration for what properties (axioms) need to be maintained. Our approach is to explicitly introduce normative properties that one would like to have and design a mechanism that satisfies them. Based on this idea, Kamada and Kojima (2015) introduce a new mechanism that achieves efficiency, stability, and incentive compatibility, among other things. Their flexible deferred acceptance (FDA) algorithm is a variation of DA and identical to the Japanese mechanism except that it attaches a certain "waitlist processing" phase to each step of the algorithm. Intuitively, the waitlist processing phase adjust the artificial capacities at each hospital in a given region in a flexible manner. Now we describe FDA more formally. We begin with the empty matching, i.e., a matching in which every doctors is unmatched. Then, each step t = 1, 2, … proceeds as follows. • Step t: Each doctor who is not tentatively kept by a hospital applies to her next highest choice (if any).

-Phase 1: Each hospital considers both new applicants and doctors who are temporarily held from the previous step together, and tentatively accepts its most-preferred acceptable doctors up to its target capacity, put the next preferred acceptable doctors on its waitlist up to its true capacity, and rejects every other doctor. -Phase 2: Take the first hospital with respect to an exogenously fixed order.

If there is any applicant on its waitlist and the total number of doctors tentatively matched in the hospital's region is strictly smaller than its regional maximum quota, then let the hospital tentatively accept its most preferred applicant from its waitlist. Apply the same procedure to the second hospital (again, with respect to the exogenously fixed order), and so forth (and after the last hospital, return to the first hospital). When there is no more applicant to be processed, reject all the remaining doctors on the waitlist and proceed to the next step.

The algorithm terminates at a step in which no rejection occurs-given that the numbers of doctors and hospitals are finite, it is clear that this algorithm terminates in a finite number of steps. The FDA mechanism is defined as the mechanism that produces the matching at the termination of the above algorithm. FDA is similar to DA but guarantees feasibility of the produced match, i.e., satisfies the regional cap constraints. The difference of FDA from JRMP in that it lets hospitals accept doctors in a flexible fashion because of waitlist-processing. Specifically, Phase 1 of the FDA algorithm is identical to a phase in JRMP, while Phase 2 allows hospital accept (temporarily) more doctors from the waitlist as long as the corresponding region's cap is not filled yet. FDA eliminates inefficiency of the Japanese mechanism thanks to this waitlist-processing phase. Generally, Kamada and Kojima (2015) establish that FDA produces a stable and constrained efficient matching in the presence of regional cap constraints. To illustrate, in Example 2, inefficiency occurred in the JRMP mechanism because doctors i 9 and i 10 are rejected from hospital B due to the artificial capacity even though neither the hospital's real capacity nor the regional maximum quota is binding. The FDA algorithm eliminates this kind of inefficiency by allowing hospital B to accept doctors i 9 and i 10 from the waitlist in Phase 2.

In addition to efficiency and stability, incentive compatibility is an important property for the matching mechanism. Kamada and Kojima (2015) show that FDA is strategy-proof for doctors. Moreover, they show that the matching produced by the FDA mechanism is Pareto superior to the JRMP outcome for doctors. In other words, each doctor weakly prefers the outcome of FDA to the outcome of JRMP. An implication of this result is that the number of unmatched doctors will weakly decrease if the mechanism were to be changed from JRMP to FDA.

For practical implementation, an important question would be whether the magnitude of improvement by a better mechanism is substantial enough to warrant (likely costly) implementation of a new mechanism. To make a progress on this question, Kamada and Kojima (2015) conduct numerical analysis. They use artificially generated data in their simulations. Specifically, preferences of doctors and hospitals are randomly generated following a certain distribution, with the model parameters calibrated to match the publicly available data for Japanese medical residency matching. They compute how many doctors are matched and unmatched, respectively, under the original, unconstrained DA, JRMP, and FDA. They first find that regional maximum quotas can leave significantly more doctors unmatched: About 800 out of about 8300 doctors are unmatched in the unconstrained DA, which is substantially smaller than 1400 in the JRMP mechanism. They also find that FDA eliminates much of the loss due to regional caps. The FDA mechanism leaves roughly 1000 doctors unmatched, which is an increase of merely 200 additional doctors over the unconstrained DA, which is much smaller than the corresponding figure for JRMP, namely 600 additional unmatched doctors. We refer interested readers to Kamada and Kojima (2015) for further detail including the simulation methods and additional numerical results.

Clearly, a major limit of the numerical study presented above is that it is based on artificially created data. Although Kamada and Kojima (2015) calibrated the numerical model's parameters to match publicly available data, it is nevertheless obvious that the match is not perfect. The number of unmatched doctors under JRMP, for example, is about 1400 in their simulation, which is much larger than the actual numbers, which were about 300 in years around the introduction of the regional cap constraint. 12 We are hoping to obtain real data on residency match to do more realistic simulations.

In human resource allocation in the private sector, there is also a need to avoid biasing employees to certain regions or divisions. Furthermore, in corporate human resources, it is usually unacceptable for organizations to leave its employees unmatched. Perhaps for these reasons, Japanese firms often ignored the wishes of at least one of the sides (i.e., the division or the employee) when deciding on assignments.

We have launched a team that aims to study how to improve personnel assignment in organizations, as well as actually help improve the procedures in practice. Our team includes the authors, Akira Matsushita, and Yusuke Narita. We have partnered with Sysmex Corporation, a Japanese medical device manufacturer, to apply matching theory to human resource allocation. As a first project, we used the FDA to determine the assignments for employees who joined the firm in April 2021.

The decision to use FDA was not in the initial plan, but its benefit became increasingly clear as we talked about their needs in meetings. One of the features of their problem is that there are multiple divisions that belong to a larger unit which we call a "division group." For instance, there are multiple research teams within one of the firm's research facilities, and capacity constraints are imposed on individual research teams as well as the entire facility; for sales representatives, there are capacity constraints on individual sales offices as well as on each region (e.g., Sapporo, Sendai, and so on). We observe that the setting is identical to the one for residency match under regional cap constraints, once we associate each division with a hospital and each division group with a region. So the FDA seemed like it would be an appealing market design approach in this setting.

And in fact, the FDA proved useful in this case. While we mentioned to the firm's representatives that one could use a JRMP-style algorithm, i.e., set artificial capacities at the individual division level, we explained that such a mechanism can entail efficiency loss. The firm's representatives recognized FDA's efficiency gain over the JRMP-style design and adopted it. When we implemented FDA, we compared its performance to what would have happened if we were to stick to the more traditional JRMP-style design, using the real data submitted by the participants. We found that FDA improves the match for employees, and that the magnitude of the improvement was quite significant (detailed analysis will not be included here and deferred to a full paper to be written). Overall, our new design succeeded in accommodating practical issues at the firm related to assignment while incorporating the wishes of both divisions and employees.

One important research question we are trying to answer is that of how to best measuring the long-term impact of matching mechanisms. Theory suggests that the new mechanisms improve the satisfaction level of employees (and likely division leaders as well), and possibly the performance of the firm may be affected. Empirically, however, the long-run impact of the introduction of the FDA is yet to be measured, and we plan to continuously observe it. Meanwhile, the preliminary feedback we have received from the participants so far suggests that the employees and divisions were assigned with highly desirable outcomes, and they report higher levels of satisfaction and motivation than in previous years. Among the reasons cited by the participants for this high level of satisfaction is that they were led to give serious thoughts on their own preferences and appeal to the other side during the process of forming preferences and participating in the formal matching process. This aspect appears to be often ignored or minimized in the formal analysis in matching theory, but it may be of a big practical importance and may merit further scrutiny.

This paper surveyed some of the recent advances in matching theory and our effort to implement mechanisms in practice. To conclude here, we discuss how our implementation efforts could enrich research and vice versa.

When one thinks of a relation between research and practical implementation, the benefit that research has on implementation seems rather obvious at this point, if not 20 years ago. Guided by theory, there are many examples of successful reorganizations of marketplaces, ranging from medical match, school choice, organ allocation, and spectrum auction, just to name a few. This also seems to be apparent in our own projects such as daycare assignment, medical match, and internal personnel allocation in firms. A possibly more nontrivial question is, how about the opposite direction? What, if any, does practical implementation do to improve research? Once researchers have mathematically proven what desirable properties a certain mechanism has, isn't the implementation "just an application" of existing knowledge off the shelf?

We argue that practical implementations can be sources for research ideas and enrich research. For example, when we talked with multiple firms interested in personnel assignments, we became aware that divisions in a firm often have flexibility about how many positions of each type to offer to its employee, as long as the division's budget constraint is satisfied. The setting here is more general than the common constraint in division groups mentioned in Sect. 4.2.2 because different positions may have different cost, so the FDA mechanism cannot be used off the shelf. The constraint, however, satisfies the general feasibility constraint analyzed in Kamada and Kojima (2017) . That paper provides an algorithm to find a "weakly stable" matching under general constraints, although they also observed that such an algorithm is not necessarily strategy-proof for the applicants. In an ongoing effort to address this problem, we recently found an algorithm that not only finds a weakly stable matching but also is strategy-proof for the applicant under budget constraints. Currently, we are evaluating whether the new mechanism is practical in the intended applications and, in particular, whether there is any unintended negative consequence associated with the new design.

Another example of this kind concerns daycare assignment. As we delved into institutional details of childcare and interacted with various stakeholders such as parents and municipality officials, it became increasingly apparent to us that the city boundary can hinder efficient assignments of daycare seats. In the current practice, the daycare system of each municipality primarily serves its own residents. Even if the municipality allows residents in other districts to apply, their priority is set lower than the residents and, given that the chance for admission is very low while the application process is costly (the applicant needs to submit an application separately to each municipality), the number of such inter-municipality daycare admission is very low. This seems like a significant problem, given that there are over 1,700 municipalities in Japan, with each municipality serving only a relatively small population and geographic area. Moreover, many parents may find it convenient to put their child to a daycare close to their workplace that is in a different municipality from where they reside (which is especially commonplace in a large metropolitan area such as Tokyo). A work in progress by Yuichiro Kamada and Kojima formalized this problem and found an algorithm that produces a constrained-efficient fair matching subject to a "balanced exchange" requirement, the property that the number of non-residents admitted to daycares in a municipality is equal to that municipality's residents who are admitted to daycares in other municipalities. 13 These are among the research ideas that are directly motivated by our effort to learn from practical issues in applications. We are optimistic that researcher-practitioner interactions, like the ones we conduct with the help of UTMD, will not only benefit society at large but also enrich research itself.

School choice: a mechanism design approach

Childcare availability, household structure, and maternal employment

The college admissions problem with lower and common quotas

The multi-unit assignment problem: theory and evidence from course allocation at Harvard

On the new child-and childbearing support policy

Machiavelli and the Gale-Shapley algorithm

College admissions and the stability of marriage

Interdistrict school choice: a theory of student assignment

Efficient matching under distributional constraints: theory and applications

Stability concepts in matching with distributional constraints

Fair matching under constraints: theory and applications. Review of Economic Studies (forthcoming)

Matching practices for Universities-Ukraine

Recent developments in matching theory and their practical applications

Matching with couples: stability and incentives in large markets

Summary of the Current Status of Non-Publicly Certified Daycare Centers, Fiscal Year

Summary of the situation related to nursery schools, etc

School choice with general constraints: a market design approach for nursery school waiting lists problem in Japan

Angry blog post sparks movement for improved day care

The economics of matching: stability and incentives. Mathematics of Operations Research

The evolution of the labor market for medical interns and residents: a case study in game theory

The Economist as Engineer: game theory, experimentation, and computation as tools for design economics, Fisher-Schultz lecture

The redesign of the matching market for American physicians: some engineering aspects of economic design

Kidney exchange

Pairwise kidney exchange

Efficient kidney exchange: coincidence of wants in markets with compatibility-based preferences

Course bidding at business schools

An economist tries to reduce the daycare waitlist to zero