| paper | d4-conf-ijcai-2022-0418 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even without hospital-specific expansion limits · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
Given finitely many hospitals, a finite support \(T\) of resident types with rational masses \(\mu_t\), complete resident rankings and hospital priority classes, rational per-capita baseline capacities, an expansion budget and optional hospital limits, and a welfare threshold \(K\), does there exist a feasible real expansion vector whose resident-proposing mass-DA assignment has total resident rank at most \(K\)?
Residents are represented by types carrying mass \(\mu_t\); each type includes its complete preferences and priority profile. The decision variables are real per-capita capacity expansions and assignment flows \(x_{th}\); mass-DA may split a type at a hospital’s priority cutoff, while each individual still receives one integral assignment. The objective is to meet the threshold on \(\sum_{t,h} r_t(h)x_{th}\) under the expanded capacities and total expansion budget.
The paper does not establish that large matching markets have small support over complete resident preference and hospital-priority profiles; those joint profiles may be nearly as numerous as residents, and proportional capacity expansion also needs an application-specific rationale.
fatal: False
The mirror covers Proposition 1’s capacity-expansion decision hardness, which the paper attributes to Bobbio et al.; it leaves the UCT search guarantees, tree representations, and empirical anytime performance unmirrored.
The lead anchor is Proposition 1 (“Hardness result,” cited to Bobbio et al. (2021)). It says that the decision version of the paper’s capacity-expansion problem is NP-complete even without hospital-specific expansion limits \(b_h\). In that problem, one chooses integer extra seats within a total budget and a matching that respects the expanded quotas and stability constraints, seeking total resident rank at most a given threshold. Abe, Komiyama, and Iwasaki cite this result; they do not prove it. For each fixed expansion, resident-proposing DA gives the minimum-rank stable matching, so the hardness is in choosing the expansion.
My lead mirror is Type-Mass Residency Capacity Expansion. Its input is a finite set of hospitals \(H\), a finite support \(T\) of resident types, rational masses \(\mu_t>0\) summing to \(1\), and each type’s complete hospital ranking. Each hospital has a ranking over resident types; a type includes the hospital-priority class, so people grouped together are identical in every respect relevant to this problem. The input also gives rational per-capita baseline capacities \(\bar q_h\), an expansion budget \(\bar B\), optional per-hospital limits \(\bar b_h\), and a rational welfare threshold \(K\). Capacities are normalized by population size: a discrete market with \(N\) residents and \(n_t\) residents of type \(t\) has \(\mu_t=n_t/N\) and capacity \(q_h/N\).
The decision variable is a real expansion vector \(y\), with \(0\le y_h\le\bar b_h\) and \(\sum_h y_h\le\bar B\); omit the upper bounds when there are no hospital-specific limits. For each \(y\), define the outcome by resident-proposing mass-DA: resident mass applies down its ranking, and each hospital holds up to \(\bar q_h+y_h\) mass in priority order, rejecting any excess to continue proposing. If a cutoff splits a type, the flow records the fraction of that type held. An outside option can be included last in every ranking and given unlimited capacity. Write \(x^{DA}_{th}(y)\) for the mass of type \(t\) assigned to hospital \(h\), and \(r_t(h)\) for its rank. The question is whether some feasible \(y\) gives
\[
\sum_{t\in T}\sum_{h\in H\cup\{\bot\}} r_t(h)x^{DA}_{th}(y)\le K.
\]
A solution is that expansion vector together with its DA mass assignment; each individual still receives at most one integral assignment. The fractional \(x\) records how much of a type receives each assignment.
A plausible high-multiplicity setting is a large centralized residency match whose applicants use a finite menu of rank-list templates and whose programs use a small number of priority tiers. The population can then be much larger than the number \(\tau=|T|\) of template-and-tier combinations, while the hospitals remain finite. The paper’s JRMP data does not establish that this regime holds there; the scenario would need to be supported independently. The mirror nevertheless preserves the paper’s central question—allocate extra program capacity to improve resident rank under stable DA—and the type assumptions are explicit. Population mass is the continuized object; the assignment flow is its aggregate description.
I expect Class A, provisionally: replacing indivisible seat counts and individual residents with mass variables may yield a polynomial type-flow or stability formulation in \(H,\tau,L\), where \(L\) is the input bit length. That is a conjectured route, not a result of this paper. The key test is whether the coupling between continuous capacities and DA cutoffs admits a compact exact formulation, especially with priority ties. If it leaves an exponential partition or a hard disjunction, the mirror could instead be continuum-specifically hard. Proposition 1’s discrete NP-completeness does not settle this: fractional expansions and type flows change the feasible set, so hardness does not automatically transfer.
The next questions are whether mass-DA can be evaluated exactly in time polynomial in \(H,\tau,L\); whether the joint expansion problem has a polynomial-size formulation or efficient separation method; and how its solution rounds to a large finite match with a controlled per-capita welfare loss.
The weakest point is the regime assumption. Exact shared rank lists and priority classes may be uncommon in systems where programs rank applicants individually. The paper’s authors should recognize the capacity-and-stable-DA question, but may regard the priority ties and continuously scaled seat supply as a material change. This case covers Proposition 1’s capacity-expansion hardness question only; it does not mirror the paper’s UCT search method or claim that the discrete algorithmic results become continuous results.
Proposition 1 is a real computational anchor, even though it imports Bobbio et al.’s NP-completeness result rather than proving it here. Its continuous mirror is also well-defined. The strongest case against it is that the paper gives little reason to believe a useful high-multiplicity regime exists for the matching problem it studies.
A resident’s complete type must encode a rank list and the relevant priority class at every hospital. In actual residency matches, those lists and hospital rankings can be highly individualized. Grouping residents by a few preference templates is insufficient if their priority profiles across hospitals still vary widely: the joint profiles may leave nearly as many types as residents. The proposed finite-template, finite-tier market avoids that problem by assumption, but the paper’s JRMP data does not establish that such a regime occurs. That leaves a narrow application whose suitability depends on evidence outside the paper.
The capacity scaling adds another substantial assumption. The experiments allocate 10 or 30 extra seats, while a nonzero normalized expansion budget in a growing population requires \(B_N/N\) to stay positive. With fixed \(B_N\), the normalized feasible expansion set collapses toward zero; studying its effects would be a separate question about vanishing capacity changes. Proportional expansion may make sense for some systems, but the paper does not motivate it for residency programs.
These concerns do not rule out the mirror. School choice, which the paper also names, could plausibly have recurring preference templates, shared priority categories, and staffing that scales with enrollment. That is a credible rescue scenario, and the authors might recognize its capacity-expansion question as theirs. So the negative case is weak against the universal claim: it shows that the paper itself supplies little evidence for a suitable regime, but it cannot establish that no worthwhile scenario exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.