| paper | d4-conf-ijcai-2003-0082 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1 characterizes strategy-proofness, while Theorems 2 and 3 characterize false-name-proofness; none gives an algorithm, complexity bound, hardness result, or computation-used formulation. The proposed continuous-market question is a plausible extension of that mechanism-design theory, but it cannot supply the missing computational anchor, so bit (a) fails.
fails bit a — no named computational result to mirror
The proposed extension concerns only Theorem 1’s strategy-proofness characterization; it does not cover Theorems 2–3 or the Section 6 protocol construction.
I find no eligible computational anchor in this paper. Theorem 1, proved here, says that every strategy-proof protocol in the paper’s deterministic, individually rational auction model can be described as a price-oriented, rationing-free (PORF) protocol. Theorem 2, also proved here, says that a PORF protocol with weakly anonymous pricing and no super-additive price increase is false-name-proof; Theorem 3 proves the converse under weakly anonymous pricing. These are substantive mechanism-design characterizations, but none asserts a complexity bound or gives an algorithm for a named computational problem. Section 7’s note that a naive implementation calculates prices for all bundles is not a runtime result.
The closest positive lead is a continuous-population analogue of Theorem 1. Imagine a large market of small buyers for replicated bundles of services, with buyers grouped by their complete valuation functions. A type \(t\) has mass \(\mu_t\), and bundle supplies scale with the population. The question would be whether every deterministic, feasible, individually rational, strategy-proof auction for such a population admits a PORF description: prices for each bundle are independent of the individual buyer’s report, and each buyer receives a utility-maximizing bundle, subject to aggregate feasibility. A solution would be a proof of that characterization or a counterexample.
That is a plausible extension of the paper’s central question, but it is not an anchor-based ChoCo case. It adds a continuous population and scaled supplies, and it asks for a mechanism characterization rather than a computational result. The paper does not establish that the high-multiplicity version is tractable, hard, or even computationally studied. Its weakest point is therefore decisive for this programme: the proposed mirror would continue the paper’s mechanism-design theory, while the required computational anchor is absent.
The paper’s best candidate is Theorem 1, and the proposed continuous version is a sensible mechanism-design question. A population of many buyers with repeated valuation functions is plausible; scaling bundle supplies with population size gives mass-level feasibility. I would not reject the mirror on the ground that high multiplicity has no natural auction setting.
The problem is that Theorem 1 is a characterization of strategy-proof protocols, not a computational result. The paper defines no input encoding, computational task, or complexity bound for finding or checking a PORF description. Theorems 2 and 3 have the same limitation: they characterize false-name-proofness through WAP and NSA. So the proposed continuum theorem would extend the paper’s mechanism-design theory; it would not mirror a computational claim of the kind ChoCo is set up to classify.
There is also a real modeling fork. In a nonatomic society, one buyer has mass zero, so changing that buyer’s report leaves the aggregate distribution unchanged. The extension may reduce to a pointwise menu characterization, while aggregate feasibility remains a separate market-clearing question. Giving buyers positive mass preserves strategic influence, but makes the result depend on the chosen atoms or cohorts rather than on a genuinely nonatomic population. Either version could be worth studying; neither is a clear continuation of the paper’s computational content. The false-name results face an additional choice: splitting a zero-mass buyer has no aggregate effect, while letting aliases reproduce a buyer’s full demand requires new rules for how duplicated demand interacts with supply.
One could formulate fresh computational problems around computing VCG prices, checking NSA, or implementing the proposed protocol for repeated buyer types. Those could be worthwhile. The paper, however, supplies no computational result to anchor them, and their definitions would require choosing a valuation representation and an auction-computation task that the paper leaves open.
So the negative case is strong for ChoCo’s purposes: no computational anchor survives, and the nearest continuous analogue moves into a different kind of theory. It does not establish that no continuous auction question could ever be worthwhile; it establishes that this paper does not motivate one as a computational 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.