| paper | d4-conf-ecai-2023-0397 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 4 proves an economic impossibility about which mechanisms can satisfy incentive compatibility, budget balance, and efficiency; it says nothing about computing a solution or the complexity of doing so. The other numbered results characterize or construct mechanisms and establish their economic properties, but provide no computational guarantee, hardness result, or formulation used to compute. The repeated-market extension is coherent, but it cannot supply the missing computational result.
fails bit a — no named computational result to mirror
The proposed batch model extends Theorem 4’s constant-efficiency impossibility to independent copies of the path auction. It does not mirror a computational result, and leaves the paper’s other theorems unaddressed.
The strongest honest case is narrow. The paper has no numbered result classifying a computational problem as, for example, polynomial-time solvable or NP-hard. Its closest anchor is Theorem 4, proved in this paper: in a single-unit network auction, no incentive-compatible, weakly budget-balanced mechanism achieves any fixed positive constant approximation ratio for allocation efficiency in the worst case. The proof uses a referral path \(s\to a\to b\): for bids \(0\le x<\alpha\) and \(1\), an \(\alpha\)-approximation must allocate to \(b\), while incentive compatibility and budget balance force a payment to \(a\) that makes the seller’s revenue negative.
A plausible regime for mirroring that result is a large platform running many separate, repeated referral auctions—for example, similar local service markets, each with its own seller, item, and referral network. A type records an agent’s valuation and exact role in a local network template, including the referral links relevant to the auction. Mass is the fraction of buyers with each complete type. The platform may have millions of buyers while using only a small set of repeated templates and types; each local market still sells one indivisible item, so total supply scales with the number of markets.
Call the resulting question Batch Network-Auction Approximation\(_\infty\). Its input is a finite set of typed, rooted network templates and a binary-rational distribution over copies of those templates. A candidate solution is a direct mechanism, applied to each local market, that outputs an integral winner and payments, is incentive compatible for each buyer’s bid and referral reports, and is weakly budget balanced in each market. The question is whether one such mechanism can guarantee, for every allowed population and truthful profile, aggregate allocation efficiency at least an \(\alpha\) fraction of aggregate efficient welfare. The mechanism’s solution must include that guarantee, or an impossibility proof.
My expectation is that Theorem 4’s non-approximation impossibility transfers to this setting. The population can consist entirely of copies of the two-agent path instance, so averaging over markets does not remove the incentive and budget constraints that cause the deficit. This is a boundary result about mechanism feasibility, not a computational-complexity classification.
The mirror covers Theorem 4 alone. Its weak point is also its limit: the population is continuous across repeated local auctions, rather than across bidders competing in one shared network auction. The authors might recognize this as a meaningful batch extension, but it does not supply the computational landscape ChoCo seeks. I would not present it as evidence that this paper already offers a strong continuous-computation problem.
The case against is strongest on fit with ChoCo’s computational brief. The paper has no numbered result about the running time or complexity of a computational problem. Theorem 4, the proponent’s anchor, is a mechanism-design impossibility: its \(\alpha\) concerns allocation efficiency, not the approximation ratio of an algorithm. The other named results likewise characterize or construct mechanisms and establish incentive, budget, and false-name properties. A new complexity question could be built around these mechanisms, but the paper does not supply a computational result to mirror.
The proposed batch version is coherent, and I grant that Theorem 4’s obstruction transfers: repeat the path \(s\to a\to b\) across independent markets, and the same deficit persists in each copy, so aggregating welfare does not remove it. That makes a plausible extension in mechanism design. But its continuous object is a distribution over repeated local markets, each retaining the original finite auction. The proposed question asks whether a mechanism with certain economic properties exists; it does not identify an algorithmic task, input-size parameter, or complexity bottleneck. Turning counts of copies into rational masses does not supply those missing pieces. To make a computational project, one would need a new task, such as synthesizing a mechanism over a restricted class; the paper’s theorem would not anchor its complexity.
A more faithful attempt would use one large referral network. There, preserving Theorem 4’s witness requires preserving a pivotal gateway whose participation can change access to downstream bidders. If many identical gateways are present, removing one need not disconnect the others’ bidders. If the network has a unique gateway, it remains a special individual, while the downstream crowd supplies the multiplicity. A model with such a finite strategic core and a continuous population behind it might be sensible, but it is a new hybrid model; a block or template model that duplicates the whole path returns to the batch setting. Either could motivate further mechanism-design work, but neither makes Theorem 4 a computational result. The false-name result is an even less promising alternative anchor: its subject is the number and wiring of named replicas, which a mass representation would have to redefine.
The negative case has a real limit: a large platform with a pivotal influencer and many followers could support a worthwhile continuous mechanism-design study, and the authors might recognize it as their problem. I would reject the proposed anchor as evidence for a ChoCo computational mirror, not claim that no meaningful continuous extension of this paper exists in any broader sense.
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.