| paper | d4-conf-aaai-2018-0642 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 3 proves a worst-case price-of-fairness bound, which is a performance bound rather than an algorithm, complexity, or hardness result. The typed cycle-rate LP is a plausible extension, but it has no qualifying named computational result to anchor it, so bit (a) fails.
fails bit a — no named computational result to mirror
Theorems 1–9 cover random-graph price-of-fairness bounds, worst-case bounds for fairness rules, and a hybrid-rule price-of-fairness bound; the experiments evaluate finite exchange graphs. None provides a named algorithmic or complexity result for a continuous mirror.
I can’t make an anchor-compliant positive case: this paper has no named computational-complexity or algorithmic result of the kind the programme requires.
The closest numbered result is Theorem 3, proved in this paper: for every cycle cap \(L\) and every \(0<\alpha\leq1\), there is a kidney-exchange graph \(G\) whose price of fairness under \(\alpha\)-lexicographic fairness is at least \((L-2)/L\). That is a worst-case efficiency-loss result; it does not classify the complexity of a problem or give an algorithmic guarantee. The other numbered theorems similarly establish price-of-fairness bounds. The paper does say that kidney-exchange clearing is NP-hard and solves instances using the PICEF formulation, but the hardness claim is background, and PICEF is a formulation from prior work—not a named computational result established here. So there are no qualifying anchors, and no per-anchor continuous questions to offer.
There is nevertheless a plausible *unanchored extension*. In a large multi-center exchange, many patient–donor pairs might share a small number \(\tau\) of complete clinical types, with population size \(n\gg\tau\). A type would need to include sensitization and the pair’s compatibility and success probabilities with every other type; blood type and sensitization class alone may not capture enough. Let \(\mu_t\) be each type’s population fraction. For every allowed typed cycle or chain \(S\), choose a nonnegative rate \(x_S\), subject to \(\sum_S a_{tS}x_S\leq\mu_t\) for each type \(t\), where \(a_{tS}\) counts how many members of \(t\) the pattern uses. Let \(u_H(x)\) and \(u_L(x)\) be the expected transplants for highly and lowly sensitized patients under the paper’s failure model. One concrete problem is to compute rates maximizing \(u_H(x)+u_L(x)\), subject to \(u_H(x)\geq\alpha u_H^*\), where \(u_H^*=\max_x u_H(x)\). The output is the rate vector and its resulting utilities.
With fixed cycle and chain caps, enumerating typed patterns gives an LP, or a two-stage LP for the fairness constraint, so this candidate looks Class A. But a mirror would need to show that the fluid optimum predicts finite exchanges: realized pairwise compatibility can distinguish members of the same coarse type, and exact compatibility types may make \(\tau\) large. The paper’s random-graph analysis already uses population fractions, which makes the extension natural but also risks making it thin or close to work the paper has substantially analyzed.
The weakest point is decisive for this task: this model could be a worthwhile new research lead, but it is not the continuous mirror of a qualifying named computational result in this paper. Presenting it as one would overstate the case.
On ChoCo’s stated gate, this paper has no result to anchor a continuous computational mirror. Theorems 1–9 bound the price of fairness or characterize matching outcomes; none gives a complexity classification or an algorithm for a computational problem. Kidney-exchange clearing’s NP-hardness is background, and PICEF is prior work. Theorem 3 is the closest candidate, but its \((L-2)/L\) bound is a worst-case efficiency-loss result. A continuous version of that bound could be interesting, yet it would not supply the kind of computational question the programme is set up to chart.
The proposed typed cycle-rate LP does not rescue the anchor. It defines a sensible new model if compatibility is homogeneous between types. With fixed cycle and chain caps, its pattern variables give a standard LP. If compatibility remains specific to individual pairs, the type description must preserve those differences; the support can then grow with the exchange, removing the high-multiplicity advantage. Replacing realized links with type-pair probabilities instead asks about a stochastic fluid model. That is a plausible extension, but it changes the object being analyzed.
Theorem 3’s gadget is the strongest challenge to this negative case. A single disadvantaged vertex has vanishing mass as \(L\) grows, but that issue can be avoided by replicating the gadget at fixed \(L\), leaving both classes with positive mass. In a type-homogeneous blow-up, fractional cycle rates may even preserve its price-of-fairness bound. So I cannot honestly claim that no worthwhile continuous question exists in any scenario. The firmer case is narrower: such a question would extend the paper’s performance analysis, rather than mirror a named computational result that this paper establishes.
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.