| paper | d4-conf-sagt-2022-0010 |
| 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: The first stated approximation factor remains NP-hard to attain; the second remains hard to attain under UGC. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 13
Given finite resident and hospital type sets with positive rational masses \(\rho_i,\eta_j\), tied and incomplete rankings over types, mutual acceptability, and a common quota pair \(1\le\ell\le u\), find a maximum-score stable flow \(x_{ij}\ge0\). Require \(\sum_j x_{ij}\le\rho_i\), \(q_j=\sum_i x_{ij}\le u\eta_j\), and \(x_{ij}=0\) for unacceptable pairs; for each acceptable pair define \(D_{ij}=\rho_i-\sum_{j':j'\succeq_i j}x_{ij'}\) and \(A_{ij}=u\eta_j-q_j+\sum_{k:i\succ_j k}x_{kj}\), and require \(D_{ij}=0\) or \(A_{ij}=0\). Maximize \(\sum_j\eta_j\min\{1,q_j/(\ell\eta_j)\}\), with complexity measured in the type support and input bit length.
A two-sided nonatomic matching market with rational masses of resident and hospital types, type-level flows \(x_{ij}\), capacity \(u\eta_j\) for each hospital type, and capped satisfaction based on each type’s average occupancy.
The proposed objective caps type-average occupancy, whereas the paper sums capped occupancy separately for each hospital; the proponent gives no realization argument showing that this score matches a balanced cohort of stable individual hospitals.
fatal: False
The mirror covers Theorem 13’s uniform-model inapproximability results under UGC and \(P\ne NP\); it leaves the approximation guarantees in Theorems 6–12 and the other model-specific results alone.
My strongest case is one mirror of the paper’s Theorem 13, its hardness result for the uniform model. I would call the continuous problem Uniform Type-Mass HRT-MSLQ.
Consider a large residency market with many residents and many hospital programs, but relatively few complete profiles. Resident types might encode specialty, credentials, location constraints, and a ranking of program classes; hospital types might encode service, location, quota, and a ranking of resident classes. Within a type, agents are interchangeable for everything the model uses. A plausible regime is \(N\) residents and hospitals, with \(N\) much larger than the numbers of resident and hospital types, \(\tau_R\) and \(\tau_H\). This preserves the paper’s two-sided preferences, ties, incomplete acceptability, quotas, stability, and lower-quota objective. It continuizes the population; each unit of resident mass still receives one hospital type.
An instance has finite resident and hospital type sets \(\mathcal R,\mathcal H\), binary-rational masses \(\rho_i,\eta_j\), and a common positive quota pair \([\ell,u]\) for every hospital type, with \(1\le\ell\le u\). Normalize resident mass so \(\sum_i\rho_i=1\); hospital masses use the same population scale. Each type has a possibly tied and incomplete ranking of the opposite type set, with mutual acceptability. Let \(x_{ij}\ge0\) be the mass of resident type \(i\) assigned to hospital type \(j\), and \(q_j=\sum_i x_{ij}\). Require \(\sum_jx_{ij}\le\rho_i\) and \(q_j\le u\eta_j\), and set \(x_{ij}=0\) for unacceptable pairs. A flow partitions each type cohort across destinations; it does not give an individual a fractional assignment.
Here is a precise mass version of the paper’s stability condition. For an acceptable pair \((i,j)\), define
\[
D_{ij}(x)=\rho_i-\sum_{j':\,j'\succeq_i j}x_{ij'}
\quad\text{and}\quad
A_{ij}(x)=u\eta_j-q_j+\sum_{k:\,i\succ_j k}x_{kj}.
\]
The first quantity is resident mass unmatched or assigned strictly worse than \(j\). The second is hospital capacity slack plus mass assigned to resident types that \(j\) ranks below \(i\). Require that no pair has both quantities positive: \(D_{ij}(x)=0\) or \(A_{ij}(x)=0\) for every acceptable \((i,j)\). Thus a positive mass of residents cannot strictly improve at the same time as a positive capacity or replacement opportunity exists for their desired hospital type.
The objective is to maximize
\[
\sum_{j\in\mathcal H}\eta_j\min\!\left\{1,\frac{q_j}{\ell\eta_j}\right\},
\]
omitting zero-mass types. This is the total lower-quota satisfaction per population scale, using the type-level average occupancy; it is the natural fractional score for a large cohort of identical hospitals. The continuous problem is: given the type masses, preferences, and quotas, find an optimal stable flow \(x\). Its size is measured in \(\tau_R,\tau_H\), the acceptable type pairs, and the input bit length.
The anchor is Theorem 13, proved in this paper’s §5.1. It states that HRT-MSLQ in the uniform model, where \(\theta=u/\ell\), is inapproximable within \(1+\theta/3-\epsilon\theta^2\) for every \(\epsilon>0\) under UGC, and within \(1+\frac{2-\sqrt2}{3}\theta-\epsilon\theta^2\) for every \(\epsilon>0\) unless P=NP. The proof is given here by reduction from Vertex Cover with a perfect matching; it uses the reduction in Proposition 16 and hardness results for that source problem, including results cited from elsewhere. The proposed mirror asks whether those approximation barriers persist for the stated type-mass optimization problem.
My tentative expectation for the continuous problem is tractable, as a Class A candidate. Mass flows can split across types, and the objective has a simple piecewise-linear form; if the exact mass-stability conditions admit a compact linear description, maximizing this score is an LP. That is a direction to investigate, not a result established by Theorem 13. The concrete first question is whether the no-block condition above has such an exact LP characterization. Further questions include whether the optimum is computable in time polynomial in the type support and bit length, whether a discrete optimal or stable flow can be rounded with bounded loss, and which parameter controls any remaining hardness.
The mirror covers Theorem 13’s uniform-model hardness only. It does not claim that the paper’s hardness factor transfers, nor does it mirror the approximation guarantees for Triple Proposal.
The weakest point is that the hardness reduction encodes a graph through detailed agent preferences. Preserving that information may require a separate type for nearly every gadget, making \(\tau_R+\tau_H\) grow with the construction; meanwhile, allowing mass to split may destroy the reduction’s integrality. So this is a credible continuous version of the authors’ optimization problem, but the paper’s theorem gives no answer about its complexity. That gap is also the substantive question the mirror would put to a prover.
Theorem 13 is a real computational anchor, so the objection cannot be that the paper has nothing to continuize. The strongest case against it is that its hardness is encoded in the fine structure of named agents’ preference lists, while a useful high-multiplicity model needs agents with the same complete preferences to become interchangeable types.
That creates a dilemma for this anchor. Preserve the reduction’s preference distinctions exactly, and the type support tracks the graph encoded by the reduction; making the electorate larger by cloning those types does not compress the graph. Coarsen the preferences to rankings over resident and hospital classes, and the model changes at the point that carries the hardness: tied cohorts can split across assignments, so the integral choices represented by the Vertex Cover construction are no longer preserved. The proponent’s flow problem is still a coherent research question, but Theorem 13 does not tell us that it is a mirror of the theorem’s hard instances.
There is also a modelling gap in the proposed flow formulation. The paper scores each hospital separately, and stability is checked against each hospital’s occupants. Type-level totals \(q_j\) do not by themselves record how residents are distributed among copies of a hospital type. The displayed score and blocking condition therefore need a justification that aggregate flows can be realized across individual hospitals while preserving both stability and the per-hospital lower-quota score. A stronger mirror could track a distribution of hospital occupancies, but that adds a new layer of state and may restore much of the structure the type aggregation was meant to remove.
A more conventional continuum matching model keeps a finite set of hospitals and makes the resident side a continuum. Such models already study stable allocations analytically using supply and demand; Azevedo and Leshno give one example. That is not a prior-art collision with this paper’s computational optimization, but it underscores that the proposed two-sided type-mass model is a substantive modelling choice, not the automatic limit of HRT-MSLQ. [Azevedo and Leshno](https://www.microsoft.com/en-us/research/publication/a-supply-and-demand-framework-for-two-sided-matching-markets/)
These points weaken the connection between Theorem 13 and the proposed mirror; they do not establish that no useful mirror exists. A fixed set of plausible preference classes with mass assignments could still be worth studying. The honest negative case is therefore limited: this paper’s strongest anchor does not yet make that case compelling, but the claim that no scenario could yield a worthwhile mirror goes beyond what the paper supports.
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.