geo slide06 最近の更新履歴 yyasuda's website

Improving Efficiency in Matching Markets with

Regional Caps: The Case of The Japan Residency

Matching Program

Yuichiro Kamada¹ Fuhito Kojima²

October 8, 2011

1Harvard University.

2Stanford University.

Overview

Geographical distribution of medical doctors is a contentious (and often politicized) issue in health care.

Hospitals in rural areas do not attract enough medical residents to meet their demands: 35 million Americans living in underserved areas and need 16,000 doctors.

Doctor shortages are common around the globe.

Geographical Distribution of Medical Residents in Japan

Japanese medical residency matching from 2003: a clearinghouse using the deferred acceptance algorithm by Gale and Shapley (1962).

Prior to the reform, clinical departments in university hospitals allocated doctors.

Critics say that many rural hospitals fill fewer positions in the new matching mechanism.

Japanese government introduced a “regional cap” as a constraint, and modified the DA (JRMP mechanism).

Main Results

Research goal: study how to design labor matching clearinghouses under constraints, taking Japanese residency as a concrete case. This project

1 shows that the JRMP mechanism may result in avoidable inefficiency and instability,

points out the standard stability concept may be inadequate and formalizes several stability concepts under regional caps,

2 proposes the flexible deferred acceptance mechanism which

1 improves efficiency and generates stable matchings while meeting the regional caps,

2 is (group) strategy-proof for doctors.

→ A better mechanism!

Related Literature

Rural hospital theorem: McVitie and Wilson (1970), Roth (1984, 1986), Gale and Sotomayor (1985), Martinez, Masso, Neme, and Oviedo (2000).

Requirements on balanced student distributions: Roth (1991), Abdulkadiroglu and Sonmez (2003), Abdulkadiroglu (2005), Abdulkadiroglu, Pathak, and Roth (2005, 2009), Ergin and Sonmez (2006), Ehlers (2010), Westkamp (2010).

Matching with contracts: Hatfield and Milgrom (2005), Hatfield and Kojima (2008, 2009), Hatfield and Kominers (2009, 2010). Constraints on aggregate distribution: Abraham, Irving and Manlove (2003), Sonmez and Unver (2006). Milgrom (2009), Budish, Che, Kojima and Milgrom (2010).

Basic Setup

There are a set of doctors D and a set of hospitals H.

Each doctor d has strict preferences ≻d over hospitals and being unmatched, ∅.

Each hospital h has strict preferences ≻h over doctors and being unmatched, together with capacity qh. Preferences are extended to subsets of doctors (“responsive preferences,” Roth 1985).

A matching µ specifies which doctor is matched with which hospital: For any i ∈ D ∪ H, µⁱ is the matching for i.

Model of Regions

Each hospital belongs to exactly one region r ∈ R.

For each region r , there is a regional cap qr (a positive integer). A matching is feasible ifthe number of doctors assigned in each region r is at most qr.

This requirement distinguishes the environment from the standard model without regional caps.

Other potential applications:

1 Medical specialties: ACGME decides total numbers of residents in each specialty.

2 Student placement in public schools: multiple school programs share one school building.

The Deferred Acceptance (DA) Algorithm

In a model with no regional cap, Gale and Shapley (1962) propose the (doctor-proposing) deferred acceptance algorithm. Start from a matching in which no one is matched.

Application Step:

Choose a doctor who is currently unmatched, and let her apply to her most preferred hospital that has not rejected her so far (if any). Acceptance/Rejection Step:

Each hospital considers the combined pool of the tentatively matched doctors and the new applicant (if any). Specifically, the hospital chooses its most preferred acceptable doctors up to its capacity (if they exist) and rejects everyone else.

The algorithm terminates at a step in which no rejection occurs, producing a matching.

Why Use DA?

1 DA outcome is stable, i.e., individually rational and there is no block (mutually profitable deviation by a doctor and a hospital).

Stability ⇐⇒ Core.

Stability is often regarded as fairness.

2 DA produces an efficient matching (because it is in the core).

3 DA is (group) strategy-proof for doctors (Dubins and Freedman 1981, Roth 1982): reporting true preferences is a dominant strategy for every doctor.

4 DA is not strategy-proof for hospitals, but incentives for manipulation become small in large markets (Roth and Peranson 1999, Kojima and Pathak 2009).

The JRMP Mechanism

In Japan, government exogenously imposes a target capacity

¯

q^h≤ q^h for each hospital h such that^P_h∈Hr ¯q^h≤ q^r for each region r ∈ R.

The JRMP mechanism implements the deferred acceptance mechanism, except that it uses the target capacity instead of the hospital’s actual capacity as input.

Idea: In order to satisfy regional caps, simply force hospitals to be matched to a smaller number of doctors than their real capacities, but otherwise use the standard deferred acceptance algorithm. But does the JRMP mechanism inherit good properties of DA?

JRMP Matching Can Fail (Constrained) Efficiency

There are two hospitals h1, h2 in one region with regional cap 10. Each hospital has a capacity of 10 and a target capacity of 5. There are 10 doctors, d1^{, . . . ,}d10 such that

d1≻^hd2^,≻^h. . .≻^hd10≻^h ∅, for both hospitals, d₁,d₂,d₃ find only h₁ acceptable,

d4, . . . ,d10 find only h2 acceptable. The JRMP mechanism produces

µh_{1 = {d1},d2^,d3}

µh_{2 = {d4},d5^,d6^,d7^,d8}. This matching is inefficient.

Stability Concept

Clearly, the JRMP matching may be unstable in the standard sense. We introduce a new stability concept.

→ Idea: The only blocking pair is caused because the regional cap is binding.

Definition

A matching µ is weakly stable if it is feasible, individually rational and,if(d, h) is a blocking pair, then

1 number of docs matched inh’s region = regional cap, and

2 _d^′ _≻hd for all d^′ ∈ µ^h.

The definition may not be the most natural because a movement to a hospital with a vacancy from a hospital in the same region is precluded (discussed later).

Outcome of JRMP May Violate Weak Stability

The same example as before: There are two hospitals h1, h2 in one region with regional cap 10.

Each hospital has a capacity of 10 and a target capacity of 5. There are 10 doctors, d1, . . . ,d10 such that

d1≻^hd2^,≻^{h. . .}≻^hd10≻^h ∅, for both hospitals, d1^,d2^,d3 find only h1 acceptable,

d₄, . . . ,d₁₀ find only h₂ acceptable. The JRMP mechanism produces

µh₁ = {d1^,d2^,d3}

µh_{2 = {d4},d5^,d6^,d7^,d8}. This matching is not weakly stable.

The Flexible DA Mechanism

We define the flexible deferred acceptance mechanism below, given target capacity profile (¯q^h)h∈H. Start with a matching in which no one is matched.

Application Step:

Choose a currently unmatched doctor, and let her apply to her most preferred hospital that has not rejected her so far (if any). Acceptance/Rejection Step:

Consider the region of the hospital receiving the new application. Each hospital in the region chooses from the tentatively matched doctors and the new applicant (if any):

1 First, each hospital chooses its most preferred acceptable applicants up to its target capacity.

2 Then, one by one, each hospital in the region takes turns (following a fixed order) to choose the most preferred remaining applicant who are applying to it until (i) the regional quota is filled or (ii) the capacity of the hospital is filled or (iii) no doctor remains to be matched.

Example of flexible DA

The same example as before: There are two hospitals h1, h2 in one region with regional cap 10.

Each hospital has a capacity of 10 and a target capacity of 5. There are 10 doctors, d1, . . . ,d10 such that

d1≻^hd2^,≻^{h. . .}≻^hd10≻^h ∅, for both hospitals, d1^,d2^,d3 find only h1 acceptable,

d₄, . . . ,d₁₀ find only h₂ acceptable. The flexible DA mechanism produces

µh₁ = {d1^,d2^,d3}

µh_{2 = {d4},d5^,d6^,d7^,d8^,d9^,d10}, which isweakly stable and efficient.

Weak Stability

Theorem

The flexible deferred acceptance mechanism produces a weakly stable matching for any input.

Intuition:

Unlike JRMP, the target capacity of each hospital is not rigid. As long as the regional cap is not violated, hospitals can tentatively accept doctors beyond the target capacities.

Like the DA, an acceptable doctor rejected from a more preferred hospital was rejected either because there are enough better doctors in that hospital, or regional quota was filled by other doctors.

→ The doctor cannot form a blocking pair!

Efficiency

Theorem

Any weakly stable matching is efficient.

Note: This result is well-known when there is no regional cap, and is a straightforward implication of the fact that stability is

equivalent to core.

But with regional caps, there is no obvious way to define the core. Fortunately the statement still goes through.

Corollary

The flexible deferred acceptance mechanism produces an efficient matching for any input.

Strong Stability

Weak stability may be problematic because blocking within a region does not violate regional caps. → Stronger stability concept! Definition

A matching µ is strongly stable if it is feasible, individually rational and, if(d, h) is a blocking pair, then

1 number of doctors matched in h’s region = its regional cap,

2 _d^′ _≻hd for all d^′ ∈ µ^h, and

3 d is not matched in h’s region. ← new!

Strongly Stable Matchings May Not Exist

There is one region with regional cap of one, with two hospitals h1

and h2 with capacity one each and two doctors, d1 and d2, with preferences

≻^h₁: d₁,d₂, ≻^h₂: d₂,d₁,

≻^d₁: h2^,h1^, ≻^d₂: h1^,h2^.

1 No matching in which two doctors are matched is feasible because it violates the regional cap.

2 If no doctor is matched, then there is a blocking pair (d1 and h₁ for example).

3 A matching where µ^h₁ = {d2}. → (d1^,h1) is a blocking pair (h1 can reject d2 to be paired with d1).

4 A matching where µh₁ = {d₁}. → (d1^,h2) is a blocking pair.

5 _µh

2^{= {d}2} and µ^h₂ = {d1} is not strongly stable (symmetric argument).

Stability

Definition

A matching µ is stable if it is feasible, individually rational and, if(d, h) is a blocking pair, then

1 number of doctors matched inh’s region = its regional cap,

2 _d^′_≻hd for all d^′∈ µh, and

3 ₁ d is not matched in h’s region or

2 _{|µh| + 1 − ¯qh>|µµd| − 1 − ¯qµd}

Idea: If there is a blocking pair that involves a doctor movement within a region, then moving (weakly) increase the imbalance of doctor distribution within the region.

Theorem

The flexible deferred acceptance mechanism produces a stable matching for any input.

Intuition: The flexible DA tries to fill excess doctors above target one by one.

Incentives

Theorem

The flexible DA mechanism is (group) strategy-proof for doctors: Truthtelling is a dominant strategy for every doctor.

A (very rough) intuition: a doctor doesn’t need to give up trying for her first choice because, even if she is rejected, she will be able to apply to her second choice etc. Thedeferredacceptance guarantees that she will be treated equally if she applies to a position later than others.

Truthtelling is not necessarily a dominant strategy for hospitals (Roth 1982: There is no strategy-proof and stable mechanism.)

Failure of The Rural Hospital Theorem

The conclusion of the rural hospital theorem fails: The set of unmatched doctors and hospitals can differ across stable matchings.

There are two regions r and r^′ with regional cap of one each. Hospitals h1 and h2 are in r and h3 is in r^′ with capacity one each. Preferences are

≻^h1^{: d}1,d2, ≻^h2^{: d}2,d1, ≻^h3^{: d}2,

≻^d₁: h₁,h₂, ≻^d₂: h₂,h₃.

One stable matching matches d1 to h1 and d2 to h3. Another stable matching matches d2 to h2 only.

Given this, design of the mechanism may influence geographical distributions of doctors.

Our Results Put in Context

Practical contribution: a better mechanism for the Japanese residency matching market.

More generally, this project tries to advance market design to solve practical design problems.

Other potential applications:

1 Residency markets in other countries.

2 U.S. medical resident markets: ACGME decides total numbers of residents in each specialty.

3 Student placement in public schools: multiple school programs share one school building.

Theoretically, we propose a new model of matching with regional caps. New stability concepts are defined and analyzed.

Conclusion

JRMP can be improved upon by another mechanism, the flexible DA.

A new matching problem with regional caps and appropriate stability concepts were introduced.

→ the model may be useful more generally. Other Issues and Future Research:

1 Alternative policy goals → generalized flexible DA algorithms.

2 Other applications.

3 Empirical study or simulation, practical implementation.