| paper | Couples Can Be Tractable: New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples |
| authors | Gergely Csáji, David Manlove, Iain McBride, James Trimble |
| venue | IJCAI 2024 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 12
statement extracted from the paper’s text layer
Given disjoint institution sets \(H_1,H_2\), rational masses \(\mu_k\) of complete couple types, optional single-doctor type masses, rational capacities \(q_h\), sub-responsive and sub-complete acceptable pairs, and strict priorities over type classes, find a mass matching \(y_{k,h_1,h_2}\) and \(x_{s,h}\) satisfying capacities and feasibility, with no positive-mass blocking deviation under the paper's HRC predicate generalized to priority classes.
A finite-type dual-market society with masses \(\mu\), capacities \(q\), and mass-transfer variables \(y_{k,h_1,h_2}\) and \(x_{s,h}\); the objective is to decide existence of, and construct, a stable mass matching under positive-mass blocking.
The paper's strict named-doctor priorities do not supply a type-level tie convention or a theorem lifting positive-mass stability back to strict finite HRC instances.
fatal: False
The mirror covers Corollary 12 and its HRC-DUAL existence and polynomial-time solvability result; it leaves Theorem 4, Theorems 14–16, and the remaining structural corollaries unassessed.
My strongest case is a qualified yes. The best mirror is a high-multiplicity dual-market version of the paper’s own student-allocation interpretation.
The lead anchor is Corollary 12, proved in this paper as a consequence of Theorem 10: “HRC-DUAL is solvable in polynomial time if each couple is sub-responsive and sub-complete. Furthermore, there always exists a stable matching.”
The scenario is exactly one suggested by the authors. A “couple” is a student applying simultaneously to a university programme and an internship or company. In a large national cohort, many students can share the same complete type: the same ranking of universities, ranking of companies, acceptable pairs, joint preference relation, and priority class at every institution. The mass \(\nu_k\) of type \(k\) is the fraction of students with that profile. Universities and companies have capacities measured as fractions of the cohort, so supply scales with population. A plausible regime is tens of thousands of students and perhaps tens or hundreds of recurring preference-and-priority types.
Call the problem Typed Dual-Market HRC\(_\infty\). An instance consists of disjoint hospital sets \(H_1\) and \(H_2\), rational capacities \(q_h\), rational masses \(\nu_k\) of couple types, and optionally rational masses \(\mu_s\) of single-doctor types. Every couple type \(k\) has two individual preference orders, a joint preference order, and an acceptable-pair set \(\mathcal A_k\subseteq (H_1\cup\{\varnothing\})\times(H_2\cup\{\varnothing\})\) satisfying sub-responsiveness and sub-completeness. Every hospital or company has a strict priority order over the relevant type classes. Priority information is part of the type, as required by the programme’s definition of high multiplicity.
A solution is a collection of rational masses \(x_{s,h}\) and \(y_{k,h_1,h_2}\). The variables obey \(\sum_h x_{s,h}\le\mu_s\), \(\sum_{(h_1,h_2)\in\mathcal A_k}y_{k,h_1,h_2}\le\nu_k\), and the capacity constraints
\( \sum_s x_{s,h}+\sum_{k,(h_1,h_2):\,h\in\{h_1,h_2\}}y_{k,h_1,h_2}\le q_h. \)
The solution is stable if there is no \(\delta>0\), type, and currently occupied assignment from which \(\delta\) mass can move to a strictly preferred acceptable hospital or hospital pair, with every newly used institution either having positive spare capacity or being able to replace positive mass of strictly lower-priority assigned types. For couples, the case distinction is exactly Definition 1 of the paper, with cardinalities replaced by masses and the deviation taken from a currently occupied mass cell. The output is any stable mass matching.
This is not treating a couple as two independently splittable agents: \(y_{k,h_1,h_2}\) moves whole couple mass to a joint pair. It is the high-multiplicity encoding of many indistinguishable copies. If all masses and capacities have common denominator \(D\), multiplying by \(D\) produces a finite HRC-DUAL instance with \(D\nu_k\) copies of each couple type. Conversely, aggregating any such clone instance recovers \(x\) and \(y\). Thus rational-clone equivalence is available, subject to the usual within-type priority convention.
I expect this problem to be Class A. The paper’s reduction to Stable Fixtures already has a finite gadget structure; large multiplicities only become capacities on type vertices. The natural continuous question is whether that reduction admits a type-level capacitated stable-fixtures or flow formulation running in time polynomial in \(|H|\), \(\tau\), and the bit length of the rational masses, rather than in the expanded number of students. This is a genuine computational question, not a restatement of the paper’s algorithm. The paper supplies the structural reason to expect tractability, while the continuous formulation supplies the high-multiplicity regime.
Further questions include whether the compressed algorithm can be made strongly polynomial, whether irrational masses admit a well-defined limiting stability notion, and exactly where tractability fails when the dual-market or sub-completeness assumptions are relaxed.
A second, weaker but still credible mirror uses Theorem 4, proved here: for sub-responsive and sub-complete couples, a stable matching exists after changing every hospital capacity by at most \(1\), and the modified capacities and matching can be found in \(O(m)\) time.
Call this Typed Near-Feasible HRC\(_\infty\). The instance is the same typed HRC model, now without the dual-market restriction. Normalize the population to total mass \(1\), let \(q_h\) be rational normalized capacities, and let \(D\) be a common denominator for all type masses and capacities. The problem is to output a mass matching \(x\) and modified capacities \(\bar q\) satisfying \( |\bar q_h-q_h|\le 1/D \) for every hospital, such that \(x\) is stable with respect to \(\bar q\). Equivalently, one can minimize \( \|\bar q-q\|_\infty \); Theorem 4 predicts an optimum of at most \(1/D\) in this domain.
The \(1/D\) tolerance is exactly one individual capacity unit after clearing denominators, so this preserves the paper’s near-feasibility guarantee rather than introducing an arbitrary fractional relaxation. Its expected classification is also Class A: the proof’s half-integral Stable Fixtures construction suggests a type-level continuous rounding or flow formulation. The main open issue is whether the paper’s per-agent rounding argument survives compression without making the running time depend pseudo-polynomially on \(D\).
The authors should recognize both mirrors. The first is their own university-plus-company application, preserving two-sided priorities, coupled assignments, capacities, and stability. The second preserves their exact near-feasibility objective, with the discrete \( \pm1 \) becoming \( \pm1/D \) in normalized units. I am not claiming that the paper proves either compressed algorithm; these are continuous research problems anchored in its proved results.
My weakest point is identity inside priority lists. The paper ranks named doctors strictly, whereas a high-multiplicity type model makes clones indistinguishable and therefore induces ties within a type. If idiosyncratic tie-breaking affects stability, it must be included in the type, potentially making \(\tau\) as large as the population and destroying the gain. Also, an atomless individual has zero mass, so “blocking” must be defined as a positive-mass version of the paper’s deviation predicate. Those are genuine extensions, not details to hide. The case survives because the paper’s dual-market application has a natural cohort interpretation, and rational cloning gives a precise bridge back to finite HRC instances. I would therefore cover Corollary 12 and Theorem 4, but not claim a mirror for Theorems 14–16 without separately checking whether their hardness reductions retain repeated types.
The strongest negative case is that both anchors silently replace the paper’s strict, identity-sensitive matching problem with a different one: priority classes and fractional mass assignments. That is a serious modelling change, not a routine replacement of counts by weights.
Corollary 12, via Theorem 10, is the stronger anchor. HRC hospitals rank named doctors strictly. If two doctors are genuinely the same type, their relative position in every hospital’s strict list is not determined. If that position is retained, each copy must carry an identity or rank index, so the number of types grows with the population and the compression disappears. If it is discarded, the hospital has ties. But weak, strong, and super-stability under ties are different predicates, and the paper’s blocking definition uses strict comparisons such as \(c\succ_h r\). A mass vector cannot record which copy of a type occupies a post; with one capacity-one hospital, assigning the higher-priority copy is stable while assigning the lower-priority copy may create a blocking pair, although both assignments have the same type masses.
The proposed “within-type priority convention” does not remove this issue. It requires a new global tie-breaking or lifting theorem showing that every stable type-level allocation can be realized by one finite strict HRC instance, including the two endpoint priorities of every couple. Different hospitals may order the same clones differently, so this is not automatic. The natural repair—priority classes with a declared tie-stability notion and positive-mass blocking—is author-recognizable, but it is a new HRC-with-ties problem. The Stable Fixtures reduction in Theorem 10 does not itself establish that its strict, unit-agent gadgets survive this change.
Theorem 4 has a more fundamental problem. Its guarantee of changing each capacity by at most one is a rounding statement about an individual seat. After normalization, the proposed tolerance \(1/D\) depends on the chosen finite population scale \(D\), not on the society distribution \(\mu\) or capacities \(q\). The same \((\mu,q)\) can arise from \(D\) clones or \(kD\) clones, yielding different tolerances \(1/D\) and \(1/(kD)\). Keeping \(D\) makes this a finite-resolution high-multiplicity family; removing \(D\) makes the tolerance \(0\), producing an exact fractional stable-matching problem rather than the paper’s near-feasible integral problem.
That distinction matters because the proof’s essential operation is to round a half-integral Stable Fixtures solution by assigning each named doctor its best positive edge and then changing a hospital capacity by one. In an atomless model, a type can be split across several assignments, so \(y_{k,h_1,h_2}\) describes a distribution of couple copies rather than an actual matching of couples. The paper’s per-agent rounding argument has then vanished. A better formulation with an explicit resolution parameter \(\varepsilon\) is coherent, but it is no longer a population-only continuum and its rational-clone bridge merely reconstructs the finite problem.
The honest limitation of this negative case is Corollary 12. The university-plus-internship interpretation is explicitly supplied by the authors, and a large cohort with repeated preference and priority classes is genuinely plausible. If one accepts priority ties as the natural high-multiplicity version, then Typed Dual-Market HRC\(_\infty\) is a legitimate new computational problem. The objections above show that it needs a precise stability and lifting theory; they do not prove that no worthwhile mirror exists.
Thus the strongest defensible negative verdict is: reject Typed Near-Feasible HRC\(_\infty\) as a direct mirror, and treat the dual-market proposal as an extension requiring substantial semantic work. I cannot honestly sustain the universal claim that Corollary 12 has no worthwhile continuous mirror in any scenario.
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.