| paper | d4-conf-atal-2010-0162 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 7
statement extracted from the paper’s text layer
Fix \(m\) and let \(\mu\) range over rational distributions on a finite catalogue of single-minded types \(t=(S_t,v_t)\). For finite bid profiles \(P_N\) whose empirical type distributions converge to \(\mu\), evaluate ARP and the Pareto optimum using the paper’s convention that demands for bundles of size at least two are treated as bids for all goods; retain exact finite-alias deviations when testing false-name-proofness at each \(N\). What is \(\inf_{\mu,(P_N)}\liminf_{N\to\infty}s_{\mathrm{ARP}}(P_N)/s^*(P_N)\), and is it \(2/(m+1)\)?
The society is \(\mu\) over complete single-minded types \(t=(S_t,v_t)\). Its finite approximants have \(n_t/N\to\mu_t\), retain \(m\) indivisible goods, and preserve identity-level deviations to any finite set of aliases. ARP assigns bundles to individual buyers, describable by unnormalized winner counts \(x^N_{t,B}\); its total surplus is compared with the Pareto-optimal total surplus.
With fixed \(m\)-good supply, only finitely many buyers win, so \(\mu\) alone does not identify recipients or encode the finite aliases that determine false-name incentives; the question must remain a limit over finite profiles.
fatal: False
The mirror covers Theorem 7’s ARP efficiency guarantee for single-minded bidders, relying on Theorem 6’s false-name-proofness and Theorem 1’s finite-profile ceiling. It leaves out the Set, MB, and LDS comparisons and the general-valuation results.
My lead is Theorem 1, proved in this paper. It says that for \(m\) goods and at least \(m+1\) bidders, every deterministic, goods-symmetric, false-name-proof mechanism satisfying independence of irrelevant good has worst-case efficiency ratio at most \(2/(m+1)\). The bound still holds when all bidders are single-minded. Here the ratio is the infimum, over bid profiles, of the mechanism’s social surplus divided by the Pareto-efficient surplus. This is an impossibility bound on mechanism performance, not a runtime or NP-hardness result.
A plausible high-multiplicity setting is an online auction platform with a fixed, scarce set of \(m\) goods and many buyers whose single-minded valuations come from a small catalogue. A type is \(t=(S_t,v_t)\): the buyer wants bundle \(S_t\) and values any bundle containing it at \(v_t\). The society is a rational distribution \(\mu\) over the \(\tau\) types, where \(\mu_t\) is their population share and the number of buyers is much larger than \(\tau\). Buyers of one type have the same preferences and face the same prices, as high multiplicity requires. The fixed goods supply preserves the paper’s scarcity; each actual buyer still receives an integral bundle.
The limit needs to remember that the mechanism serves only a few people. I would represent its allocation by \(x_{t,B}\), the limiting number of type-\(t\) buyers assigned bundle \(B\); fractional values of \(x_{t,B}\) represent averages across identical buyers, while each person gets an integral bundle. Feasibility requires \(\sum_{t,B:j\in B}x_{t,B}\leq 1\) for every good \(j\). The surplus is \(\sum_{t,B}x_{t,B}v_t\mathbf 1[S_t\subseteq B]\), compared with the maximum feasible surplus.
Here is the continuous question I would hand to a prover: High-Multiplicity False-Name Ratio. Given \(m\) and a rational distribution \(\mu\) over a finite set of single-minded types, determine the best limiting worst-case efficiency ratio achievable by a family of deterministic, goods-symmetric mechanisms that is feasible, false-name-proof, and satisfies the analogue of independence of irrelevant good. A solution is either a mechanism family with a proved ratio guarantee, or an upper-bound proof ruling out a better one. The family acts on finite populations whose empirical type distributions converge to \(\mu\). Its false-name constraints must retain finite, identity-level deviations: one buyer may replace their report with any finite collection of aliases, with their utility evaluated across those identities. Those deviations change the empirical distribution by \(O(1/N)\), so a rule on \(\mu\) alone would lose them.
I expect the bound in Theorem 1 to survive in this limit. Its witness uses \(m+1\) bidder roles, and each role can have a positive share of the population, leaving arbitrarily many representatives of every role as \(N\) grows. The finite theorem applies along each approximating sequence. For the full ratio frontier, I expect the tractable side of the programme’s trichotomy: an explicit mechanism attains the ceiling below.
That constructive anchor is Theorem 7, also proved here. It says that the adaptive reserve price mechanism has worst-case efficiency ratio exactly \(2/(m+1)\) for \(m\) goods and single-minded bidders. The paper proves its false-name-proofness separately in Theorem 6. Its continuous question is whether the limit of these reserve-price rules achieves the same guarantee for every distribution \(\mu\) in the stated regime. The answer should be yes: the guarantee holds on every finite approximant, and the limiting ratio therefore cannot fall below \(2/(m+1)\); Theorem 1 supplies the matching ceiling. The solution is the limiting allocation and price rule, or a proof of its guarantee. This anchor is a constructive counterpart to Theorem 1, rather than an additional hardness result.
The mirror covers the paper’s single-minded setting, its false-name-proof mechanism class, and its worst-case efficiency ratio. It does not extend the paper to general valuation functions or supply a complexity classification. The paper contains no named P/NP/FPT result; Theorems 1 and 7 are approximation and mechanism-design results.
The weak point is that a distribution over types cannot by itself express an individual’s false-name deviation: a finite set of aliases has zero mass in the limit. The proposed mirror preserves that behavior through finite perturbations around the continuous population. That is a defensible high-multiplicity limit, but authors might regard it as an asymptotic family of their finite problems rather than a new continuum mechanism problem. Fixed scarce supply also means only a few agents receive goods, so the masses mainly describe which valuation classes remain abundant. Those limitations make this a narrower positive case than the programme’s LP over type masses, but the population still becomes the continuous object, and the paper’s central performance bound and matching mechanism give it concrete content.
The central weakness is already in the paper’s results: none states a complexity or algorithmic claim. Theorems 1–4 and 7 concern welfare ratios; Theorems 5–6 establish feasibility and incentive properties. There is no running-time bound, hard computational problem, or pricing problem to carry into a continuous setting. A new question about computing an optimal mechanism for a distribution of buyer types might be interesting, but it would add a computational problem the paper does not study. That makes this a poor fit for ChoCo’s complexity programme.
Theorem 1 is the strongest proposed anchor, but its witness does not directly yield the claimed continuous bound. The theorem bounds a mechanism’s worst-case ratio over finite bid profiles. It does not say that every high-multiplicity sequence, or every fixed distribution \(\mu\), has a bad profile with that ratio. Cloning each bidder role changes the witness, so the finite proof would need to be redone for profiles in which every role has positive population share. If instead the continuous problem ranges over all finite approximants, the theorem’s global bound transfers to each approximant only when its mechanism satisfies the finite assumptions; that is a bound on a sequence of discrete mechanisms, not a result derived from the distribution \(\mu\).
There is also a deeper mismatch in the proposed model. With \(m\) fixed, indivisible goods, at most \(m\) buyers receive anything. If allocations are normalized by population, the type-level allocation tends to zero. If allocations are kept as finite counts \(x_{t,B}\), they describe a few winners, while false-name-proofness still depends on an individual’s exact deviation and the mechanism’s response to it. Those deviations change empirical type frequencies by \(O(1/N)\), which vanishes in \(\mu\). One can preserve them by carrying a finite bid profile alongside \(\mu\), but then the operative strategic object remains discrete; \(\mu\) is background data, not a continuous replacement for the society.
Theorems 6 and 7 share that problem. ARP allocates to at most two bidders, and its prices depend on the highest individual bids and their order. Along finite approximants, its ratio guarantee follows from the finite theorem. But a limiting allocation of population mass is zero; a limiting count of winners needs finite-agent detail that \(\mu\) does not provide. The paper proves a guarantee for a mechanism on finite profiles, not a continuous allocation or pricing rule.
Scaling supply with population is the strongest rescue, and the programme permits such co-modifications in principle. But it changes the auction into one about growing quantities or replicated goods, requiring new valuation and feasibility models. It also does not preserve the paper’s strategic core: a finite set of aliases remains a vanishing share of the market, so a rule based only on aggregate masses cannot capture the original false-name deviations. Retaining those deviations requires keeping individual-level structure.
I would not claim that no author could find an asymptotic auction model worthwhile. A model combining a type distribution with explicit finite-agent deviations is defensible. But that is the negative case’s weak point too: if the reader accepts that enriched hybrid as a continuous population model, the paper has a plausible mirror. My case is that it is a narrow limit analysis of a discrete mechanism-design problem, with no computational result from the paper to mirror and no natural mass-allocation object under its fixed-supply setting.
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.