| paper | d4-conf-aaai-2016-0339 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for every fixed pair of caps \(\ell,k\). An exact rational maximum-weight mass allocation can be computed in time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given paired and altruist types \(P\cup A\), rational masses \(\mu_t\), type-to-type compatibility and edge weights, and fixed cycle and chain caps \(\ell,k\), compute a maximum-weight allocation of legal cycles and chains. A template may repeat a type label when separate participants fill its positions; for template \(q\), choose mass \(x_q\geq 0\) to maximize \(\sum_q W_qx_q\) subject to \(\sum_q a_{tq}x_q\leq\mu_t\) for every type \(t\). Does this mass-allocation problem admit a polynomial-time algorithm in the number of types and the input bit length for fixed caps?
A configuration LP over integral cycle and chain templates, with each type carrying mass \(\mu_t\), each template consuming \(a_{tq}\) units of type \(t\) per unit of template mass, and objective equal to total edge weight. Pricing searches for a positive reduced-value template; repeated type labels are allowed because a type’s mass can supply distinct participants.
Exact type classes may be numerous in real exchanges with pair-specific crossmatches and values, and the proponent does not establish that a clinically credible category catalogue keeps their count small.
fatal: False
The mirror covers Theorem 1’s capped pricing role within type-mass clearing; it leaves the discrete solver’s full branch-and-price correctness proof, runtime comparisons, and behavior on pair-specific graphs outside the mirror.
The strongest defensible mirror is narrow: it concerns capped cycle and chain pricing inside the clearing problem, not the paper’s whole solver or its empirical runtime results.
My sole numbered anchor is Theorem 1, proved in this paper. It states that if the reduced graph contains a negative cycle, the corrected algorithm returns at least one. The paper’s surrounding analysis gives the corrected pricer a running time of \(O(|V||E|K^2)\) when \(K>L\); the theorem proves the algorithm’s completeness, while that separate bound supplies its polynomial-time aspect. The paper’s statement that finite maximum-cardinality clearing is NP-hard for cycle cap \(L>2\) is cited from Abraham, Blum, and Sandholm (2007), not presented as a numbered result here, so I would not use it as an anchor.
A plausible regime is a very large exchange pool in which compatibility and transplant value are determined by a manageable catalogue of clinical categories—for example, a model using blood group and a bounded set of compatibility and priority bands. There may be many thousands of patient–donor pairs and altruists, but far fewer distinct types. A paired type specifies a patient–donor category; an altruist type specifies an altruist category. Two participants share a type only when they have the same eligibility and edge values against every type. Thus \(\mu_t\) is the fraction of the pool in type \(t\), with \(\sum_t\mu_t=1\). This is an exact description of that category-based regime, rather than a claim that individual crossmatches in every real exchange are interchangeable.
Lead problem: Type-Mass Capped-Exchange Clearing. An instance gives finite type sets \(P\) of paired types and \(A\) of altruist types, rational masses \(\mu_t\), directed compatibility arcs between types, rational edge weights \(w_{tu}\), and cycle and chain caps \(\ell\) and \(k\). A legal template \(q\) is either a cycle of paired types of length at most \(\ell\), or a chain starting at an altruist type and continuing through paired types, with at most \(k\) vertices including the altruist. Repeated type labels are allowed: separate participants from that type’s mass fill the separate positions.
For each template let \(W_q\) be its total edge weight and \(a_{tq}\) the number of times type \(t\) occurs in it. The task is to find an optimal nonnegative mass \(x_q\) for every template:
\[ \max \sum_q W_qx_q \quad\text{subject to}\quad \sum_q a_{tq}x_q\leq \mu_t\quad\text{for every type }t. \]
The solution is the optimal allocation and its value. Each \(x_q\) represents a fraction of participants routed through an integral cycle or chain; nobody receives a fractional transplant. This makes the population itself continuous, while the discrete exchange bundles and the paper’s caps remain intact.
The connection to Theorem 1 is the pricing problem for this mass LP. Given dual prices \(\lambda_t\), seek a legal template with positive reduced value \(W_q-\sum_t a_{tq}\lambda_t\), or certify that none exists. As in the paper, this is a negative-cycle search after assigning edge lengths \(\lambda_t-w_{tu}\) and adding a zero-weight return edge to represent a chain. At the type level, revisiting a type means using distinct participants from its mass, so bounded-walk dynamic programming can price these templates. With caps fixed as policy parameters, or encoded by their numeric values, this gives a polynomial-time pricing route and hence a tractable LP mirror: Class A. The question Plaut et al. should recognize is whether their capped cycle-and-chain clearing objective has this tractable mass-allocation form and pricing oracle.
The weakest point is the type assumption. Real kidney-exchange graphs can have pair-specific crossmatches and values; grouping those participants into exact types may make \(\tau\) large enough to erase the high-multiplicity benefit. The anchor is also a pricing-correctness result, not a hardness theorem or a polynomial-time result for the paper’s entire discrete clearing problem. The case survives only for the stated category-homogeneous regime, where the same cycles, chains, caps, and additive edge objective are preserved.
This mirror generates two useful follow-up questions: how closely does the mass optimum track the normalized optimum of large finite clone-expanded pools, and what is the finite-pool integrality gap? It also asks whether clinically meaningful compatibility categories can keep \(\tau\) small without losing too much clearing value.
The sole anchor is weaker than the proponent makes it sound. Theorem 1 proves completeness of a corrected pricing algorithm on a finite compatibility graph: if a negative cycle exists, the algorithm returns one. The \(O(|V||E|K^2)\) bound appears in the surrounding discussion, but the theorem’s distinctive point is avoiding repeated *vertices* in a path.
That point changes under the proposed mass model. A type can occur several times in a chain or cycle because each occurrence can use a different participant from its nonatomic mass. The finite-graph loop that the fix must prevent can therefore represent a valid type sequence. Pricing on a finite type graph becomes a bounded-length walk problem, solvable directly by dynamic programming; with fixed practical caps, the templates can also be enumerated. That may support a continuous clearing LP, but it does not continue the theorem’s correctness issue or its fix. It is a different pricing problem.
The model then faces a fidelity trade-off. To preserve pair-specific compatibility and edge weights exactly, a type must retain enough information about its interactions with other participants or types. When crossmatches and values vary by pair, exact type classes may be close to singletons, so the mass representation gains little. Grouping by broader clinical categories gives a coherent model only when those categories make interactions sufficiently uniform—or when the model replaces individual compatibility with an aggregate approximation. That can be a sensible stylized exchange, but it narrows the kidney-exchange problem substantially.
There is also a limit to the chain part of the mirror: if the number of altruists stays bounded while the paired population grows and \(K\) stays fixed, chains can serve at most \(O(K|A|)\) pairs. Their share of the normalized population then vanishes. Scaling altruists with the population or keeping them as a separate finite resource can address this, but each is an additional modelling choice.
So the strongest case against is that the theorem’s main computational issue belongs to finite, participant-specific graphs; under exact aggregation it loses its distinctive content, while broader aggregation risks changing the compatibility model. But that does not establish the requested universal negative. A genuinely block-constant exchange with many cloned participants per type is a coherent high-multiplicity regime, and its mass-clearing question could still be worthwhile. I would reject Theorem 1 as strong evidence for the proposed mirror, while conceding that this anchor alone cannot rule out a worthwhile mirror in every scenario.
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.