| paper | d4-conf-atal-2016-0305 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-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}\)-complete, and hence \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given hospitals with qualities \(q_j\), per-patient costs \(c_j\), a per-capita budget \(b\), and a society described by \(\tau\) patient-value types \(v_t\) with rational masses \(\mu_t\), compute a budget-feasible stable assignment maximizing average social welfare. The decision variables are masses \(x_{tj}\ge 0\) assigned from each type to each hospital and common waiting times \(w_j\ge 0\); require \(\sum_j x_{tj}=\mu_t\), \(\sum_{t,j}c_jx_{tj}\le b\), and every hospital receiving positive mass from type \(t\) maximizes that type's nonnegative utility \(v_tq_j-w_j\).
A finite-support society of patient-value types with masses \(\mu_t\); each type's mass may be split among hospitals, while all patients assigned to a given hospital share its waiting time. Minimize no separate cost: maximize \(\sum_{t,j}x_{tj}(v_tq_j-w_j)\) subject to stability, full assignment of each type's mass, and the per-capita budget. The computational parameters are \(m\), \(\tau\), and input bit length \(L\).
The mirror covers Theorem 1's optimal stable-assignment problem. It leaves Theorem 2's discrete FPTAS, Theorem 3's ordered-Knapsack FPTAS, and the lottery results in Theorems 4 and 5 outside its scope.
My lead is the finite-support continuous version of the optimal stable assignment problem. A type \(t\) is a patient’s complete description for this model: their value \(v_t\) for the service. They share the same hospital qualities and costs as everyone else. The society is a distribution \(\mu\) over \(\tau\) such types, where \(\mu_t\) is the fraction of patients of type \(t\). Hospitals have qualities \(q_j\) and per-patient costs \(c_j\), with the common ranking \(q_1\ge\cdots\ge q_m\). The planner has a per-capita budget \(b\).
The decision variable is \(x_{tj}\), the mass of type \(t\) assigned to hospital \(j\), together with hospital waiting times \(w_j\). Each patient still receives one hospital; divisible mass means that a large cohort of identical patients can be divided among hospitals. A feasible solution has \(\sum_j x_{tj}=\mu_t\), \(\sum_{t,j}c_jx_{tj}\le b\), and, whenever \(x_{tj}>0\), hospital \(j\) maximizes \(v_tq_j-w_j\) over all hospitals, with that maximum nonnegative. The objective is to maximize average social welfare, \(\sum_{t,j}x_{tj}(v_tq_j-w_j)\). The computational question is to return a maximizing stable mass assignment and its waits, on input given by binary-encoded qualities, costs, type values, rational masses, and budget. Its parameters include \(m\), \(\tau\), and input bit length \(L\).
Theorem 1 is my anchor. It states that, in the common-preference Provision-after-Wait problem, computing an optimal budget-feasible stable assignment that maximizes social welfare is NP-hard. The result is proved in this paper: its reduction is from Subset Sum, through a decision version of Provision-after-Wait; the reduction and supporting argument are presented here, with some proofs deferred to the full version. The underlying problem is exactly the one above, except that the input is a finite list of individual patients and the assignment gives each one a hospital.
The regime I have in mind is a large regional or national health system providing one procedure over a budget period. Many patients fall into the same standardized urgency or willingness-to-wait category, so the number of patients \(N\) is much larger than the number of distinct types \(\tau\). Each category has the same value \(v_t\) for the procedure, and therefore shares the common quality ranking and proportional valuation structure of the paper. Normalizing the total population to one means the budget must also be expressed per capita. That scaling keeps the planner’s budget constraint meaningful as the population grows. This is a plausible high-multiplicity regime, though the common ranking and exact within-type homogeneity are substantive assumptions.
I expect this mirror to be tractable, in Class A, though that is a conjecture for the prover to settle. The paper’s hardness reduction encodes Subset Sum choices through individual patient assignments. In the continuous version, each type’s mass can be split across patients’ assignments, which may dissolve those binary choices. The paper also establishes ordered structure for stable assignments, and its continuous section gives a reason to look for an optimization formulation using that structure. But shared waiting times couple the choices across types: it would take a structural or algorithmic result to show that the resulting problem is polynomial in \(m,\tau,L\). Further questions include whether a polynomial-size LP captures the feasible stable mass assignments, how the continuous optimum relates to high-multiplicity discrete instances, and whether the tractability survives when valuations are not proportional to hospital quality.
The authors would plausibly recognize this as their problem: it preserves their patients, common preferences, hospital qualities and costs, waiting-time rationing, stability, budget, and welfare objective. Their Section 4 already treats patients as a continuous population for lottery results and defines an optimal stable assignment as a comparison point. That section makes the setting especially natural, but it also marks the weakest point of my case: a referee could regard the continuous stable-assignment model itself as already present in the paper. The contribution I am arguing for is narrower—the exact computational problem for a rational, finite-support population, which the lottery comparisons do not classify. This mirror covers Theorem 1 only; it does not claim to mirror the ordered-Knapsack results or the lottery theorems.
The strongest objection is that the proposed mirror’s continuous model is already in the paper. Section 4 makes patients a population on \([0,1]\), defines stable assignments and their optimum, and Section 4.3 derives an interval structure and waiting-time formula for stable assignments. The proposed finite-support version changes how that population is encoded and asks for a bit-complexity classification, but its population model and much of its structural analysis are already present. That makes the new contribution narrower than the case for it suggests.
That objection does not defeat the anchor. The paper’s continuous analysis compares stable assignments with lotteries; it does not classify the computation of the optimal stable assignment from rational type masses. The LP in Section 4 computes an optimal randomized assignment, not an optimal stable one. Under the programme’s stated standard, an existing analytic treatment is not an answer to the computational question.
Nor can I rule out the mirror on modeling grounds. A large health system with repeated urgency or willingness-to-wait categories is a plausible high-multiplicity regime. Patients of the same value are indistinguishable for this model, mass is meaningful, and a per-capita budget is a natural scaling. Fractionally splitting a type’s mass preserves the individual requirement that each patient receive one hospital. Theorem 2’s FPTAS for finite patient counts does not settle the complexity in \(m,\tau,L\), and the Subset Sum reduction’s discrete hardness cannot count against asking what happens after continuization.
So the negative case is weak. The best claim is that this mirror may be an incremental computational refinement of a continuous model the authors already study. But that is not enough to show it is unworthwhile, and I cannot honestly defeat the anchor or support the universal claim that no worthwhile continuous mirror 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.