| paper | d4-conf-aaai-2021-1199 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Lemma 5.1
statement extracted from the paper’s text layer
Given rational masses for supported patient-donor types and altruist-donor types, together with compatibility data and an exchange-length limit of three, choose feasible exchange masses to maximize total transplanted mass; among those maximizing allocations, maximize the minimum patient-type transplant rate.
Represent each complete patient-donor profile by a type \(t\) of mass \(\mu_t>0\), and each altruist profile by mass \(\nu_a\). For each feasible type-level cycle or altruist-started chain \(e\), choose exchange mass \(x_e\ge 0\); let \(a_{te}\) count type-\(t\) pairs used by \(e\), and set \(y_t=\sum_e a_{te}x_e\), subject to \(y_t\le\mu_t\) and altruist capacity constraints. First maximize \(\sum_t y_t\), then maximize \(z\) subject to \(z\le y_t/\mu_t\) for every patient type. With exchange length at most three, this is an LP over polynomially many type-level patterns, \(O(\tau^3)\) up to altruist types.
The paper’s experiments do not show that many patient-donor pairs share a complete compatibility profile, so a regime with τ much smaller than the population remains plausible but unsubstantiated here.
fatal: False
The mirror covers the static optimal-transplant and Maxmin fairness stage represented by Lemma 5.1. It leaves aside enumeration of integral plans, the paper’s enumeration algorithms and experiments, and its relaxed-optimality and dynamic directions.
The strongest honest anchor is Lemma 5.1, stated in this paper; its detailed proof is referred to Farnadi et al. (2021). The paper does not give a numbered theorem classifying one of its problems as P, NP-hard, or #P-hard. It does say that enumerating all optimal plans is #P-complete even for length-two exchanges when maximizing transplants, citing Valiant (1979), but that statement is unnumbered and external, so I would not use it as a named anchor.
Lemma 5.1 says: let \(S\) be the set of optimal exchange plans, where two plans are KEP-equivalent if they transplant exactly the same patients. A projection \(\bar S\subseteq S\) contains one plan from each equivalence class. Then the optimum value of both the \(L_p\)-norm fairness problem and the Maxmin fairness problem is unchanged when the choice is restricted to \(\bar S\). The \(L_p\) objective measures dispersion in patients’ transplant probabilities; Maxmin maximizes the lowest such probability.
A plausible high-multiplicity regime is a large exchange registry in which many patient-donor pairs share the same complete clinical and compatibility profile. A type \(t\) records the patient and donor features used by the problem, compatibility with each other type, and any priority values used by the objective. Its mass \(\mu_t\) is the fraction of paired patients of that type, with \(\sum_t\mu_t=1\). Altruistic donors can likewise be grouped into types with masses \(\nu_a\). This is a regime with \(n\gg\tau\), where \(\tau\) is the number of supported pair types.
My lead mirror is Mass-Maxmin Optimal Kidney Exchange. Its input is those type masses and compatibility data, with the paper’s exchange-length limit of three. Let \(E\) be the valid type-level cycles and altruist-started chains. For each \(e\in E\), choose \(x_e\ge0\), the mass of exchanges of that pattern. If \(a_{te}\) counts how many type-\(t\) pairs participate in \(e\), then \(y_t=\sum_{e\in E}a_{te}x_e\) is the mass of type \(t\) transplanted, and \(\sum_e a_{te}x_e\le\mu_t\). Altruist use is bounded by the corresponding \(\nu_a\). First maximize total transplants, \(\mathrm{OPT}=\max\sum_t y_t\). Then, among allocations with \(\sum_t y_t=\mathrm{OPT}\), maximize \(z\) subject to \(z\le y_t/\mu_t\) for every type \(t\). The solution is the exchange mass allocation \(x\), the service rates \(q_t=y_t/\mu_t\), and the best guaranteed rate \(z\). Under anonymous assignment within each type, \(q_t\) is the transplant chance of a type-\(t\) patient. Each transplant remains an indivisible transplant for an individual; \(x_e\) allocates portions of a cohort to complete exchanges.
This is close to the paper’s question: it keeps the compatibility structure, transplant objective, and fairness goal among optimal plans. Lemma 5.1’s equivalence becomes equivalence of mass allocations with the same transplanted-mass vector \((y_t)\). Fairness depends on that vector, not on which cycle decomposition produced it. Moreover, a distribution over optimal mass allocations has a mean allocation that is itself feasible and optimal, so the continuous problem can optimize the service rates directly. That is the continuous counterpart of projecting away cycle-level redundancy.
For the stated length bound, there are only polynomially many type-level exchange patterns—\(O(\tau^3)\), up to the number of altruist types. The first stage and the Maxmin stage are linear programs with rational data. I therefore expect this mirror to be Class A, tractable in \(\tau\) and the input bit length \(L\). Other linear objectives can be handled by fixing their lexicographic optimum values, as in the paper’s definition of hierarchical criteria. The scope here is the fairness selection stage for static optimal KEP plans, especially Maxmin; it does not settle enumeration of integral plans or the paper’s dynamic questions.
The main follow-up is a precise bridge: for fixed \(\tau\) and bounded exchange length, does the best discrete Maxmin value converge to the mass value as \(n_t/n\to\mu_t\), and at what additive rate? If the length bound or support size grows, the number of type patterns may cease to be manageable; then the pricing problem and the possibility of transferred or continuum-specific hardness become substantive questions.
My weakest point is the type regime. Exact compatibility and clinical profiles may be nearly unique, leaving \(\tau\) close to \(n\) and little computational gain. There is also a real change in representation: the paper selects among integral plans, while this mirror schedules mass across exchanges. The programme permits that co-modification when population mass forces it, and the rates preserve the paper’s transplant-probability fairness question. But this mirror would not, by itself, resolve the paper’s stated #P-complete enumeration task.
The strongest case against starts with the anchor itself: Lemma 5.1 is a structural invariance result, not a computational complexity result. It says that, once the optimal plans have been enumerated, keeping one representative per transplanted-patient set preserves two fairness optima. The paper’s #P-completeness statement concerns enumeration, but it is an unnumbered claim citing external work. So this paper gives no named complexity classification whose continuous counterpart would directly extend its theorem. And “count all optimal allocations” has no natural meaning for a continuum of allocations.
That still does not defeat the stronger mirror the proponent offers. A type-level mass model can ask a clear computational question: optimize transplant rates across cohorts with the same complete compatibility profile, using fractional mass assigned to integral exchange patterns. Fractional allocations may not be lotteries over the paper’s exactly optimal discrete plans, but under the programme’s rules, that co-modification is allowed; mass can be partitioned into groups that each receive an integral exchange. The resulting LP is a genuine continuous-population problem, not just a restatement of Lemma 5.1.
The most credible practical objection is that kidney-exchange compatibility can be highly specific to each patient-donor pair. If preserving every medically relevant distinction makes nearly every pair its own type, then \(\tau\) approaches the population size and the proposed high-multiplicity advantage disappears. But that is a limitation of some instance regimes, not of the problem in every regime. Large cohorts with repeated compatibility profiles remain plausible, and the programme explicitly treats that as the operative question.
So the negative case is weak. The absence of a named computational theorem narrows what this paper directly contributes, and the type model may fit poorly when profiles are mostly unique. Neither point defeats the better mass-maxmin mirror across all plausible scenarios. I cannot honestly support the claim that no worthwhile continuous mirror exists.
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.