| paper | d4-conf-ijcai-2015-0032 |
| 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: Polynomial-time solvable: the decision problem belongs to \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given patient types \(t\in T\) with rational masses \(\mu_t\) summing to \(1\), each endowed with two donor classes and a set of compatible donor classes, and the resulting donor-class supplies, determine whether a feasible allocation can reassign positive patient mass to pairs of compatible donor units while conserving every donor supply and allowing the remaining mass to keep its endowment. Each patient unit receives a whole pair; assignments may split across units of the same type.
Use variables \(u_t\) for unchanged mass and \(x_{t,P}\) for mass of type \(t\) assigned compatible donor-class pair \(P\). Require \(u_t+\sum_P x_{t,P}=\mu_t\) for every type and equality between each donor class’s endowed supply and its total use in unchanged and reassigned pairs. Maximize \(\sum_{t,P}x_{t,P}\) and ask whether the optimum is positive.
Complete crossmatch profiles may be nearly unique, so a registry with small \(\tau\) is asserted rather than evidenced; the proponent acknowledges this risk but offers only a future-registry scenario.
fatal: False
The mirror covers Theorem 1’s non-triviality decision. It leaves Theorem 2’s mechanism properties, implementation algorithms, and empirical running-time comparisons unmirrored.
The strongest mirror is Lung-Exchange Nontriviality\(_\infty\), anchored on Theorem 1. The theorem, proved in this paper by a reduction from Perfect 3D-Matching, says that given a lung-exchange instance \(G\), deciding whether \(G\) has a feasible non-trivial solution is NP-complete. Here “non-trivial” means that some patients receive compatible donors through the exchange, rather than everyone retaining their original donors.
A plausible high-multiplicity setting is a future regional or national lung-exchange registry with many patient-donor pairs but a recurring set of clinical profiles. A patient type records the patient’s relevant traits, their two donors’ traits, and the resulting compatibility profile. Donor classes group donors who are interchangeable for this problem. For example, a protocol might use a fixed set of blood-type, lung-size, and crossmatch categories. The regime is \(N\gg\tau\): many registrants, but relatively few complete patient types. This is not a claim that today’s lung-exchange market has that scale; the paper itself says lung exchange had not yet been practiced.
An instance consists of patient types \(t\in T\), each with rational mass \(\mu_t\), an endowed donor-class pair \(e(t)\), and a set \(A_t\) of compatible donor classes. Let \(D\) be the donor classes. The mass of available donors of class \(d\) is
\[
b_d=\sum_{t\in T}\mu_t\,\mathrm{mult}_d(e(t)),
\]
where \(\mathrm{mult}_d\) counts occurrences of \(d\) in a pair. A solution assigns mass \(u_t\) of each type to the unchanged outcome and mass \(x_{t,\{d,e\}}\) to compatible donor-pair assignments. Each assigned pair consists of two distinct donor units; the classes may coincide if there are enough units.
The allocation must satisfy
\[
u_t+\sum_{\{d,e\}}x_{t,\{d,e\}}=\mu_t
\]
for each patient type, and, for every donor class \(d\),
\[
\sum_t \mathrm{mult}_d(e(t))u_t
+\sum_{t,\{a,b\}}\mathrm{mult}_d(\{a,b\})x_{t,\{a,b\}}
=b_d.
\]
The question is whether the maximum of \(\sum_{t,\{d,e\}}x_{t,\{d,e\}}\), over compatible assignments, is positive. Each unit of patient mass still receives a whole pair of donors; only the cohort allocation is divisible.
This is a direct mirror of the theorem’s underlying problem: it retains the paired donors, compatibility constraints, donor exclusivity, and unchanged option, while replacing the search over indivisible patients with a search over mass. The co-modification is part of the model: mass assigned through the exchange receives integral donor pairs. The type-level allocation is an LP with \(O(|T||D|^2)\) pair-assignment variables, so exact rational LP algorithms decide nontriviality in time polynomial in the input size and bit length. I expect this mirror to be Class A, with the discrete NP-hardness dissolving because whole-patient choices can be split across compatible pair assignments.
There is also a useful bridge to the discrete problem. A feasible discrete exchange gives a feasible mass allocation after normalizing by population size. Conversely, a positive rational LP solution can be scaled by a common denominator to obtain an exchange in a sufficiently large replicated market with the same type proportions. So the continuous question asks whether these proportions admit exchange at some sufficiently large replication, even though a particular finite market may not.
The main weak point is the type model. Blood group and size classes alone may not capture all clinically relevant crossmatches; if compatibility signatures are highly individualized, \(\tau\) could grow almost as fast as \(N\), and the proposed low-support regime becomes less convincing. The mirror still describes the high-multiplicity version, but its practical appeal depends on whether a real registry can define recurring complete types.
This case covers Theorem 1’s nontriviality decision problem. It does not claim to mirror Theorem 2’s strategy-proofness result or the paper’s empirical running-time comparisons. It also raises a natural follow-up: how much exchange can be recovered when a continuous allocation is rounded to a finite market of a prescribed size?
Theorem 1 is the right anchor, and the proposed LP is a coherent mirror. With complete patient and donor types, its balance constraints preserve donor exclusivity, and a rational positive solution can be scaled into a discrete exchange in a sufficiently large replicated market. Maximizing exchanged mass gives a more useful version of the same question and remains an LP. So the negative case cannot rest on a flaw in the formalization or on the possibility that the continuous answer is easy.
The difficulty is finding a convincing high-multiplicity lung-exchange regime. A complete patient type must preserve the patient’s relevant traits, both donors’ traits, and their compatibility with donor types. Blood group and lung-size bins alone may merge patients whose crossmatch outcomes differ. Preserving those outcomes can create many rare profiles, making the support grow with the registry rather than keeping \(\tau\) small relative to the population. The paper’s reduction illustrates the issue: its hard instances encode 3D-matching through patient-specific compatibility patterns. That shows where the combinatorics enter; it does not make the hardness an objection to asking the continuous question.
A large regional registry with recurring clinical profiles is the strongest counter-scenario. It is possible to define a finite profile system in which many patients and donors are interchangeable, but the paper’s setting involves paired donors, individualized compatibility, and simultaneous operations. The paper itself notes that lung exchange had not been practiced at the time. In that setting, repeated *complete* types at the scale needed for mass to be operationally meaningful are a substantial assumption. Coarsening profiles to obtain repetition would change compatibility; retaining the exact profiles risks making fractional portions of rare patient types the main source of the result.
Under a fixed, small type system, the mirror is still well-posed, but its algorithmic contribution appears modest: a direct fractional assignment LP with variables for patient types and compatible donor pairs. The existential question also certifies exchange only after some replication; it does not establish that a particular finite registry can conduct a transplant. The mirror’s strongest potential value would be in the follow-up problem of recovering a large exchange at a specified finite scale, but that requires additional work beyond Theorem 1’s nontriviality question.
So the case against is ultimately a case against the regime’s relevance, not against the mathematics. It is weaker than I would want for a confident rejection: if the authors can justify a registry with a small number of complete, recurring types, this anchor survives and deserves a continuous treatment.
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.