| paper | d4-conf-atal-2014-0135 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4 is a welfare-frontier characterization, not a named computational result under the stated gate. Algorithm 1 ranges over an arbitrary mechanism and its full valuation domain, and the paper gives no finite representation or computation guarantee. The proposed \(W_\infty(\mu)\) is a coherent asymptotic extension, but deriving it does not make the paper’s anchor computational.
fails bit a — no named computational result to mirror
Theorem 4 provides no computation on a finite encoding: Algorithm 1 maximizes over arbitrary mechanisms and a continuum of values. The proponent acknowledges the lack of a running-time claim but does not show that this makes the named theorem a computational result under the stated gate.
fatal: True
The proposed limit covers only the high-multiplicity behavior of Theorem 4’s FNP welfare frontier; it leaves Theorems 1–3 and 5 and the paper’s finite-instance mechanism properties without a mirror.
The strongest honest case is a high-multiplicity limit of the paper’s welfare frontier. The paper has no numbered result classifying a problem as NP-hard, in \(\mathrm P\), or by another complexity class. Its best named optimization anchor is Theorem 4, proved here: within the paper’s standing mechanism class, the exponentially decreasing redistribution (EDR) mechanisms are exactly the false-name-proof (FNP) mechanisms that are not welfare-dominated by any other FNP mechanism. The theorem’s proof gives both sides of that claim: Proposition 2 constructs an EDR mechanism that welfare-dominates any given FNP mechanism, and Proposition 3 shows no EDR is dominated by another FNP mechanism. Algorithm 1 gives the construction, though the paper does not establish its running time.
Consider a large membership-based community bidding for one indivisible shared resource. Suppose members’ values fall into a small number of standardized rational-valued classes. A type is a member’s value for the resource; \(\mu_t\) is the fraction of members of type \(t\). It is plausible to have \(n\) members but only \(\tau\) valuation types, with \(\tau\ll n\). This matches the paper’s own bounded-participation motivation and preserves its central manipulation: a member may register additional identities.
My proposed problem is High-Multiplicity FNP Welfare Limit. Its input is a finite set of values \(T\subseteq[0,\bar V]\) and a rational distribution \(\mu\) over \(T\). For each population size \(n\) such that every \(n\mu_t\) is an integer, form the profile \(v^{(n)}\) with \(n\mu_t\) bidders of value \(t\). A solution must give the supremal limiting social welfare
\[
W_\infty(\mu)=\sup_{\mathcal M\in\mathcal F}\limsup_{n\to\infty:\,n\mu_t\in\mathbb Z\ \forall t}\mathrm{SW}(\mathcal M,v^{(n)}),
\]
and a mechanism family attaining it. Here \(\mathcal F\) consists of families of mechanisms defined at every finite population size, satisfying the paper’s standing assumptions and FNP on all finite valuation profiles. The objective is the paper’s aggregate social welfare, not welfare per capita. The population is represented continuously by \(\mu\); the finite approximants retain individual identities and the paper’s exact false-name deviations.
The answer is \(W_\infty(\mu)=0\), attained by the Vickrey auction. To see the upper bound, let \(v_{\max}\) be the highest value with positive mass. Theorem 4 gives, for any \(\mathcal M\in\mathcal F\), an EDR mechanism that welfare-dominates it on every finite profile. For sufficiently large \(n\), at least two bidders have value \(v_{\max}\). An EDR mechanism with parameters \(c_n,r_n\) either does not sell, giving welfare \(0\), or sells and gives welfare \(n c_n\). In the latter case \(r_n\le v_{\max}\), while the EDR conditions imply \(r_n\ge 2c_2\) and \(c_n\le c_2/2^{n-2}\). Thus \(n c_n\le n v_{\max}/2^{n-1}\), which tends to zero. Vickrey is FNP and, with at least two top-valued bidders, has welfare exactly zero. So the limit is explicit and tractable from \((T,\mu)\); the finite EDR frontier collapses as the society grows.
I expect this mirror to be Class A, in the modest sense that the limiting optimum and an attaining mechanism are explicit. It covers Theorem 4’s welfare-dominance result in the regime of many repeated valuation types. It does not mirror the paper’s other results or claim that the paper itself proves a complexity classification. A natural follow-up is to let the top-valued type’s mass shrink with \(n\): when does a small number of exceptional high bidders prevent the welfare frontier from collapsing?
The weak point is that this is an asymptotic family of finite markets, not a literal atomless auction. That choice preserves the paper’s individual-level FNP condition; replacing bidders by infinitesimal agents would make the effect of a single person or a finite number of false identities disappear. The authors should recognize the limit question as theirs because their mechanisms are indexed by population size and their dominance theorem ranges over finite profiles. Still, it is a narrow, easy consequence of their structure—not a new complexity classification.
The proponent’s anchor is not a computational result in the sense ChoCo is meant to study. Theorem 4 characterizes which finite-market mechanisms are welfare-undominated by other false-name-proof mechanisms. Algorithm 1 constructs an EDR mechanism, but its key step ranges over all agent sets and valuation profiles; the paper gives no running-time bound in a compact input representation. The theorem supplies no complexity classification or algorithmic guarantee to continuize.
Even granting the proposed limit as a new computational question, its welfare objective collapses. Let \(v^*\) be the highest value in the finite support of \(\mu\). Along the admissible population sizes, the highest-valued type eventually has at least two members. Vickrey then has social welfare zero. By Theorem 4, an EDR mechanism welfare-dominates any proposed FNP mechanism on every finite profile. On this profile, an EDR either does not sell, giving welfare zero, or sells, giving welfare \(n c_n\). Since sale requires \(r_n\le v^*\), while \(r_n\ge 2c_2\) and \(c_n\le c_2/2^{n-2}\), this welfare is at most \(n v^*/2^{n-1}\). Thus every FNP mechanism has limiting welfare at most zero, and Vickrey attains zero. The masses and values in \(\mu\) matter only enough to guarantee a tie at the top. Dividing by population does not restore a meaningful welfare comparison.
The reason is tied to the paper’s central constraint. FNP compares one agent’s payoff with the payoff from creating finitely many additional identities, and the EDR parameters depend on the resulting integer bidder count. In an atomless society, one person and their aliases have zero mass. Preserve those exact deviations and the proposed “continuous” problem remains a sequence of finite markets, with the welfare limit above. Remove them and the continuum no longer expresses the paper’s FNP condition. A prior-based optimization over EDR parameters is a stronger candidate, but a type distribution alone either gives the same collapsed limit or omits the finite-count information that governs those incentive constraints.
Scaling the resource supply with population could avoid the single-item welfare collapse, and the paper itself points toward multi-unit auctions. But exact false-name incentives would still concern individual identities against a background of continuous mass; representing them requires an additional finite-agent layer. That could motivate a new model, but it does not rescue the proposed mirror of Theorem 4.
The negative case is not airtight: repeated valuation types in a community auction are plausible, and a high-multiplicity study of these mechanisms could be worthwhile. My objection is narrower: this paper’s named result is not a computational result, and the strongest proposed continuous version loses the welfare distinction it set out to study.
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.