| paper | A Fine-Grained View on Stable Many-To-One Matching Problems with Lower and Upper Quotas |
| authors | N. Boehmer, Klaus Heeger |
| venue | WINE 2020 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite hospital set \(H\), prescribed \(H_{\mathrm{open}}\subseteq H\), rational population-scale quotas \(0\le \ell_h\le u_h\), and rational type masses \(\mu_t\ge0\) summing to \(1\), where each type \(t\) has a strict preference order over acceptable hospitals, decide whether there are masses \(x_{t,h},x_{t,\bot}\ge0\) with \(\sum_{h\in H}x_{t,h}+x_{t,\bot}=\mu_t\), zero mass at \(H\setminus H_{\mathrm{open}}\), and \(\ell_h\le\sum_t x_{t,h}\le u_h\) for each \(h\in H_{\mathrm{open}}\), such that every undersubscribed open hospital \(h\) satisfies \(\sum_t\sum_{g\in H\cup\{\bot\}:\,h\succ_t g}x_{t,g}=0\) and every closed hospital satisfies \(\sum_t\sum_{g\in H\cup\{\bot\}:\,h\succ_t g}x_{t,g}<\ell_h\).
A large annual applicant population partitioned into finitely many complete resident types \(t\), with \(\mu_t\) the cohort mass; \(x_{t,h}\) assigns mass to programmes, quotas are per-capita fractions, hospitals are indifferent, and the objective is feasibility of a stable assignment.
The remaining modelling concern is that per-capita lower and upper quotas may be artificial for the paper's fixed-capacity hospital stories; the proponent gives a plausible cohort scenario but not a concrete application validating that scaling.
fatal: False
It covers Theorem 3 and the paper's diagnosis that assigning mass to a prescribed \(H_{\mathrm{open}}\) is the source of \mathrm{HALUQ} hardness; it leaves endogenous hospital opening, \mathrm{HRLUQ} with hospital preferences, ties, and the other parameterized results untouched.
The strongest positive case is built around Theorem 3, proved in this paper. I would use it as the lead anchor rather than trying to mirror the entire paper.
Theorem 3 states that the following problem for \(\HALUQ\) is NP-complete: given a set \(H_{\open}\) of hospitals, decide whether there is a stable matching in which exactly the hospitals in \(H_{\open}\) are open. The result remains NP-complete even when \(|H_{\open}|=4\), every resident accepts at most five hospitals, every hospital has lower quota at most two, and one knows in advance that any stable matching, if one exists, opens exactly \(H_{\open}\). The theorem is proved in the paper, by reduction from Independent Set on \(3\)-regular graphs.
The corresponding continuous problem is:
\[ \textsc{Fixed-Portfolio-}\HALUQ_\infty. \]
An instance consists of a finite set of hospitals \(H\), a prescribed set \(H_{\open}\subseteq H\) of hospitals that must be open, rational lower and upper capacity fractions \(\ell_h\le u_h\), and a finite set \(T\) of resident types. A type \(t\in T\) specifies an acceptance set and a strict preference order over hospitals; all residents of type \(t\) are identical for every purpose of the problem. The society is given by rational masses \(\mu_t\ge0\), with \(\sum_t\mu_t=1\). Hospitals have no preferences over residents, exactly as in \(\HALUQ\).
A solution is an assignment of resident mass \(x_{t,h}\ge0\), together with unmatched mass \(x_{t,\bot}\), satisfying
\[ \sum_{h\in H}x_{t,h}+x_{t,\bot}=\mu_t \]
for every type \(t\). Hospitals outside \(H_{\open}\) receive zero mass, while each \(h\in H_{\open}\) receives mass
\[ \ell_h\le \sum_t x_{t,h}\le u_h. \]
Every infinitesimal resident still receives one integral bundle—one hospital or the outside option. Only the aggregate assignment of an indistinguishable type is fractional. Thus this is a continuous population model, not a lottery over outcomes.
Stability is the direct mass version of the paper’s blocking definitions. If an open hospital \(h\) is undersubscribed, then no positive mass may be assigned to an option worse than \(h\):
\[ \sum_{g:\,h\succ_t g}x_{t,g}=0. \]
Otherwise that mass would contain a resident who can form a blocking pair with \(h\). For a closed hospital \(h\), define
\[ B_h(x)=\sum_t\sum_{g:\,h\succ_t g}x_{t,g}. \]
A blocking coalition exists exactly when \(B_h(x)\ge \ell_h\), since a nonatomic population can select a coalition of mass \(\ell_h\). Hence stability requires
\[ B_h(x)<\ell_h \]
for every closed hospital.
This is a natural high-multiplicity regime. Think of a large annual population of applicants divided into cohorts with identical eligibility and ranked preferences over programmes, campuses, or activities. The number \(N\) of applicants may be very large, while the number \(\tau=|T|\) of preference-and-eligibility types is modest. The four hospitals in \(H_{\open}\) can represent the programmes currently funded or operating; the remaining hospitals are possible but closed programmes. Since \(\HALUQ\) already assumes that hospitals are indifferent among applicants, the mirror does not erase any hospital-side preference structure present in the anchor. It simply replaces \(N\) named, indistinguishable applicants by their population masses.
I would expect this continuous problem to be in Class A. The reason is exactly the phenomenon Theorem 3 exposes. Once \(H_{\open}\) is fixed, the only remaining combinatorial issue is which open hospitals are full. Guess a subset \(F\subseteq H_{\open}\) of full hospitals. For \(h\in F\), impose
\[ \sum_t x_{t,h}=u_h; \]
for \(h\in H_{\open}\setminus F\), impose
\[ \ell_h\le\sum_t x_{t,h}<u_h. \]
All blocking-pair constraints for undersubscribed hospitals and all blocking-coalition constraints for closed hospitals are linear inequalities in the \(x_{t,h}\). Strict inequalities can be handled by maximizing a common slack variable. Thus each guess gives a linear-programming feasibility problem. Since Theorem 3 has \(|H_{\open}|=4\), only \(2^4\) full/undersubscribed patterns need be considered. The continuous mirror is therefore solvable in polynomial time in the explicit type-and-hospital description.
That outcome is not a failure to mirror the paper’s question. It is the precise question the paper makes interesting. The authors explain that \(\HALUQ\) remains hard even when the open hospitals are known because, with named indivisible residents, there may be exponentially many ways to decide which residents fill a popular hospital. In the continuum, that choice becomes a mass allocation governed by linear inequalities. The question is whether the discrete NP-hardness was caused by population granularity; this mirror tests exactly that.
The weakest point is that Theorem 3’s particular reduction almost certainly does not transfer as a hardness reduction. Its Independent Set choice is encoded by assigning individual residents integrally to \(h^+\), \(h^-\), or edge hospitals. A continuous mass of one type can be divided among those destinations, potentially destroying the graph encoding. An opponent could therefore say that the mirror has removed the source of hardness. My answer is that this is precisely what continuization is meant to test: the underlying assignment and stability notions remain, while only high-multiplicity divisibility changes. The case is strongest in the regime where cohort identity is genuinely meaningful; it would be weaker for populations dominated by idiosyncratic priorities or one-off applicants.
This mirror covers Theorem 3 and the paper’s diagnosis that, for \(\HALUQ\), the difficult part is assigning residents to a prescribed set of open hospitals. It does not claim to continuize the paper’s full \(\HRLUQ\) landscape, endogenous hospital opening, or hospital-side preferences.
It also raises useful follow-up questions: whether \(\HALUQ_\infty\) remains tractable when the set of open hospitals is endogenous; how accurately a continuous solution can be rounded to a finite high-multiplicity population; and whether adding finitely many hospital priority classes leads to an LP, an integer program, or a genuinely continuum-specific hard problem.
The strongest negative case is that the proponent has not really mirrored the paper’s hardness family; they have replaced its only difficult feature with convexity. In Theorem 3, the graph choice is encoded by indivisible residents: two endpoint residents either jointly fill an edge hospital or they do not. After scaling the instance to a population of mass \(1\), the crucial quotas of two disappear as \(2/N\), and a type’s mass can be split across several hospitals. The blocking-coalition gadget therefore loses exactly the atomic structure that carries the Independent Set reduction. The resulting LP is not a softened version of the theorem’s instances so much as a different feasibility problem.
That objection is not enough, however. The programme explicitly asks whether this population granularity is the source of the discrete hardness. A failed reduction is evidence for a Class A result, not evidence that the question is meaningless. The proposed scenario—large cohorts of applicants with identical eligibility and preferences—is a legitimate high-multiplicity regime. The theorem’s residents need not themselves be repeated types for the continuous question to be sensible; the same \(\textsc{HALUQ}\) model can describe repeated cohorts.
A stronger objection is that the proposed mirror is computationally too thin. Once \(H_{\open}\) is prescribed and hospitals have no preferences, the mass assignment is essentially a small transportation LP. With \(|H_{\open}|=4\), even the full-versus-undersubscribed case distinction is constant-sized. Thus the mirror may tell us only that divisibility removes an assignment gadget, without exposing the column-generation, pricing, or other structural phenomena that motivate the programme.
But this also does not defeat it. The paper’s Theorem 3 specifically identifies indivisible assignment to a known portfolio as the source of NP-hardness. Asking whether that hardness disappears under high multiplicity is exactly the relevant computational comparison. A simple Class A answer remains a meaningful answer, particularly because the discrete problem is hard under severe restrictions while the continuous one is governed by explicit mass constraints.
The only genuinely serious reservation is modelling: the continuous version needs quotas that scale with population, whereas the reduction uses small absolute quotas such as \(2\). If the application is a fixed-capacity collection of hospitals serving an increasingly large population, scaling may be artificial and the continuum limit may indeed be uninformative. Yet a better scenario exists—programmes or activity cohorts whose capacities and viability thresholds are fixed fractions of a large annual population—and the paper’s one-sided preferences make repeated applicant types entirely credible there.
So the universal negative case does not hold. Theorem 3 is a genuine named computational anchor, its objective depends only on aggregate assignment rather than identity, and a sensible high-multiplicity regime exists. The proposed mirror may be modest and its direct relation to the reduction is weak, but that is a criticism of ambition, not a reason to reject it. My honest negative verdict is therefore weak: this anchor survives.
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.