Matching with regional constraints: An equivalence

Elizabeth Nanami Aoi

REVIEW 3 major objections 5 minor 24 references

Matching with regional constraints: An equivalence

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that deferred acceptance, run with per-hospital quotas taken from the FDA outcome's fill counts, reproduces the FDA matching exactly, so constrained-efficient allocations of regional caps always exist.

desk verdict A plausible, novel equivalence between FDA and DA with adapted capacities, but the proof relies on an unverified identification of Algorithm 2 with the KK2015 FDA, so it needs revision before the claim is established. read the letter →

arxiv 2504.17467 v1 pith:SHOC4ZZS submitted 2025-04-24 econ.TH

Elizabeth Nanami Aoi This is my paper · ORCID

classification econ.TH MSC 91B68

keywords FDAalgorithmDAregionalconstraintsmatchingwithcontractsweakstabilitycapacitydesigndistributionaldoctor-optimality

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper addresses a practical obstacle in applying the deferred acceptance (DA) algorithm to markets with regional caps: the caps must be split among hospitals, and a poor split can make DA inefficient. It proves that, for any fixed preferences, there exists a split under which DA produces a constrained efficient, weakly stable matching. The construction is not arbitrary—the right split is the doctor distribution produced by the flexible deferred acceptance (FDA) algorithm, and DA run with those exact per-hospital quotas returns precisely the FDA matching. This gives the FDA algorithm a new reading as an endogenous capacity-design tool for DA, and it offers a general way to prove equivalences among DA-based mechanisms.

What carries the argument

The key machinery is the matching-with-contracts model—contracts are doctor–hospital pairs, with all hospitals aggregated into one agent—together with rationalized hospital-side choice functions. For the original market the hospital side maximizes $g^F(\xi(Y)) + f_R(\xi(Y)) + \epsilon f_H(Y)$; for the shadow market it maximizes $g^D(\xi(Y)) + f_H(Y)$, where $\xi(Y)$ is the vector of doctors per hospital. The first terms enforce feasibility (regional caps in one market, adapted capacities in the other), $f_R$ encodes the region-level preference, $f_H$ encodes hospital preferences, and the small $\epsilon$ makes the region-level objective dominate. These rationalizations let the proof express stability in both markets as a choice-function condition, so that doctor-optimality of the generalized DA in each market forces the FDA outcome and the shadow-market DA outcome to be the same.

What would settle it

Run doctor-proposing DA on a small market (for instance, the three-hospital, five-doctor example in the paper) with each hospital's capacity set to its FDA fill count; if any FDA order produces a DA outcome different from the FDA matching, Theorem 2 is false. Alternatively, directly test the hospital-side choice rule of Algorithm 2 for substitutability and the law of aggregate demand, since the proof inherits doctor-optimality from a cited theorem only under those conditions.

Watch

Extended reading notes

Core claim

The central result, Theorem 2, says that if $\mu^F$ is the matching produced by the FDA algorithm and each hospital $h$ is assigned the adapted capacity $\tilde q_h = |\mu^F_h|$, then the DA matching $\mu^D$ in the market with those capacities satisfies $\mu^F = \mu^D$. The proof constructs two markets: the original market $M^F$ with regional caps, where the FDA runs, and a shadow market $M^D$ without regional caps but with the adapted hospital capacities, where DA runs. Using the matching-with-contracts framework, the author shows that the FDA outcome is stable in both markets and that the DA outcome is stable in both markets. Since the generalized DA is doctor-optimal in each market, the two stable allocations must coincide. The author concludes that efficient allocations of regional caps therefore always exist, that they can be read off the FDA outcome, and that the same argument extends to hierarchical regional constraints and to any DA-based mechanism whose hospital-side choice function first picks a distribution and then assigns doctors.

Load-bearing premise

The load-bearing premise is that the two-phase hospital-side choice rule in Algorithm 2 satisfies substitutability (a rejected offer stays rejected when more offers arrive) and the law of aggregate demand (more offers never reduce the number of doctors chosen), because the proof's equivalence argument inherits doctor-optimality from a cited theorem that requires those two conditions but does not itself verify them for this specific algorithm.

Editorial extensions

If this is right

There always exists an allocation of regional caps under which the DA algorithm is constrained efficient and weakly stable (Corollary 1).
Starting from any weakly stable but inefficient DA matching, moving to the FDA-based allocation makes every doctor weakly better off (Theorem 1).
The FDA outcome can be implemented by a standard DA run in a shadow market with hospital-level quotas, so no region-level hospital order is needed at implementation time.
Weak stability in the original regional-cap market coincides with ordinary stability in the shadow market with adapted capacities.
The equivalence extends to hierarchical regional constraints and to any DA-based mechanism whose hospital-side choice first fixes a distribution and then assigns doctors, when the required regularity conditions hold.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A reverse reading is implicit: any DA run with adapted capacities can be viewed as an FDA run for some region-level preference order, whenever those capacities match the fill counts of some FDA outcome.
For applications such as residency matching, the equivalence suggests a regulator could compute fill counts once from FDA and then implement with plain DA, preserving strategy-proofness for doctors while avoiding the appearance of favoring one hospital order.
The proof is a transferable recipe for other constrained settings: model the hospital side as a distribution-picking choice function, verify the regularity conditions, and compare doctor-optimal stable allocations in original and shadow markets.
Because the theorem is stated for fixed preferences, it does not say how the adapted capacities should be revised when preferences change; a dynamic or preference-robust version of the equivalence remains open.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Two things to know. The equivalence claim is genuinely new and the two-market optimality proof is an attractive idea. But the proof as written does not cover the algorithm it defines, and that is a real problem.

What is good: the paper states a clean result — set each hospital's capacity in DA to the number of doctors the FDA placed there, and DA reproduces the FDA matching. That gives FDA a nice interpretation as endogenous capacity design and recasts weak stability as ordinary stability in a shadow market. The proof technique, using the Hatfield-Milgrom framework and KK2018's rationalization of choice functions, is compact and mostly fillable. The author is honest about relying on KK2018.

The soft spots. Algorithm 2 is presented as the Kamada-Kojima (2015) FDA, but it is a variant: the real KK2015 FDA has no target-capacity phase. Here the algorithm first fills target capacities, then lets the region fill remaining seats in hospital order. In Example 2 this produces a different outcome than the actual KK2015 FDA with the same order. The proof invokes KK2018 Proposition 1 to assert that the FDA outcome is doctor-optimal stable in the original market, but that proposition requires the hospital-side choice function to satisfy substitutability and the law of aggregate demand. The paper never checks these properties for the choice function induced by Algorithm 2, and the target-capacity phase makes it doubtful that the KK2018 result covers it. Without that check, the premise of Step 1 is unsupported. There is also a small gap in Step 2(i): the distribution equality holds because x' and the rejected contract must be at the same hospital; this follows from the rural hospital theorem but is not explained.

So the result is plausible and the proof strategy is a genuine contribution, but the paper is not ready as written. It needs either a direct proof of the choice-function conditions for Algorithm 2, or a redefinition of the algorithm to match the KK2015 FDA.

Who is this for: people working on matching with distributional constraints, particularly those comparing DA-based mechanisms. It deserves referee time — the idea is worth taking seriously and the fix seems feasible.

Recommendation: send to peer review, but make clear that the KK2018 identification and the target-capacity issue must be resolved before acceptance.

Referee Report

3 major / 5 minor

Summary. The paper studies two-sided matching with regional caps. It claims that for any preference profile there exist allocations of the regional caps among hospitals (adapted capacities) such that the deferred acceptance (DA) algorithm produces a constrained efficient and weakly stable matching, and that this matching coincides exactly with the outcome of the flexible deferred acceptance (FDA) algorithm of Kamada and Kojima (2015). The proof embeds the original regional-constraint market and a shadow market with adapted capacities into the matching-with-contracts framework, invokes doctor-optimality of the generalized DA and the rural hospital theorem, and concludes that the FDA and DA outcomes coincide.

Significance. If the theorem holds, it provides a clean interpretation of the FDA algorithm as an endogenous capacity-design device for DA and offers a broadly applicable template for equivalence proofs among DA-based mechanisms, with natural extensions to hierarchical constraints. The paper builds on established results, and the two-market optimality argument is elegant and economical. However, the proof as written has gaps that prevent acceptance in its current form.

major comments (3)

[Section 2.5, proof of Theorem 2; footnotes 7 and 10; Section 2.3, Algorithm 2] The proof relies on Kamada and Kojima (2018) Proposition 1 to assert that the FDA outcome X^F is a doctor-optimal stable allocation in the original market M_F, but it does not verify that the hospital-side choice function induced by Algorithm 2—with its target-capacity filling phase and order-based regional filling phase—satisfies substitutability and the law of aggregate demand, nor that Algorithm 2 is exactly the cumulative offer process of that contracts market. Because Step 1 of the proof depends entirely on this premise, the equivalence theorem is not yet established.
[Section 2.5, Step 2(i)] The equality ξ(X^F + x') = ξ(X^D + ~x) is asserted for any x' ∈ X^D\X^F with X^F + x' ≻_D X^F, but it holds only if x' and ~x involve the same hospital. This is a gap. The case appears to be vacuous because ~x ∈ X^F and ~x ∈ C_D(X^D + ~x) contradict X^D ≽_D X^F from (1), but the paper should state this explicitly or construct x' with the required hospital. As written, this step is unsupported.
[Section 2.3, Algorithm 2] The definition of the FDA algorithm includes target capacities q̄_h, which are not part of the model primitives in Section 2.1 and are not part of the original Kamada and Kojima (2015) FDA as presented there. The paper should specify the domain of q̄_h and state whether Theorem 2 is meant to hold for all target capacities or for a particular choice; otherwise the statement of Theorem 2 is not fully well-defined.

minor comments (5)

[Section 2.2, Example 1] The text says "d4 and d5 remain unmatched," but in the displayed matching d5 is matched to h3; the intended statement is that d3 and d4 remain unmatched.
[Algorithm 1] The phrase "rejects the the lowest-ranking" contains a duplicated article.
[Footnote 7] The definition of substitutability uses the variables x and x' in a way that could be confused with the surrounding text's use of x; consider relabeling.
[Footnote 9] The word "gerenralized" is a typo for "generalized."
[Section 3] The statement that weak stability in the original market coincides with stability in the shadow market is asserted without proof; if this is intended as a direct consequence of Theorem 2, it should be made explicit.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the adapted capacities are derived from the FDA outcome, and the equivalence is proved via external optimality theorems rather than assumed.

full rationale

The paper's central claim, Theorem 2, is a genuine equivalence statement: it defines the DA capacities as the FDA fill counts q̃_h = |μF_h| and then proves, not assumes, that the DA outcome equals the FDA outcome. The proof does not fit any parameter to a target and rename it a prediction; q̃_h is an endogenous construction from μF, and the theorem would be false if the DA algorithm could choose a different matching within those capacities. The derivation chain relies on external results — Hatfield and Milgrom (2005) doctor-optimal stable allocations in matching with contracts, Kamada and Kojima (2018) Proposition 1 identifying the FDA outcome with a doctor-optimal stable allocation, and the rural hospital theorem — none of which are authored by the present paper's author, so no self-citation load-bearing issue arises. The potential weaknesses flagged by a skeptical reader, namely that the paper does not explicitly verify substitutability and the law of aggregate demand for the specific choice function induced by Algorithm 2, and that the Step 2(i) distributional equality is not fully justified, are correctness and completeness concerns, not circularity: they concern whether the cited premises are satisfied, not whether the conclusion is secretly an input. No equation or definition in the paper sets μD := μF or defines the FDA outcome in terms of the DA outcome. Accordingly, the paper is not circular; it is a derivation against external benchmarks, with any gaps belonging to proof hygiene rather than self-referential reasoning.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The proof is a derivation and fits no data, so there are no fitted free parameters and no newly postulated entities. The load-bearing inputs are background results from the cited literature (DA optimality, the rural hospital theorem, and KK2018 Proposition 1) plus the paper's own asserted rationalizations of the hospital-side choice functions, whose properties are not derived in the text.

assumptions (5)

standard math In a standard two-sided market with responsive preferences, the doctor-proposing DA algorithm returns the doctor-optimal stable matching (Gale and Shapley 1962; Hatfield and Milgrom 2005).
Used in the proof to make X^D the doctor-optimal stable allocation in the shadow market MD, Section 2.5.
standard math The rural hospital theorem: all stable matchings in MD match the same number of doctors at each hospital, so ξ(X^D) = ξ(X^F).
Invoked right after Equation (1) in Section 2.5 to equate the distributions of the two stable matchings.
domain assumption Kamada and Kojima (2018), Proposition 1: the generalized FDA outcome X^F is a doctor-optimal stable allocation in the matching-with-contracts market whose hospital-side choice function aggregates hospital and regional preferences.
Load-bearing external result cited in footnote 10; the paper relies on it to make X^F doctor-optimal in the original market MF and does not reprove the substitutability and law of aggregate demand conditions.
ad hoc to paper The hospital-side choice function of the FDA (Algorithm 2, with target capacities and turn-taking order) can be rationalized by f^F(Y) = g^F(ξ(Y)) + f_R(ξ(Y)) + ε f_H(Y) with lexicographic priority, and similarly f^D for the shadow market.
Asserted in Section 2.5; existence and strict-priority properties of f_R (for example monotonicity in holding more contracts) are not proven in the text.
domain assumption Hospital preferences are responsive (Roth 1985) with capacity q_h, and regional caps and hospital capacities are the only constraints.
The model in Section 2.1; the proof uses responsiveness to invoke additive f_H rationalizations and the rural hospital theorem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Matching with regional constraints: An equivalence." pith.science (2026). https://pith.science/paper/SHOC4ZZS

@misc{pith2026250417467,
  author       = {Pith},
  title        = {Pith review of: Matching with regional constraints: An equivalence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SHOC4ZZS}},
  note         = {Machine review of arXiv:2504.17467}
}

read the original abstract

In two-sided matching market, when the regional constraints are present, the deferred acceptance (DA) algorithm suffers from undesirable inefficiency due to the artificial allocation of the regional caps among hospitals. We show that, given preferences, there exist allocations that guarantee the efficiency of the DA algorithm. Furthermore, it is equivalent to the FDA algorithm developed by Kamada and Kojima (2015), which endows the latter with an interpretation as a tool for endogenous capacity design. Our proof applies the optimality within the matching with contracts (Hatfield and Milgrom 2005) framework, offering a broadly applicable method for establishing equivalence among DA-based mechanisms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 22 canonical work pages

[1]

Abdulkadiro g lu, A. (2005). College admissions with affirmative action. International Journal of Game Theory , 33:535--549

work page 2005
[2]

and S \"o nmez, T

Abdulkadiro g lu, A. and S \"o nmez, T. (2003). School choice: A mechanism design approach. American economic review , 93(3):729--747

work page 2003
[3]

Akin, S. (2021). Matching with floor constraints. Theoretical Economics , 16(3):911--942

work page 2021
[4]

and Turhan, B

Ayg \"u n, O. and Turhan, B. (2020). Dynamic reserves in matching markets. Journal of Economic Theory , 188:105069

work page 2020
[5]

and Yildiz, K

Do g an, B. and Yildiz, K. (2023). Choice with affirmative action. Management Science , 69(4):2284--2296

work page 2023
[6]

and Yenmez, M

Echenique, F. and Yenmez, M. B. (2015). How to control controlled school choice. American Economic Review , 105(8):2679--2694

work page 2015
[7]

E., Yenmez, M

Ehlers, L., Hafalir, I. E., Yenmez, M. B., and Yildirim, M. A. (2014). School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic theory , 153:648--683

work page 2014
[8]

and Troyan, P

Fragiadakis, D. and Troyan, P. (2017). Improving matching under hard distributional constraints. Theoretical Economics , 12(2):863--908

work page 2017

Show all 24 references

[9]

and Shapley, L

Gale, D. and Shapley, L. S. (1962). College admissions and the stability of marriage. The American mathematical monthly , 69(1):9--15

1962
[10]

Goto, M., Iwasaki, A., Kawasaki, Y., Yasuda, Y., and Yokoo, M. (2014). Improving fairness and efficiency in matching with distributional constraints: An alternative solution for the japanese medical residency match

2014
[11]

E., Kojima, F., Yenmez, M

Hafalir, I. E., Kojima, F., Yenmez, M. B., and Yokote, K. (2022). Design on matroids: Diversity vs. meritocracy. arXiv preprint arXiv:2301.00237

2022 arXiv
[12]

E., Yenmez, M

Hafalir, I. E., Yenmez, M. B., and Yildirim, M. A. (2013). Effective affirmative action in school choice. Theoretical Economics , 8(2):325--363

2013
[13]

Hatfield, J. W. and Milgrom, P. R. (2005). Matching with contracts. American Economic Review , 95(4):913--935

2005
[14]

Imamura, K. (2020). Meritocracy versus diversity. Unpublished manuscript

2020
[15]

and Kojima, F

Kamada, Y. and Kojima, F. (2015). Efficient matching under distributional constraints: Theory and applications. American Economic Review , 105(1):67--99

2015
[16]

and Kojima, F

Kamada, Y. and Kojima, F. (2017). Stability concepts in matching under distributional constraints. Journal of Economic theory , 168:107--142

2017
[17]

and Kojima, F

Kamada, Y. and Kojima, F. (2018). Stability and strategy-proofness for matching with constraints: A necessary and sufficient condition. Theoretical Economics , 13(2):761--793

2018
[18]

Kojima, F. (2012). School choice: Impossibilities for affirmative action. Games and Economic Behavior , 75(2):685--693

2012
[19]

Kojima, F., Tamura, A., and Yokoo, M. (2018). Designing matching mechanisms under constraints: An approach from discrete convex analysis. Journal of Economic Theory , 176:803--833

2018
[20]

Roth, A. E. (1984). The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of political Economy , 92(6):991--1016

1984
[21]

Roth, A. E. (1985). The college admissions problem is not equivalent to the marriage problem. Journal of economic Theory , 36(2):277--288

1985
[22]

Roth, A. E. and Peranson, E. (1999). The redesign of the matching market for american physicians: Some engineering aspects of economic design. American economic review , 89(4):748--780

1999
[23]

and Yenmez, M

S \"o nmez, T. and Yenmez, M. B. (2022). Affirmative action in india via vertical, horizontal, and overlapping reservations. Econometrica , 90(3):1143--1176

2022
[24]

Tomoeda, K. (2018). Finding a stable matching under type-specific minimum quotas. Journal of Economic Theory , 176:81--117

2018

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Abdulkadiro g lu, A. (2005). College admissions with affirmative action. International Journal of Game Theory , 33:535--549

work page 2005

[2] [2]

and S \"o nmez, T

Abdulkadiro g lu, A. and S \"o nmez, T. (2003). School choice: A mechanism design approach. American economic review , 93(3):729--747

work page 2003

[3] [3]

Akin, S. (2021). Matching with floor constraints. Theoretical Economics , 16(3):911--942

work page 2021

[4] [4]

and Turhan, B

Ayg \"u n, O. and Turhan, B. (2020). Dynamic reserves in matching markets. Journal of Economic Theory , 188:105069

work page 2020

[5] [5]

and Yildiz, K

Do g an, B. and Yildiz, K. (2023). Choice with affirmative action. Management Science , 69(4):2284--2296

work page 2023

[6] [6]

and Yenmez, M

Echenique, F. and Yenmez, M. B. (2015). How to control controlled school choice. American Economic Review , 105(8):2679--2694

work page 2015

[7] [7]

E., Yenmez, M

Ehlers, L., Hafalir, I. E., Yenmez, M. B., and Yildirim, M. A. (2014). School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic theory , 153:648--683

work page 2014

[8] [8]

and Troyan, P

Fragiadakis, D. and Troyan, P. (2017). Improving matching under hard distributional constraints. Theoretical Economics , 12(2):863--908

work page 2017