| paper | d4-conf-atal-2023-0257 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 6.5 is the closest candidate, but it is a mechanism-design impossibility, not a computational result under the stated criteria. The mechanism-property theorems and the related impossibilities likewise provide no computational anchor, so no continuous question can satisfy both required parts.
fails bit a — no named computational result to mirror
The discussion covers Theorems 4.1, 5.4, and 6.5–6.7, but none states an algorithmic or computational-hardness result; Theorem 3.1 is attributed to prior work.
I can’t make an honest anchor-based case for a continuous mirror here. The paper has named theorems and explicit mechanisms, but it gives no named result about a problem being tractable, hard, or having a particular algorithmic complexity.
The closest candidate is Theorem 6.5, proved in the paper’s full version: every non-deficit, individually rational, Sybil-proof diffusion auction has worst-case social-welfare efficiency ratio zero. That is an important mechanism-design impossibility, but it does not classify the complexity or approximability of a computational problem. Theorem 6.6 gives a related impossibility comparing mechanisms; Theorem 6.7 does so for revenue. Theorem 4.1, proved in the full version, establishes that STM is individually rational, non-deficit, and Sybil-proof; Theorem 5.4 establishes those properties for SCM. Those are mechanism-property results, not complexity anchors. Theorem 3.1 is a dominator-tree fact attributed to Lengauer and Tarjan [9], not a complexity result of this paper.
A continuous version is tempting to imagine for a large marketplace with many buyers in a few exchangeable network roles. But the paper’s buyer type includes both a valuation and a private set of named neighbors. That topology can make the number of distinct types grow with the population. More fundamentally, each auction allocates one indivisible item to one buyer; a distribution over role masses does not itself identify that buyer. A role graph, graphon, or population-scaled supply could make a continuous model possible, but each would change the underlying auction enough that I would not trust the authors or a referee to accept it as the continuous form of Theorem 6.5.
So I have no precise continuous problem to hand to a prover for an anchor in this paper. The weakness is not just that the paper’s examples lack a high-multiplicity story: its central object is an individually structured network of buyers competing for one indivisible item, and the named results concern mechanism properties rather than the computational questions ChoCo is charting.
The strongest case against a mirror is that the paper has no named computational result to continuize. Theorem 4.1 and Theorem 5.4 establish properties of the proposed mechanisms; Theorems 6.5–6.7 are mechanism-design impossibilities. The dominator-tree theorem is a graph fact attributed to prior work. None classifies the complexity of a computational problem or gives an algorithmic result of the kind ChoCo is charting.
Theorem 6.5 is the closest candidate: one could ask whether every individually rational, non-deficit, Sybil-proof auction over a continuous society has zero worst-case welfare ratio. But that remains an axiomatic impossibility question. Replacing finite profiles with a distribution does not turn it into a complexity question, and Theorems 6.6 and 6.7 have the same limitation. The paper’s main theorems could inspire a new computational project—say, designing or evaluating Sybil-proof mechanisms—but that would be a new question rather than a continuous mirror of a computational result in this paper.
There are plausible large-market settings: many buyers could share valuation classes and occupy repeated network roles. The difficulty is that the features driving these theorems are relational and identity-sensitive. The mechanism uses reachability, dominators, and Sybil clusters; compressing buyers to role masses can erase the paths and ownership structure those concepts depend on. A network graphon or a tagged continuum might preserve more detail, but it would require a richer model than a distribution over a fixed finite set of types, and it would still leave no computational theorem here to mirror.
Scaling the supply with the population could make welfare over masses meaningful, as the programme permits. But that changes the single-item setting and its allocation problem. Keeping one indivisible item instead makes the winner an individual of zero population mass: a mass distribution alone does not record that winner or support the paper’s individual utility comparisons. These are not reasons a continuous auction model is impossible; they are reasons the most natural repairs create new mechanism-design questions rather than mirrors of this paper’s results.
So the case against a worthwhile *ChoCo mirror of this paper* is strong: its named results are about mechanism properties, not computational complexity. The broader claim that no structured network regime could ever yield useful computational work is weaker. A carefully chosen high-multiplicity network model might be valuable, but this paper does not supply an anchor for it.
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.