| paper | d4-conf-aaai-2015-0539 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 1
statement extracted from the paper’s text layer
Given finitely many atomic centers \(I\), each period center \(i\) receives a rational mass vector over a finite support of complete pair types, with expected total mass \(k_i\). Types encode center ownership, compatibility, and internal-match behavior. A center may report any submass of its arrivals. Define the clearinghouse allocation by maximum-total fractional packing into legal cycles and chains; in a random center order, subject to earlier centers’ selected matched masses, choose the current center’s maximum attainable matched mass when its credit is nonnegative and its minimum otherwise, then update its credit by the corresponding best-to-worst swing. Is there a polynomially bounded coefficient \(\lambda_i\) for the update \(c_i \leftarrow c_i + \lambda_i(\text{reported mass}-k_i)\) such that full disclosure dominates every underreporting strategy with probability \(1\) and guarantees long-term individual rationality? Determine a sufficient coefficient and prove the guarantees, or give a counterexample.
A finite set of strategic centers controls an atomless mass of donor-patient pairs grouped by complete types. Reports are submass vectors; compatibility between types defines legal fractional cycle and chain packings; credits depend on reported versus expected mass and on each center’s best and worst attainable matched mass.
The discrete proof relies on credit differences returning exactly to zero; arbitrary fractional underreports may produce real-valued balances that never return to equality, and the case gives no replacement argument.
fatal: False
The mirror covers the disclosure incentive in Corollary 1 and the linked long-term individual-rationality guarantee in Corollary 2. It leaves the immediate-IR variant, experiments, and the paper’s unnumbered NP-completeness statement without a direct mirror.
There is a narrow positive case, with an important qualification: the paper has no numbered result classifying a problem as NP-hard, polynomial-time solvable, or similar. The closest numbered anchor is Corollary 1, proved here: under the credit mechanism, revealing all pairs dominates every untruthful strategy with probability \(1\). Its proof uses Theorem 1, which says that a strategy hiding \(j\) pairs is dominated, with probability \(1\), by a strategy identical except that at one state and time it hides \(j-1\). The paper also states that its center-specific matching optimizations are NP-complete, but that statement is unnumbered and cites earlier work, so I would not treat it as the required hardness anchor.
The mirror I would defend is Continuous Credit Kidney Exchange. Picture a large exchange pool with many donor-patient pairs per matching period but relatively few repeated compatibility profiles. The pair types must retain the owner center, the donor and patient compatibility information, and the information needed to determine internal matches. Thus a pair’s type records everything relevant to the matching and the center’s payoff. The centers remain the strategic principals; mass represents many exchangeable pairs of a given type. This could fit a large regional or national pool, though the scenario only works when exact compatibility types recur often enough that the support size \(\tau\) is much smaller than the number of pairs.
Precisely, an instance has a finite set \(I\) of centers and a finite support \(Q\) of pair types, with rational mass for each type. Each period, center \(i\) receives a bounded rational mass vector \(a\), drawn from a specified finite-support distribution with expected total mass \(k_i\). It may report any submass \(x_q\le a_q\); its withheld mass can be matched internally. For every legal cycle or altruist-started chain \(P\), let \(z_P\ge0\) be the mass sent through that exchange pattern. The clearinghouse’s fractional packing must satisfy \(\sum_P m_{qP}z_P\le x_q\) for every type \(q\), where \(m_{qP}\) counts its appearances in \(P\), and maximize total matched mass \(\sum_P |P|z_P\). Each underlying pair still takes part in a complete legal exchange; \(z_P\) is the amount of mass that can follow that pattern.
The question is whether the paper’s credit rule has a fluid version that makes full disclosure dominate every strategy with probability \(1\), while selecting a maximum fractional exchange each period and guaranteeing long-term individual rationality. The version to hand a prover would update credits by \(c_i\leftarrow c_i+\lambda_i(\sum_{q\in Q_i}x_q-k_i)\), then use the paper’s random-order rule: among maximum fractional packings consistent with earlier centers’ choices, favor or disfavor the current center according to its credit balance, and update credits by the difference between its best and worst attainable matched mass. The problem is to find a polynomially computable coefficient \(\lambda_i\) and prove the guarantees—or give a counterexample. This is a direct mirror of Corollary 1’s incentive question, with the paper’s per-pair counts and credit swings replaced by mass.
I expect the matching computation to be tractable: with finite type support, the fractional cycle-packing part can be written as a circulation, and chain packing as a flow; the sequential center-specific optimizations add only linear objectives and constraints. So the computational core looks like Class A, with running time polynomial in \(|I|\), \(\tau\), and the input bit length. The new proof obligation is the credit argument. A mass-valued version needs a sensitivity bound relating a small withheld mass to the change in matched mass, plus conditions ensuring the credit process eventually offsets a deviation. If a suitable \(\lambda_i\) can be bounded using \(\tau\), the positive case is strong; if not, truthfulness may be continuum-specifically hard. Natural follow-up questions are the smallest sufficient credit scale, the effect of unbounded cycle or chain lengths, and whether the result yields an additive approximation for the discrete high-multiplicity exchange.
The weakest point is that the paper’s strategic agents are centers, while the proposed continuum is the population of pairs they control. Keeping ownership and internal compatibility in the type makes this a plausible extension of the authors’ matching mechanism, but it does not continuize the centers themselves. Also, detailed medical compatibility may make most pair profiles unique, so the regime needs a large pool with genuinely repeated *complete* compatibility types. That limits the strength of the positive case; it does not erase the specific mirror question above.
The strongest objection is that Corollary 1 is not a computational result in the sense this programme is trying to chart. It establishes a strategic property of a dynamic mechanism; the paper gives no numbered complexity theorem. The NP-completeness claim for its matching subproblem appears only as an unnumbered statement attributed to earlier work. The proponent’s mirror therefore asks for a new truthfulness theorem, with fractional matching as an algorithmic subroutine. That may be useful mechanism design, but it is a loose fit with the programme’s complexity landscape.
There is also a mismatch between the paper’s players and the proposed continuum. The players are transplant centers; the repeated units are donor-patient pairs. A continuum of centers would make each center measure zero, so unilateral deviations would have no effect and strategy-proofness could become vacuous. Keeping the centers as atoms avoids that degeneration, but leaves the strategic population finite. The pair-mass model is a coherent alternative, though: its types can preserve center ownership and medical compatibility, and a mass of identical pairs can represent whole pairs following whole exchange patterns. Its weakness is empirical compression. If a complete type must preserve all compatibility distinctions relevant to matching and internal matches, the number of types may grow with the number of pairs. A model with repeated compatibility signatures could avoid that, but it needs a convincing regime.
The paper’s proof also does not carry over directly. It relies on discrete changes in match counts and on credit balances returning to equality; with arbitrary submass reports, a center can hide any \(\varepsilon>0\), and the credit process need not revisit the same balance. A fractional packing LP handles the allocation calculation, but says nothing by itself about the intertemporal incentive guarantee. Still, that is an open proof obligation, not a reason the question is unworthy.
So the negative case is weak at its most important point. The pair-mass extension is a plausible, well-posed question for large exchanges, and the proponent’s Corollary 1 anchor survives in that stronger formulation. I can argue that it is not a direct mirror of a computational-complexity result and that its type compression needs justification; I cannot honestly argue 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.