| paper | d4-conf-ijcai-2009-0088 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 2
statement extracted from the paper’s text layer
For a finite set of recurring compatibility types \(T\), a cycle cap \(L\), and a finite horizon, arrivals and expiries change the available type masses over time. At each step, an online policy chooses feasible masses \(z_c\ge 0\) for cycle templates \(c\) of length at most \(L\), subject to \(\sum_c a_{tc}z_c\le M_t\) for every type \(t\), where \(a_{tc}\) is the number of units of type \(t\) consumed by \(c\) and \(M_t\) is its available mass. Against the clairvoyant offline optimum on the same trajectory, prove or refute that every randomized prior-free policy has an obliviously chosen trajectory with \(\mathrm{OPT}/\mathbb{E}[\mathrm{ALG}]\ge (2L-2)/L\).
A finite compatibility graph on recurring pair types, with type masses changing through arrivals and expiries. The policy assigns mass to feasible cycle templates of length at most \(L\), maximizing total transplant weight at each decision; performance is measured against the clairvoyant optimum on the realized trajectory.
Covers Proposition 2's randomized prior-free competitive-ratio lower bound and its two-trajectory construction; leaves Proposition 1, Algorithms 1–3, and the experiments unmirrored.
The strongest mirror is the paper’s online impossibility result for a large exchange pool with a small number of recurring compatibility classes. A type is a patient–donor pair’s complete compatibility and transplant-value profile against every other type, together with its arrival and expiry behavior. Mass is the fraction of a fixed reference pool in each type. A fluid exchange commits mass to complete exchange cycles: if \(z_c\) is the mass assigned to cycle template \(c\), then the amount consumed from each type cannot exceed its available mass. The objective is the total transplant weight. Individual transplants remain ordinary cycles; only their aggregate quantities are fractional.
I would ask the prover this: Fluid Kidney Exchange Competitive Ratio, with cycle cap \(L\). Given a finite type-level compatibility graph, rational initial and arrival masses, expiry information, and a finite horizon, an online policy sees the exchange as it unfolds and chooses feasible cycle masses at each decision. Future arrivals and expiries are chosen by an oblivious adversary. Against the offline optimum that knows the whole trajectory, prove or refute that every randomized prior-free policy has some trajectory on which
\[
\frac{\mathrm{OPT}}{\mathbb{E}[\mathrm{ALG}]} \ge \frac{2L-2}{L}.
\]
A solution is a proof of that lower bound, or a policy and guarantee that refute it. The type graph may have just \(L+1\) types while the pool grows, so this is a genuine high-multiplicity regime: many pairs share each of a few exact compatibility profiles.
My anchor is Proposition 2, proved in the paper’s Section 3: *No randomized prior-free algorithm can achieve a competitive ratio better than \((2L-2)/L\).* The paper’s construction contrasts taking a short 2-cycle immediately, worth 2, with waiting for a possible length-\(L\) cycle, worth \(L\). The same construction works with fluid mass. Start with unit mass of types \(A\) and \(B\), which form the short cycle. Later, either no long-cycle cohort arrives, or enough mass arrives to form a length-\(L\) cycle with the still-unmatched \(A\) mass; \(B\) expires. If the policy commits fraction \(q\) to short cycles, its ratios on the two trajectories are
\[
\frac{2}{2q}=\frac{1}{q}
\quad\text{and}\quad
\frac{L}{2q+L(1-q)}.
\]
The worst of these is minimized at \(q=L/(2L-2)\), where it equals \((2L-2)/L\). Thus fluid policies can split the cohort, but that split reproduces the mixed choice in the paper’s randomized lower-bound argument. The displayed proof in the paper appears to invert \(p\) in one intermediate line; equalizing its two displayed ratios gives the \(q\) above and the proposition’s stated bound.
I expect this lower bound to survive continuization. In the programme’s trichotomy, that is closest to hardness transferring: the continuum does not remove the online uncertainty behind this result. More precisely, Proposition 2 is a competitive-ratio impossibility, not an NP-hardness theorem. This mirror covers that impossibility and its two-trajectory construction. It does not cover the paper’s experiments or its performance claims for Algorithms 1–3. I would not use the paper’s deterministic lower-bound proposition as another anchor: its all-or-nothing choice is exactly what fluid mass can soften by splitting a cohort.
The authors should recognize the mirror: it preserves their online kidney-exchange objective, cycle cap, arrivals, expiries, and prior-free benchmark, while replacing vertex counts with type masses. Large exchange pools with repeated clinical compatibility profiles provide the regime; the motivating scale is many pairs across a bounded set of exact types, not a small committee of individually specified pairs. Further questions include whether this ratio is attainable over broader type graphs, how the guarantee changes when the policy knows a distribution over future trajectories, and how large the type support can grow before the fluid model stops being useful.
The weak point is the regime’s realism. In kidney exchange, tissue compatibility can be highly pair-specific. If exact compatibility profiles are rare, then the number of types may grow almost as fast as the number of pairs, defeating the high-multiplicity premise. The mirror is strongest for an exchange system where compatibility and transplant values genuinely repeat across a small set of classes; it should not be presented as a model of every exchange pool in the paper.
The strongest case against is about whether the proposed type regime represents the exchange problem the paper studies. In its generated data, tissue incompatibility is assigned at the patient–donor level. A complete type must capture compatibility with every other type, as well as value and expiry behavior. Those full profiles may be nearly unique, so the support size \(\tau\) could grow with the pool instead of staying small. Binning by blood type alone would avoid that problem only by discarding compatibility information that shapes the feasible cycles. This makes the mirror a poor fit for the paper’s experiments and operational claims.
That objection does not defeat Proposition 2’s mirror, though. A finite compatibility graph with recurring profiles is a sensible special case of the paper’s graph model. In that regime, the short-versus-long-cycle construction carries over: if \(q\) is the mass committed to short cycles, the two trajectory ratios are \(1/q\) and \(L/[2q+L(1-q)]\). They meet at \(q=L/(2L-2)\), giving the stated bound. In a large pool, allocating fraction \(q\) of each repeated type is physically interpretable as matching that fraction of its many pairs. The continuous policy’s fractional choice therefore does not invalidate the construction.
One can still argue that this is a narrow result, rather than a mirror of the paper’s main empirical contribution. But the paper has a named online impossibility result, and the mirror preserves its objective, cycle cap, arrivals, expiries, and prior-free benchmark. A narrow computational lower bound is within the programme’s scope; the fact that the proof reduces to a two-trajectory calculation does not make the question ill-posed.
So the defensible negative case is limited: the mirror may have little reach into the paper’s pair-specific data regime. I cannot honestly argue that no worthwhile continuous mirror exists in any scenario. Proposition 2 survives in a plausible repeated-profile regime, and I do not have a fundamental objection to that mirror.
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.