| paper | d4-conf-aaai-2015-0257 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's batch-clearing section cites NP-hardness for finite-cycle clearing, but presents no numbered computational result of its own. Its FutureMatch comparisons are empirical and state no algorithmic guarantee. The proposed type-cycle LP is a coherent mirror of the cited clearing problem, but it is not anchored in a qualifying result of this paper.
fails bit a — no named computational result to mirror
The proposed LP covers finite-cap cycle clearing; it leaves out learned potentials, dynamic arrivals and departures, failure-aware planning, and the empirical results.
The strongest honest case is a mirror of the paper’s batch kidney clearing problem, but it has an anchor limitation. The paper states that clearing with a finite cycle cap \(L>2\), even without chains, is NP-hard, citing Abraham, Blum, and Sandholm (2007). That claim is cited from elsewhere and has no theorem number in this paper. The paper contains no numbered theorem, lemma, corollary, or proposition asserting a complexity result, so this is not a qualifying anchor under your rule. Its FutureMatch results are empirical rather than formal complexity results.
Taking that cited hardness statement as the closest foothold, my candidate lead is Continuous Type Cycle Clearing. An instance has a finite set \(T\) of patient–donor types, rational masses \(\mu_t\) summing to \(1\), a directed compatibility relation between types, rational transplant weights \(w_{tu}\), and a fixed cycle cap \(L>2\). A type records the relevant donor and patient attributes; compatibility and transplant weight are determined by the types. Let \(\mathcal C_L\) be the compatible cycle templates of lengths \(2\) through \(L\), and let \(a_{tC}\) count how many times type \(t\) appears in cycle \(C\). Choose \(x_C\geq 0\), the mass assigned to complete cycles of template \(C\), to maximize
\[
\sum_{C\in\mathcal C_L} x_C \sum_{(t,u)\in C} w_{tu}
\quad\text{subject to}\quad
\sum_{C\in\mathcal C_L} a_{tC}x_C\leq \mu_t
\quad\text{for every }t\in T.
\]
The requested solution is an optimal vector \(x\) and its value. Each unit of \(x_C\) represents a complete cycle; fractional values describe how much of a large type population takes part.
A plausible regime is a mature regional or national exchange in which many pairs share the same full clinical profile and the number of pairs greatly exceeds the number of profiles. Types would need to preserve the attributes that determine compatibility and transplant weight, not just blood type. The paper’s nationwide exchange setting makes that scenario recognizable as kidney clearing, though the support-size claim is a substantive assumption. For fixed \(L\), the type-cycle LP has at most \(O(\tau^L)\) cycle templates, so I expect this mirror to be tractable in \(\tau\) and the input bit length. The discrete hardness may disappear when repeated types can be split into cycle masses. This covers the paper’s finite-cycle batch clearing core; it does not cover FutureMatch’s learned potentials, dynamic arrivals and departures, failure-aware planning, or experimental findings.
The authors would plausibly recognize the underlying clearing question: it still selects compatible barter cycles under the same cap and uses the same transplant utility. My weakest point is that exact clinical profiles, especially HLA and recipient-specific attributes, may leave few repeated types. If \(\tau\) approaches the number of pairs, this is a much less persuasive high-multiplicity regime. Natural follow-up questions are whether the LP value approximates finite batch clearing, how the model extends to altruist chains, and how type-level arrivals, departures, and transplant failures change the dynamic optimization problem.
The negative case is strongest at the anchor gate. The paper has no numbered theorem, lemma, or corollary asserting a computational result. Its own contributions are a framework and empirical comparisons; the NP-hardness claim is a sentence citing earlier work. Under the stated rule, that leaves no qualifying result for the proposed mirror to anchor on.
The proponent’s type-cycle LP is the best repair, but it mirrors that cited clearing problem, not a named computational result of this paper. It is also a credible research question in its own right: for fixed \(L\), it has \(O(\tau^L)\) cycle templates, so the explicit LP is polynomial in \(\tau\) and the input bit length. I cannot honestly dismiss it as an uninteresting or invalid continuous model. Its weaker point is whether \(\tau\) stays moderate when a type must preserve the clinical information that determines compatibility and transplant value. Kidney compatibility can depend on donor HLA antigens and recipient antibodies, among other attributes, so grouping only by blood type may change the graph and objective. [Kidney exchange compatibility model](https://pmc.ncbi.nlm.nih.gov/articles/PMC4004760/)
A stronger mirror could put arrivals, departures, and failures into a type-level population process and ask for the complexity of choosing exchanges to maximize expected long-run outcomes. That would be recognizable as kidney exchange and computational. But it would be a new stochastic-control problem: the paper reports simulation results for its learned potentials and particular data, not a formal complexity or approximation claim about such a population process.
So the stipulated anchor test yields a negative verdict on the proponent’s case: none of its proposed questions mirrors a qualifying result of this paper. The broader claim that no worthwhile continuous mirror exists in any scenario is much less secure. The static type-cycle model remains a plausible, potentially useful question; the honest negative argument is about the paper’s lack of an eligible anchor, not a fundamental flaw in continuizing kidney exchange.
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.