| paper | d4-conf-aaai-2017-0005 |
| 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: \(\mathrm{P}\) for fixed \(m\) and \(K\); also for fixed \(K\) with variable \(m\) and explicit tables. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a fixed finite set of complete types \(\Theta\), a rational distribution \(\mu\) over those types, directed compatibility \(f\), rational switching costs \(c\), and fixed cycle cap \(L\), choose transfer masses \(y_{\theta\phi}\) and masses \(x_w\) assigned to compatible cycle templates \(w\) of lengths at most \(L\). Transfers must respect the available mass of each source type, and cycle allocations must respect the resulting mass of each type. Maximize the matched fraction \(\sum_w |w|x_w\) minus per-capita switching cost \(\sum_{\theta\ne\phi}c(\theta,\phi)y_{\theta\phi}\).
A high-multiplicity kidney exchange with complete participant types carrying masses \(\mu_\theta\); decision variables are type-to-type transfer masses and cycle-template masses, with objective matched mass minus switching cost. Each unit of mass represents participants who individually receive an integral outcome.
A clinically complete type may encode enough rare distinctions that the fixed-\(|\Theta|\) regime describes few operational exchanges; this limits practical scope, though the proponent explicitly makes the mirror conditional on a small number of complete profiles.
fatal: False
The mirror covers Theorem 2’s type switching and bounded-length cycle packing. It leaves the graph representation results, including Theorems 3–5, and the empirical representation experiments aside.
The strongest mirror is Theorem 2, proved in this paper. It states that, when \(L\) and \(|\Theta|\) are constants, L-FLIP-AND-CYCLE-COVER is solvable in polynomial time. The underlying problem is to change participants’ types at costs and choose a disjoint packing of cycles of length at most \(L\), maximizing the number of matched participants minus the total switching cost. The paper treats chains as cycles with a dummy edge. This is a useful anchor because its decision variables already concern groups of participants with shared attributes, while the actual clearing decision remains a finite, indivisible matching.
A plausible regime is a large national kidney exchange pool: thousands of patient–donor pairs, but far fewer distinct profiles relevant to compatibility and the objective. A type would include the pair’s donor and patient attributes, logistics, and any other information that affects compatibility, switching costs, or value. Thus everyone in a type is interchangeable for this problem. Mass \(\mu_\theta\) is the fraction of the pool with type \(\theta\). The regime is credible where \(\tau\), the number of represented types, is much smaller than the number of pairs; it is not a claim about every kidney exchange.
Here is the continuous problem. The input is an explicit finite type set \(\Theta\); a rational distribution \(\mu\) over its support, with \(\sum_{\theta\in\Theta}\mu_\theta=1\); a directed compatibility function \(f(\theta,\phi)\); rational nonnegative costs \(c(\theta,\phi)\) for changing a participant from type \(\theta\) to type \(\phi\); and a fixed cycle cap \(L\). A cycle template \(w=(\theta_1,\ldots,\theta_\ell)\), for \(2\leq\ell\leq L\), is allowed when every successive compatibility, including the return from \(\theta_\ell\) to \(\theta_1\), holds. Let \(a_\theta(w)\) be the number of times type \(\theta\) appears in template \(w\).
Choose \(y_{\theta\phi}\geq0\), the mass transferred from original type \(\theta\) to type \(\phi\), and \(x_w\geq0\), the mass assigned to each cycle template. The transfers must satisfy \(\sum_{\phi\ne\theta}y_{\theta\phi}\leq\mu_\theta\). The mass available after transfers is \(\nu_\theta=\mu_\theta-\sum_{\phi\ne\theta}y_{\theta\phi}+\sum_{\psi\ne\theta}y_{\psi\theta}\), and cycle allocations must satisfy \(\sum_w a_\theta(w)x_w\leq\nu_\theta\) for every type. The task is to return a feasible choice maximizing \(\sum_w |w|x_w-\sum_{\theta\ne\phi}c(\theta,\phi)y_{\theta\phi}\), the matched fraction minus per-capita switching cost. A cycle allocation is a cohort of mass; each participant in that cohort still receives an integral outcome, either participating in a cycle or not.
I expect this problem to be tractable (Class A) for fixed \(L\) when the type universe and costs are explicitly represented. There are at most \(\sum_{\ell=2}^L|\Theta|^\ell\) cycle templates, so the problem is a linear program with polynomially many variables for fixed \(L\). A finite exchange with \(n_\theta\) participants of each type maps to masses \(\mu_\theta=n_\theta/n\); dividing its switch counts and cycle counts by \(n\) gives a feasible continuous solution with the same normalized objective. The continuous optimum therefore gives a fractional benchmark for the discrete exchange. Whether it also gives a useful additive approximation or a sharper discrete–continuous identity is a natural next question.
This mirror covers the type-switching and cycle-packing problem in Theorem 2. It does not cover the paper’s representation-complexity results or its experiments. In particular, I would not use Theorem 5’s NP-completeness result as a continuous anchor: that theorem concerns finding attributes for an arbitrary graph with vertex-specific edge constraints. Relabeling each such vertex as a population type would leave the hard instance at \(\tau=n\), with masses irrelevant to the constraints. That would be a weaker case for population continuization.
The soft spot is that Theorem 2 is already tractable in the paper’s bounded-\(|\Theta|\), bounded-\(L\) regime. The continuous version preserves the substantive clearing and type-change decisions, but its LP does not show that population multiplicity caused—and then lost—hardness. Its value is a clean high-multiplicity formulation and fractional benchmark, not a new hardness dissolution. It also relies on a small, complete type description and a fixed cycle cap; if those assumptions fail in the intended exchange, this mirror becomes less compelling.
The strongest objection to the proposed mirror is that its useful population regime may not survive a faithful account of compatibility. Theorem 2’s types are exact: two vertices of the same type have the same incoming and outgoing compatibility and the same switching costs. In a clinically detailed exchange, preserving those properties may require including donor and patient immunological profiles, logistics, and health-dependent costs. Those combinations can be rare or unique, so the number of supported types \(\tau\) may grow with the number of pairs. Coarsening types to get a small \(\tau\) can change which cycles are feasible and what attribute changes cost. Defining types by their compatibility neighborhoods does not solve this: those neighborhoods may be unique and depend on the exchange pool itself.
The theorem’s assumptions sharpen that concern. It requires fixed \(L\) and a constant type universe. Its polynomial guarantee says little about an operationally detailed exchange if the exact type universe is enormous or grows with the pool. The proposed continuous model then has two choices: retain the clinically relevant distinctions and lose the repeated-type regime, or aggregate them and solve a different, less faithful clearing problem. An ABO-only exchange is a coherent example of the latter, but it omits compatibility constraints that matter in actual kidney exchange.
That is a real limitation, but it does not defeat the strongest mirror. A large exchange with a genuinely small set of complete, repeated profiles is a coherent high-multiplicity regime. For fixed \(L\), cycle templates over those profiles give a direct linear program; fractional cycle mass can be partitioned into cohorts whose members each receive an integral outcome. The authors could reasonably recognize this as their type-based clearing problem. The fact that it is a simple LP, or that the discrete theorem already gives tractability under its assumptions, is not by itself a reason to reject the mirror.
So the negative case is strong against treating this as a generally faithful model of real kidney exchanges, but weak against the claim that *some* worthwhile continuous mirror exists. I cannot honestly defeat the Theorem 2 anchor in every credible 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.