| paper | d4-conf-aaai-2021-0031 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem belongs to \(\mathrm{P}\), with running time \((m+\tau+L)^{O(1)}\) bit operations. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite support \(T\) of patient–donor pair types with rational masses \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\), directed compatible and half-compatible arcs \(C,H\subseteq T\times T\), no inherently incompatible arcs, and rational bounds \(q,\rho\in[0,1]\), does there exist nonnegative mass flow \(x_{ab}\) on \(C\cup H\) such that, for each \(t\in T\), \(\sum_b x_{tb}=\sum_a x_{at}\le\mu_t\), \(\sum_{(a,b)\in H}x_{ab}\le q\), and \(\sum_{(a,b)\in C}x_{ab}\ge\rho\)? Here \(x_{ab}\) is the mass of type-\(a\) donors assigned to type-\(b\) recipients; the balance constraints make participating pair mass both donate and receive, and a feasible circulation decomposes into exchange cycles.
A typed population of patient–donor pairs with masses \(\mu_t\), compatible and half-compatible donor-to-recipient arcs, and a per-capita suppressant limit \(q\). Choose a balanced circulation \(x\) maximizing compatible-transplant mass subject to the half-compatible mass bound; the decision version asks whether the compatible mass reaches \(\rho\). This is a linear program with \(O(\tau^2)\) possible type-pair variables.
In the paper’s randomized-edge regime, complete compatibility neighborhoods may make \(\tau\) close to the number of pairs, limiting the mirror’s practical compression; the proponent acknowledges this risk but supplies no evidence that the repeated-profile regime describes those experiments.
fatal: False
The mirror covers Theorem 3’s unrestricted-cycle \(h\)-MaxKEI question in the Silver Bullet model, with a per-capita suppressant bound. Theorem 2 supplies a related full-coverage version for paired pools. It leaves the bounded-cycle ILP and its hardness discussion, Theorem 1’s other objectives, and the empirical results outside the mirror.
The strongest case is for continuous maximum compatible coverage in a typed kidney exchange pool. Kidney exchange already has the right population structure: a patient–donor pair is a natural unit, and strong individual rationality links the patient’s participation to their paired donor’s. A plausible high-multiplicity setting is a large, recurring regional or national pool with many pairs sharing clinical and compatibility profiles. A type must include the pair’s donor and recipient attributes, its compatibility with every other type, and any suppressant-related costs or utilities. If there are \(N\) pairs but only \(\tau\) such profiles, with \(N\) much larger than \(\tau\), mass \(\mu_t\) is the fraction of pairs of type \(t\).
The lead anchor is Theorem 3, proved in the paper: in the Silver Bullet model, \(h\)-MaxKEI can be solved in polynomial time. Here \(h\)-MaxKEI asks whether there is an allocation giving at least \(t\) recipients a compatible donor while using suppressants for at most \(h\) recipients.
Its continuous mirror is Continuous \(h\)-MaxKEI. The input is a finite set of pair types \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), typed compatible and half-compatible donor-to-recipient arcs, a suppressant share \(q\), and a target share \(\rho\). In the Silver Bullet model there are no inherently incompatible arcs. A solution is a nonnegative flow \(x_{ab}\) on compatible and half-compatible arcs, where \(x_{ab}\) is the mass of type-\(a\) donors assigned to type-\(b\) recipients. It must satisfy, for each type \(t\),
\[ \sum_b x_{tb}=\sum_a x_{at}\le \mu_t, \]
and
\[ \sum_{(a,b)\in H}x_{ab}\le q, \qquad \sum_{(a,b)\in C}x_{ab}\ge \rho. \]
The first condition gives the same active mass of each type a recipient and donor role, as strong individual rationality requires. A feasible flow can be decomposed into exchange cycles; each cycle’s mass represents a fraction of distinct pairs carrying out whole transplants. Fractional values describe shares of a type, not fractional kidneys or fractional treatment of an individual. The question is whether such a flow exists. This is my strongest mirror: it retains the paper’s partial-allocation question, suppressant cap, compatibility distinction, and paired participation constraint. Its expected class is A, by an explicit linear program with \(O(\tau^2)\) arc variables.
A second, complementary anchor is Theorem 2, also proved in the paper: \(h\)-AllKEI is polynomial-time solvable even in the general model, where some donors remain incompatible after suppression. It asks whether an allocation can satisfy every recipient using at most \(h\) suppressants. Its continuous mirror, Continuous \(h\)-AllKEI, uses the same typed instance and flow variables, now allowing incompatible pairs to have no arc. It asks whether a flow exists with
\[ \sum_b x_{tb}=\sum_a x_{at}=\mu_t \quad\text{for every }t, \qquad \sum_{(a,b)\in H}x_{ab}\le q. \]
This requires every unit of pair mass to participate in a transplant. It is a narrower coverage objective than the lead, but it tests the more realistic general compatibility model. Its expected class is also A, through rational LP feasibility.
The finite-to-continuous dictionary is direct: a discrete pool with \(n_t\) pairs of type \(t\) has \(\mu_t=n_t/N\), and a suppressant quota \(h\) becomes \(q=h/N\). A discrete allocation induces a flow whose entries lie on the \(1/N\) grid. The next questions are whether continuous solutions can be rounded with a useful additive guarantee, and how that guarantee depends on \(\tau\). The paper’s cycle-length restrictions suggest another extension: require the flow to decompose into cycles of length at most \(K\), then determine the dependence on \(\tau\) and \(K\). These mirrors cover unrestricted-cycle \(h\)-MaxKEI in the Silver Bullet model and full coverage in the general model; they do not claim to cover the paper’s cycle-bounded hardness discussion or its incentive and monotonicity questions.
The main weakness is whether a kidney pool really has \(N\gg\tau\) once types encode complete compatibility, costs, and utilities. Detailed immunological profiles can make many pairs unique, and operational cycle limits matter. The case is strongest for a recurring large pool whose compatibility is determined by a moderate catalog of repeated clinical profiles; it should not be generalized to every exchange market. The paper has no numbered hardness theorem to anchor here: its cycle-bounded NP-hardness statement in Section 6 is unnumbered and cites prior work. I therefore use the named polynomial-time results above rather than presenting that statement as an anchor.
The strongest case against these anchors is that kidney exchange is a poor *default* population-limit target: its operative data are directed donor-to-recipient compatibility edges, and the pair is a linked unit. A complete type must preserve the clinical attributes that determine those edges. With pair-specific crossmatches, center rules, and immunological risks, identical types may be uncommon; in the paper’s random half-compatible-edge experiments, exact compatibility neighborhoods would usually make nearly every pair its own type. Then \(\tau\) grows with the pool, and the proposed population representation offers little compression.
That objection is conditional, though. Compatibility can also be generated from repeated donor and patient attributes. A study of real UNOS graphs reports lossless representations using far fewer attributes than the worst case, and describes fielded exchanges as generally restricting cycles to length two or three. That evidence makes repeated profiles plausible, rather than ruling them out. It is not a continuous-population computational treatment, so it is no novelty collision; it does, however, weaken the claim that useful type compression is impossible. [Small Representations of Big Kidney Exchange Graphs](https://arxiv.org/abs/1605.07728)
For Theorem 3, the proponent’s per-capita suppressant budget \(q\) is the right repair if supply grows with the pool. If the real policy instead fixes the number \(h\) of available treatments while the pool grows, then \(q=h/N\) tends to zero: suppressant-enabled transplants can disappear from a positive-mass objective. That makes the normalized mirror less directly tied to a fixed scarce supply. But the programme explicitly allows per-capita supply as a co-modification, so this does not defeat the stronger version. With a bounded cycle length \(K\), one can formulate the continuous problem using variables for type-level cycles of length at most \(K\); for fixed \(K\), that avoids relying on the proposed flow’s unrestricted cycle decomposition.
For Theorem 2, exact full coverage has a sharper mismatch with a mass limit. A single exceptionally hard-to-match pair can make the finite \(h\)-AllKEI instance infeasible, yet its mass vanishes as the pool grows. A coverage fraction will not preserve that guarantee; retaining it may require treating exceptional pairs separately. Still, a curated pool with repeated types and no vanishing outlier has a coherent full-coverage feasibility question, and partial coverage leads back to the stronger Theorem 3 mirror.
So the negative case supports caution about how often these models describe actual pools, especially when complete clinical types are numerous or rare cases drive feasibility. It does not defeat the best typed-pool versions: the paper states named computational results, and a repeated-profile regime with mass-based treatment limits is plausible. I can argue these are conditional targets, but I cannot honestly defend the universal claim that no worthwhile continuous mirror exists in any 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.