| paper | d4-conf-aaai-2018-0360 |
| 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→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\): every valid instance admits a feasible \(1\)-stable mass allocation. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
For fixed \(\alpha>1\), given hospitals \(H\), a finite support \(T\) of doctor types with rational masses \(\mu_t\) summing to \(1\), and each type’s ranked contract options with rational per-capita budget uses \(\sigma_t(x)\) and hospital utilities \(u_t(x)\), distinguish whether a feasible mass allocation has no \(1\)-blocking deviation or whether every feasible mass allocation has an \(\alpha\)-blocking deviation. An allocation assigns masses \(y_{t,a}\) to each type’s options \(a\), with \(\sum_a y_{t,a}=\mu_t\) and each hospital’s total budget use at most \(1\); a blocking deviation reallocates eligible masses to contracts at one hospital, within its budget, and blocks when its utility exceeds \(\alpha\) times that hospital’s current utility.
Represent each type by its complete contract ranking and contract data, and its population by mass \(\mu_t\). Use allocation variables \(y_{t,a}\) and deviation-flow variables \(z_{t,a,x}\); require each type’s mass to be assigned once, each hospital’s per-capita budget use to stay within \(1\), and each deviation flow to draw only from mass assigned to a less-preferred option or to the same option. A hospital blocks when the utility of the deviating mass exceeds \(\alpha U_h(y)\).
The mirror covers Theorem 1’s gap-existence question. It leaves the mechanism bounds, strategy-proofness results, and the other approximation guarantees unexamined.
My lead is a continuous gap-stability problem anchored on Theorem 1. In the paper, Theorem 1 is proved here by a reduction from SUBSET SUM: for every fixed constant \(\alpha>1\), distinguishing a market that has a \(1\)-stable matching from one that has no \(\alpha\)-stable matching is NP-complete. Here, \(1\)-stability rules out a hospital deviation that strictly improves its utility; \(\alpha\)-stability rules out a feasible deviation whose utility exceeds the hospital’s current utility by a factor greater than \(\alpha\). The theorem is a promise-gap result: instances satisfying neither side need not be classified.
A plausible regime is a large, centralized physician-placement round: tens of thousands of doctors matched to a modest set of hospitals, with many doctors sharing a profile of preferences and qualifications. A type records the doctor’s complete ranking over available contracts and every attribute the market uses about that doctor, including how hospitals value the doctor. Standardized offers and a finite qualification taxonomy make it plausible that the number of distinct types \(\tau\) is much smaller than the number of doctors \(N\). This is a scenario claim, not a claim that every matching market has that structure.
Here is the mirror I would ask a prover to study. An instance has a finite hospital set \(H\), a finite support \(T\) of doctor types with rational masses \(\mu_t\ge 0\) summing to \(1\), and a finite set of contract options for each type. Each option \(x\) specifies a hospital \(h(x)\), a rational budget-use coefficient \(\sigma_t(x)\), and a rational hospital utility \(u_t(x)\); type \(t\) has a strict ranking \(\succ_t\) over its options and the outside option \(\varnothing\). The contract data and rankings are part of the type description.
An allocation is a set of masses \(y_{t,a}\ge 0\), for \(a\) an option or \(\varnothing\), with \(\sum_a y_{t,a}=\mu_t\). Each unit of mass receives one whole contract at the individual level; the allocation records how the cohort is divided among contracts. Hospital \(h\)’s budget constraint is \(\sum_{t,x:h(x)=h}\sigma_t(x)y_{t,x}\le 1\), and its utility is \(U_h(y)=\sum_{t,x:h(x)=h}u_t(x)y_{t,x}\). The per-capita normalization is the co-modification: when a finite market is replicated to grow its population, each person’s share of a hospital’s budget shrinks, while budget use per unit of population mass stays fixed. For example, if \(N\) doctors each have mass \(1/N\), setting \(\sigma_t(x)=N s(x)\) makes their aggregate use of the normalized budget equal the original sum of contract sizes \(s(x)\).
Define a deviation for \(h\) by masses \(z_{t,a,x}\ge 0\) transferred from type \(t\)’s current assignment \(a\) to an \(h\)-contract \(x\). It must satisfy \(\sum_{x\in X_t(h):\,x=a\text{ or }x\succ_t a}z_{t,a,x}\le y_{t,a}\) for each \(t,a\), and \(\sum_{t,a,x}\sigma_t(x)z_{t,a,x}\le 1\). Thus a unit can be used only once, and a unit moved to a new contract must prefer it; units retained on the same contract may stay. The deviation is \(\alpha\)-blocking if \(\sum_{t,a,x}u_t(x)z_{t,a,x}>\alpha U_h(y)\). The named problem is:
Continuous Gap-Stability. Given such a rational market and fixed \(\alpha>1\), distinguish whether it has an allocation with no \(1\)-blocking deviation or has no allocation with any \(\alpha\)-blocking deviation. A YES solution is an explicit stable mass allocation; a NO answer asserts that every feasible mass allocation admits an \(\alpha\)-blocking deviation. Its natural complexity parameters are \(|H|\), \(\tau\), the number of listed contract options, and their bit length \(L\).
I expect this mirror to be Class A, though the expectation is a research direction, not an established algorithm. The subset-sum reduction behind Theorem 1 relies on discrete selection among doctors’ contracts. In the mirror, a type’s mass can split across options, so the equality that encodes a subset choice can become a fractional allocation. For a fixed allocation, finding a hospital’s best blocking deviation is itself a linear optimization problem over eligible masses and its budget. The challenge is to characterize allocations that simultaneously rule out all such deviations; a useful route may be to dualize those deviation problems or find a configuration-LP formulation with separation over the finite type and contract support. The question is whether that global existence problem can be solved in time polynomial in \(|H|,\tau\), the option count, and \(L\).
This mirrors the paper’s central object closely: doctors’ preferences, hospital budgets, additive hospital utilities, coalitional deviations, and the multiplicative stability guarantee all remain. It covers Theorem 1’s existence gap; the paper’s mechanism bounds and strategy-proofness results are outside this particular mirror. Further questions are whether a \(1\)-stable mass allocation always exists, whether the gap problem is polynomial for the stated parameters, and what rounding guarantee a continuous solution gives for a large replicated finite market.
The weakest point is the budget scaling and the divisibility of a type’s cohort. They change how a hospital’s budget is measured and permit a fraction of identical doctors to take each contract. The model keeps each individual assignment integral, but its stability test allows a hospital to recruit a fractional mass. A referee could reasonably ask whether that is the intended high-multiplicity version. I think the cohort interpretation makes it credible, especially for repeated placement rounds with standardized contract menus and budgets that grow with intake.
Theorem 1 is the right anchor: it is a computational gap result, and stability itself does not depend on tracking which named doctor holds each contract. The strongest objection is the population scale of the hospitals’ budgets.
Replicate a fixed market \(N\) times in its doctor population, keeping the hospitals, their budgets, and the contract menu fixed. If a contract uses fraction \(s>0\) of a hospital’s budget, assigning normalized mass \(y\) to it consumes \(Ns y\): mass \(y\) represents \(Ny\) doctors. With a fixed menu of positive contract sizes, each hospital can hire only a bounded number of doctors, so its matched share tends to zero as \(N\) grows. In the probability-mass limit, the interesting allocations and blocking coalitions disappear.
A nondegenerate model must make per-doctor budget use shrink with \(N\), or make hospital budgets grow with the cohort. Either can define a sensible per-capita market, and the programme explicitly permits this kind of co-modification. But it adds a substantive economic assumption absent from the paper’s fixed hospital budgets. The proponent’s repeated-placement scenario might justify it; the paper itself does not establish that such scaling is natural for its target markets.
The low-support premise is also demanding: a type must fix a doctor’s complete contract ranking and all relevant contract data. Standardized offers and qualifications could produce repeated types, though individualized hospital preferences may make support grow with the population. That concern narrows the regime; it does not rule it out.
So the fixed-budget scale issue is the best case against, but it does not defeat the better per-capita mirror. Given the permitted scaling and the plausible cohort scenario, I cannot make a convincing universal case that this anchor has no worthwhile continuous mirror.
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.