New Algorithms for Japanese Residency Matching

1 Introduction

Real-life matching markets often pertain to different forms of constraints [Kamada and Kojima, 2017a; Sun, 2020]. For instance, diversity concerns are pervasive in school choice where students are associated with a set of types and schools impose quotas on each type [Abdulkadiro˘glu and S¨onmez, 2003; Ehlers et al., 2014; Kurata et al., 2017; Gonczarowski et al., 2019]. Another example is refugee resettlement, where refugee families have multi-dimensional requirements that involve several services such as housing, education, and job opportunities [Aziz et al., 2018].

In this paper, we focus on a particular form of distributional constraints motivated by the Japanese Residency Matching Program (JRMP) that was established in 2004. It aims to provide training for new medical school graduates at hospitals. For the past decade, more than 1000 hospitals and around 10000 doctors have annually participated in JRMP 1 .

Due to the shortage of doctors in rural areas, in 2008 the Japanese government introduced regional quotas to limit the number of doctors who can be placed in different regions. To ensure that the number of doctors matched to a region does not exceed its regional quota, a target capacity (a.k.a an artificial-cap), which is usually smaller than its real capacity, is also imposed on each hospital 2 . The Artificial-Cap Deferred Acceptance algorithm (ACDA), which is currently deployed by JRMP, works in the same way as the original Deferred Acceptance algorithm, except that each hospital is subject to its target capacity. However, such rigid target capacity may lead to a waste of vacant positions. For instance, consider a hospital with a real capacity of six and a target capacity of four. Suppose six doctors apply, two of whom cannot be matched due to the target capacity, even if the regional quota has not been filled.

1 https://www.jrmp.jp

2 https://www.mhlw.go.jp/seisaku/2009/08/04.html

The objective of our research is to solve the inefficiency issue with minimal modification to the current system. We propose an effective and simple approach to reduce vacant positions. The basic idea is that each hospital is "divided" into two dummy hospitals such that one dummy hospital has the target capacity and a larger weight, and the other dummy hospital has the remaining capacity (i.e., real capacity minus target capacity) and a smaller weight. When the number of doctors who apply for hospitals in a particular region exceeds its regional quota, the region first fills the vacant positions of the dummy hospitals with a larger weight, and then considers the dummy hospitals with a smaller weight.

The contributions of this paper are summarized as follows. First, we introduce a new model of matching with regions that incorporates weights over hospitals. It covers many applications that aim to optimize and allocate resources in a balanced way, such as school admissions. Second, we propose a class of algorithms called Generalized Deferred Acceptance with Regions (GDA-R) that provides a new framework for matching models with regions. Furthermore, we propose two particular implementations based on the GDA-R framework for JRMP. Third, we theoretically and empirically compare our new algorithms with ACDA and show that they provide an effective and simple approach to solve the inefficiency issue and are reasonable alternatives to ACDA.

2 RelatedWork

Kamada and Kojima [2015] first studied the inefficiency issue in JRMP and proposed a possible solution that treats the target capacities as soft bounds such that hospitals are allowed to accept more doctors than their target capacities as long as regional quotas are respected. Their approach equalizes the numbers of doctors matched to hospitals when the target capacities are fulfilled, by requiring hospitals to take rounds to choose doctors one by one until regional quotas are reached.

However, since this approach disadvantages larger capacity hospitals, especially for JRMP where hospital capacities vary widely, the solution may not be adequate [Kamada and Kojima, 2020]. This algorithm, which can be considered as a special implementation of GDA-R, is discussed in the Appendix.

Some existing algorithms are designed for matching with regional quotas [Goto et al., 2015; 2016; 2017a; Hamada et al., 2017] that work for some particular setting. In contrast, we propose a novel class of algorithms (GDA-R) to provide a new framework for matching with regions. Other papers are more mathematical and focus on an abstract and a general class of constraints, e.g., constraints that can be represented as a substitute choice function [Hatfield and Milgrom, 2005; Hatfield and Kojima, 2008], an M-convex set [Kojima et al., 2018]. Although representing these two models in an abstract model is possible, how to encode such constraints and preferences as a choice function in an abstract model is not obvious and deserves further exploration.

3 Model

In this section, we introduce a new model of matching with regional quotas that incorporates weights over hospitals. We choose the classical hospital-doctor setting for our illustration, although our model can be extended to many matching markets outside the context of hospital-doctor matching. An instance I R of matching with regional quotas is composed of a tuple (D, H, qH, R, δ, Y , ≻D, ≻H, ≻R, W).

Let D and H denote two sets of doctors and hospitals. A capacity vector qH = (qh)h∈H consists of each hospital h's capacity qh, which is the maximum number of doctors that it can accommodate. There is a set of regions R where each region r ∈ R is a subset of hospitals, i.e., r ⊆ H. We assume all hospitals are partitioned into disjoint regions as in JRMP s.t. for any two different regions, ri, rj ∈ R, we have ri ∩ rj = ∅. Let δ = (δr)r∈R denote a vector consisting of each region's maximum quota δr which limits the number of doctors who can be distributed to hospitals within region r.

Let Y ⊆ D×H denote a set of available contracts, where each contract (d, h) is a doctor-hospital pair denoting that doctor d is matched to hospital h. Given any Y ⊆ Y , let Yd = {(d, h) ∈ Y | h ∈ H} be the set of contracts involving doctor d, let Yh = {(d, h) ∈ Y | d ∈ D} be the set of contracts involving hospital h, and let Yr = ⋃h∈r Yh be the set of contracts involving region r. We follow the model of matching with contracts [Hatfield and Milgrom, 2005] for two reasons. First, it allows us to describe more complicated regional priorities over doctor-hospital pairs instead of doctors, as we will explain below. Second, it allows us to concisely describe our concepts and algorithms.

An outcome is a set of contracts Y ⊆ Y . An outcome Y is feasible for I R with respect to regional quotas if i) for each doctor d, we have |Yd| ≤ 1, ii) for each hospital h, |Yh| ≤ qh holds, and iii) the outcome Y respects regional quotas, s.t. for any region r, we have |Yr| ≤ δr.

Let ≻D= {≻d}d∈D be a preference profile of all doctors. Each doctor d has a preference ordering ≻d over Yd ∪ {∅} where ∅ is a null contract indicating that doctor d is unmatched. For any two contracts x, y ∈ Yd ∪ {∅}, x ≻d y means that doctor d prefers contract x to contract y. Let ≻H= {≻h}h∈H denote a priority profile of hospitals H where each hospital h has a priority ordering ≻h over Yh ∪ {∅}.

3.1 Regional Priorities

We assume that each region r also imposes a regional priority ordering ≻r over Yr ∪ {∅}. Let ≻R= {≻r}r∈R denote a priority profile of regions R. Regional priority is used to determine which doctors should be matched when the number of applicants exceeds the regional quota [Aziz et al., 2019]. Imposing a global ordering is a common way to break ties in the literature of two-sided matchings. The regional priority orderings in JRMP can be derived from academic performances or a lottery.

Given a hospital h ∈ r, the priority ordering ≻r of region r is consistent with the priority ordering ≻h of hospital h if for any two contracts x, y ∈ Yh, x ≻h y implies x ≻r y. The assumption of consistency is reasonable, because the regional priority orderings are determined by policy makers. The following is a natural way of generating consistent priority orderings. A region prefers (d, h) to (d′ , h′ ) if the rank of (d, h) at hospital h is strictly higher than the rank of (d′ , h′ ) at hospital h′ . If the ranks are the same, then ties are broken by a strict ordering over hospitals [Goto et al., 2016].

Note that the two new algorithms we designed for JRMP do not require an assumption of consistency, although they become equivalent under consistency.

3.2 Weights over Hospitals

The main difference from previous models on matching with regional quotas is that each region r additionally assigns a weight w(h) to each hospital h ∈ r to quantify the importance of hospital h to region r. Let W = {w(h)}h∈H denote the set of weights.

The intuition of weights over hospitals is that, when more doctors apply to hospitals in region r than its regional quota δr, region r gives higher precedence to hospitals with larger weights and lower precedence to those with smaller weights. In other words, region r attempts to fill the vacant positions of hospitals with larger weights whenever possible. If ties occur, then it chooses the contract with higher regional priority based on ≻r.

4 Desirable Properties

In this section, we describe several desirable properties and propose some new concepts on fairness and non-wastefulness that address weights over hospitals.

A contract (d, h) is acceptable to doctor d and hospital h if (d, h) ≻d ∅ and (d, h) ≻h ∅ hold. We assume that for any h ∈ r, if a contract (d, h) ∈ Yh is acceptable to hospital h, then it is also acceptable to region r. An outcome Y ⊆ Y is individually rational if each contract (d, h) ∈ Y is acceptable to both doctor d and hospital h. W.L.O.G., we can assume that all contracts in Y are acceptable to hospitals (by removing unacceptable contracts from Y ). Then, we can ensure individual rationality in our proposed mechanisms in which doctors only choose from acceptable contracts.

For our model, an algorithm takes an instance I R as input and yields a set of contracts Y . An algorithm is strategy-proof for doctors if no doctor can be matched with a better contract by misreporting his preferences.

Note that a stable outcome is no longer guaranteed to exist because of regional quotas [Kamada and Kojima, 2017b]. We decompose stability into two properties, fairness and nonwastefulness, which are commonly considered in the literature of two-sided matching problems [Goto et al., 2016; Kurata et al., 2017; Aziz et al., 2019; 2020]. Prior to our new fairness and non-wastefulness concepts with respect to weights over hospitals, we first introduce some notation to simplify the representation.

Given a feasible outcome Y and contract (d, h) /∈ Y with h ∈ r, we use the following function α(Y, (d, h), r) to quantify the importance of the contract (d, h) to region r.

Function α(Y, y, r) returns the weight w(h) of hospital h if it still has a vacant position and otherwise returns negative infinity.

4.1 Non-wastefulness under Regional Weights

Next we propose a new non-wastefulness concept in Definition 1 w.r.t regional priorities and weights. Definition 1 can be decomposed into two properties non-wastefulness across regions and non-wastefulness within the same region, which are formally described in the Appendix.

Definition 1 (Non-wastefulness under Regional Weights). Given a feasible outcome Y , doctor d claims a vacant position of hospital h at region r under regional weights, if new outcome Y ∪{(d, h)}\Yd is feasible and one of the following three conditions holds:

• i) Yd = ∅;
• ii) Yd = (d, h′ ) and h′ /∈ r;
• iii) Yd =(d, h′ ), h′ ∈r and for outcome Y ′ =Y \ Yd, we have either α(Y ′ , (d, h), r) > α(Y ′ , (d, h′ ), r) or α(Y ′ , (d, h), r) = α(Y ′ , (d, h′ ), r) and (d, h) ≻r (d, h′ ).

A feasible outcome is non-wasteful under regional weights if no doctor claims a vacant position.

The first two conditions of Definition 1 correspond to nonwastefulness across regions. Doctor d is matched outside of region r in the outcome Y (including the case of being unmatched), and transferring doctor d to hospital h in region r does not violate the feasibility requirement.

The third condition corresponds to non-wastefulness within the same region. Doctor d is matched to hospital h′ at region r in outcome Y and he prefers another hospital h to h′ within the same region r. The contract (d, h) is given higher precedence over Yd if for outcome Y ′ = Y \ Yd, either hospital h has a larger weight than h′ or both contracts have identical weight but contract (d, h) has higher regional priority.

Definition 1 is stronger than the original non-wastefulness concept designed for classical two-sided matchings, because we consider more possibilities for which a doctor can claim a vacant position by taking account of the regional priorities and weights.

4.2 Fairness under Regional Weights

Next we propose a new fairness concept in Definition 2 w.r.t regional priorities and weights, which can be decomposed into two properties fairness with same weight and fairness by larger weight. They are formally presented in the Appendix.

Definition 2 (Fairness under Regional Weights). Given a feasible outcome Y , doctor d with (d, h) ≻d Yd and h ∈ r has justified envy toward doctor d′ with (d′ , h′ ) ∈ Y and h′ ∈ r under regional weights, if for outcome Y ′ = Y \ {(d′ , h′ )}, one of the following three cases holds:

• i) h = h′ , (d, h) ≻h (d′ , h′ ) and (d, h) ≻r (d′ , h′ );
• ii) h ̸= h′ , α(Y ′ , (d, h), r) = α(Y ′ , (d′ , h′ ), r) and (d, h) ≻r (d′ , h′ );
• iii) h ̸= h′ and α(Y ′ , (d, h), r) > α(Y ′ , (d′ , h′ ), r).

A feasible outcome is fair under regional weights if no doctor has justified envy toward another doctor.

Note that conditions i) and ii) of Definition 2 correspond to fairness with same weight and condition iii) corresponds to fairness by larger weight. Condition i states that doctor d prefers to be matched with the same hospital h as doctor d′ , and doctor d can "replace" doctor d′ if both hospital h and region r give higher priority to contract (d, h) over (d′ , h′ ). For conditions ii) and iii), doctor d prefers to be matched with hospital h than h′ . Condition ii states that both contracts (d, h) and (d′ , h′ ) are tied in terms of importance, but region r gives higher priority to contract (d, h) over (d′ , h′ ). Condition iii states that the contract (d, h) is more important to region r than (d′ , h′ ).

5 AlgorithmDesign

In this section, we propose a new class of algorithms called "Generalized Deferred Acceptance with Regions" (GDA-R), based on a two-stage process such that contracts proposed by doctors are first shortlisted by hospitals and then further refined by regions. It provides a new framework for matching models with regional quotas and is a significant generalization of the Generalized Deferred Acceptance algorithm that works without regional quotas [Hatfield and Milgrom, 2005].

We also propose two particular implementations based on the GDA-R framework for JRMP: Generalized Deferred Acceptance with Regions and Hospitals (GDA-RH) and Generalized Deferred Acceptance with Regions Only (GDA-RO), which differ only in how hospitals choose contracts.

5.1 GDA-R

Next we illustrate how GDA-R works at a high level. In every iteration, each doctor first chooses his favorite contract that remains available and each hospital selects a set of contracts among all the proposals from doctors. Each region then chooses a set of contracts among the set of contracts chosen by hospitals. All contracts that are not selected by regions are rejected and removed from the market. Repeat this procedure until no more contracts are rejected.

Before proceeding to the formal description of GDA-R, we introduce some notation to represent the procedure of

Algorithm 1 Generalized Deferred Acceptance with Regions

Input: I R,ChD,ChH,ChR, a set of contracts Y

Output: An outcome Z ⊆ Y

• 1: Re ← ∅,A← Y,B ← ∅,Z ← ∅
• 2: while A ̸= Z do
• 3: A←ChD(Y \ Re),B ←ChH(A),Z ←ChR(B)
• 4: Re ←Re ∪ (A \ Z) %Update rejected contracts
• 5: return Z

Algorithm 2 Choice function Chr of region r

Input: An instance I R, a set of contracts Yr

Output: A set of contracts Z ⊆ Yr

• 1: Z ← ∅
• 2: Let Yr = Y 1 r ∪ ... ∪Y k r s.t. ∀(d, h) ∈ Y a r , ∀(d′ , h′ ) ∈ Y b r
• w(h) = w(h′ ) ⇒ a = b
• w(h) > w(h′ ) ⇒ a < b
• 3: for each Y a r ∈ Yr, a ∈ [1, · · · , k] do
• 4: for (d, h) ∈ Y a r in descending ordering of ≻r do
• 5: if |Zr| < δr and |Zh| < qh then
• 6: Z ← Z ∪ {(d, h)}

• 7: return Z

selecting contracts. Given any Y ⊆ Y , let Chd(Y ) denote choice function of doctor d that selects his most preferred contract from Yd. Choice function Chh(Y ) of hospital h and choice function Chr(Y ) of region r select a set of contracts from Yh and Yr. The choice function of a set of agents is the union of each individual's choice function, i.e., ChD(Y ) = ⋃d∈D Chd(Y ). Armed with these choice functions, we describe GDA-R in Algorithm 1.

It is not unique to define choice functions Chh(Y ) and Chr(Y ), and each different method specifies one implementation of GDA-R algorithm. In this paper, we propose one particular way to define Chr(Y ), as shown in Algorithm 2. We consider two different ways to define Chh(Y ), and the GDA-RO and GDA-RH algorithms differ only in their choice function of hospitals.

5.2 Choice Function of Regions

Choice function Chr of region r in Algorithm 2 works as follows. First, divide all contracts Yr = Y 1 r ∪ Y 2 r ... ∪ Y k r into disjoint groups based on hospitals' weights s.t. for any two contracts (d, h) ∈ Y a r , (d′ , h′ ) ∈ Y b r , i) if two hospitals h and h′ have the same weight, then two contracts belong to the same group; ii) if hospital h has a higher weight than hospital h′ , then contract (d, h) belongs to the group with a smaller superscript a. Region r first selects contracts from group Y 1 r , followed by Y 2 r and so on. For each group Y a r , region r selects contracts based on its regional priority ≻r without exceeding its regional quota and the hospital capacity.

The intuition of Algorithm 2 is that regions assign weights to hospitals to quantify their importance in terms of achieving a balanced outcome. When the number of applicants exceeds the regional quota, then the region determines which doctors should be chosen in a reasonable way to fill the vacant po-

Algorithm 3 Choice function Chh of hospital h

• Input: An instance I R, a set of contracts Y Output: A set of contracts Y ′ ⊆ Y 1: Y ′ ← ∅ 2: for y = (d, h) ∈ Y in descending ordering of ≻h do 3: if |Y ′h | < qh then 4: Y ′ ← Y ′ ∪ {y} 5: return Y ′

sitions of hospitals with larger weights whenever possible. When ties occur, the region chooses the contract with a higher regional priority.

5.3 Choice Functions of Hospitals

Next we introduce the choice function of hospitals employed in GDA-RH, which works as follows. Each hospital selects contracts one by one based on its priority ordering ≻h until the number of contracts reaches its capacity qh, as described in Algorithm 3, which is equivalent to its counterpart in the classical Deferred Acceptance algorithm.

We can define another choice function Ch∗h of hospital h that chooses all contracts proposed by doctors without rejecting any contract (even if the number of proposals exceeds hospital's capacity). Formally, given any Yh, Ch∗h (Yh) = Yh. Choice function Ch∗h is used in Generalized Deferred Acceptance with Regions Only (GDA-RO).

5.4 Comparison of GDA-RH and GDA-RO

Although GDA-RH is more natural and appropriate for taking hospitals' choices into account, it satisfies fewer properties than GDA-RO. On the other hand, we present GDA-RO for theoretical interest, because it satisfies all the desirable properties. In addition, GDA-RO is equivalent to GDA-RH under a reasonable assumption of consistency.

We formalize these results through the following theorems. We also compare GDA-RH, GDA-RO and ACDA in Table 1. Detailed proofs are provided in the Appendix.

Theorem 1. The GDA-RO algorithm is strategy-proof for doctors and yields a non-wasteful and fair outcome under regional weights.

Table 1: Properties satisfied by GDA-RO, GDA-RH, and ACDA under general priority domain

Theorem 3. When the priority orderings of hospitals and regions are consistent, both GDA-RO and GDA-RH return the same outcome.

6 Example of JRMP

Next we illustrate how to apply GDA-RO and GDA-RH to JRMP through Example 1. Recall for ensuring that the sum of doctors matched to one region does not exceed its regional quota δr, a target capacity qh is imposed on each hospital with ∑h∈r qh ≤ δr [Kamada and Kojima, 2015].

Example 1. Consider the following market with four doctors and two hospitals located at one region r. In the priority ordering of region r, only acceptable contracts are listed:

≻r: (d1, h1), (d2, h1), (d3, h1), (d4, h2).

The outcome yielded by ACDA is {(d3, h1), (d4, h2)}. However, the regional quota is not fulfilled and one position at hospital h1 is wasted.

Next we illustrate how GDA-RO and GDA-RH work. Recall that GDA-R requires weights over hospitals as part of the input, and we first divide each hospital into two dummy hospitals with different capacities and weights, where one dummy hospital has the target capacity and a larger weight, and the other dummy hospital has the remaining capacity and a smaller weight (see Figure 1). The subscripts of dummy hospitals correspond to their original hospitals and the superscripts indicate their weights.

Then we create new contracts with respect to dummy hospitals. For each doctor d, his preference ordering is modified as follows. First, replace each contract (d, h) with (d, h1 ) and insert another contract (d, h0 ) right after (d, h1 ). For instance, ≻d1 : (d1, h11 ), (d1, h01 ). Each dummy hospital inherits the priority ordering from its original hospital, i.e., ≻h11 : (d3, h11 ), (d1, h11 ), (d2, h11 ), (d4, h11 ).

The outcome yielded by GDA-RH is {(d1, h01 ), (d3, h11 ), (d4, h12 )} and the outcome yielded by GDA-RO is {(d1, h11 ), (d2, h01 ), (d4, h12 )}. The detailed procedures of GDA-RH and GDA-RO are presented in the Appendix.

During the GDA-RH and GDA-RO processes, each region first attempts to fill the vacant positions of the dummy hospitals with larger weights (corresponding to the target quotas) and then considers all the dummy hospitals with smaller weights (corresponding to the remaining quotas). This provides a simple and effective way to distribute doctors to underserved regions with minimal modification to the current system. This idea can be useful for other matching markets in which the agents who play the role of regions have the authority to interfere in the matching process.

7 Experiments

In this section, we empirically evaluate our newly designed algorithms GDA-RH and GDA-RO. Since we have proved that they satisfy some notion of non-wastefulness, our experiments instead focus on the welfare of doctors. Note that their welfare is also a major concern to JRMP, because it incentivizes medical students to participate in the program. The government annually announces the numbers of doctors who are matched to their top k choices, and we use this method to measure the performances of the algorithms.

As a benchmark, we chose Artificial-Cap Deferred Acceptance algorithm (ACDA) , which is currently deployed in JRMP market and is commonly used as the baseline in the literature on matching with regions [Fragiadakis et al., 2016; Goto et al., 2016; 2017b; Hamada et al., 2017].

7.1 Setup

We consider a medium-sized market with |D| = 200 doctors, |H| = 10 hospitals, and |R| = 2 regions. We assume all hospitals have the same capacity and artificial-cap, and all regions have the same number of hospitals and regional quotas.

In JRMP, the total quota of all the regions is around 11,000, which equals the sum of all the artificial-caps of the hospitals. The total number of doctors participating in the market is about 10000 3 . In the experiments, the artificial cap is set to |D| / |H| ∗ 1.1 = 22, and the regional quota is set to |D| / |R| ∗ 1.1 = 110 where the factor 1.1 simulates JRMP market. Since we do not have access to the actual capacity of hospitals, we use |D|/|H| ∗ ratio to determine the capacity of each hospital, where a ratio is chosen from three reasonable values: {1.2, 1.5, 2.0}.

The preference profiles of the doctors and the priority profiles of the hospitals and regions are generated by Mallows Model (MM), which is commonly used to generate preference and priority profiles when such information is unavailable [Lu and Boutilier, 2011]. Let Φ denote a set of possible preference orderings. The Mallows Model is a distribution over the permutations of Φ determined by two parameters: a reference order σ ∈ Φ and a dispersion parameter θ ∈ (0, 1]. The probability of choosing a preference order ≻d is calculated:

where d(≻d, σ) represents the Kendall distance, measured by the number of inconsistent ordered pairs between ≻d and σ. We exploit the PrefLib library to generate preference and priority profiles [Mattei andWalsh, 2013]. In this experiment, θ takes three values from {0.2, 0.5, 0.8}.

3 http://www.jrmp2.jp/toukei/2019/2019toukei.htm

Note that in our setting, the doctors consider all contracts acceptable and the sum of all the artificial-caps exceeds the total number of doctors. Thus no doctor is unmatched for all three algorithms.

7.2 Experimental Results

There are two parameters in our experiments. Ratio determines the capacity of each hospital, and dispersion parameter determines the preference and the priority profiles generated by the Mallows Model. There are totally nine different settings, as shown in Figure 2. Next we summarize our experimental results.

The first observation is that for each algorithm, Mallows Model's dispersion parameter significantly affected the welfare of the doctors. As the dispersion parameter increased, doctors' preferences became more diverse and they became more likely to be assigned to their top choices.

The second observation is that the ratio parameter that determines the capacity of each hospital played a minor role. As the ratio became larger, the number of doctors who were matched to their top k choices slightly increased.

The third observation is that, GDA-RH consistently outperformed GDA-RO and ACDA for all the settings. Although GDA-RO matched fewer students to their top three choices than ACDA for ratio 1.2 and θ ≤ 0.5, it outperformed ACDA for ratio 2.0. When ratio was 1.5, GDA-RO performed weakly better than ACDA except for the number of top choices with θ = 0.5.

In summary, GDA-RH dominated the other two algorithms in terms of doctors' welfare, and GDA-RO performed better than ACDA when the hospitals' capacities exceeded the artificial-caps (i.e., ratio 1.5 or more).

8 Conclusion

In this paper, we studied the Japanese Residency Matching Program (JRMP), which suffers from inefficiency issues due to target capacities imposed by the government. We derived two algorithms, GDA-RO and GDA-RH, to reduce waste with minimal modification to the current system. GDA-RO satisfies more desirable properties than GDA-RH, although GDARH more effectively satisfies doctors' welfare. These two algorithms become equivalent under a reasonable assumption of consistency.

In conclusion, our two new algorithms, GDA-RH and GDA-RO, are suitable alternatives to ACDA for several reasons. First, both algorithms satisfy at least one notion of nonwastefulness while the ACDA algorithm leads to a waste of vacant positions. Second, GDA-RH is beneficial for the welfare of doctors, especially for real-life markets where doctors have similar but not identical preference orderings (i.e., θ = 0.5). On the other hand, GDA-RO satisfies many more desirable properties than ACDA and outperforms ACDA when hospitals' capacities exceed artificial-caps.

For the future work, one possible direction is to investigate whether algorithms exist that have the merits of both GDARO and GDA-RH based on the GDA-R framework.

Acknowledgments

This work was partially supported by JSPS KAKENHI Grant Numbers JP20H00587 and JP20H00609.