| paper | d4-journals-jair-2007-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Yes. Exact welfare \(W=W_{\mathrm{full}}\) is attained by finite rational intensities and can be constructed in time polynomial in \(m,\tau,L\), independently of \(\varepsilon\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.5
Given a finite type set \(T=H\times V\), rational masses \(\mu_{h,v}\) summing to one, and a public priority order on \(H\), consider a single indivisible item and one-bit reports. In the limit of finite replications of these types, represent the winner lottery by per-unit-mass intensities \(\lambda_{h,b}\), with total winning probability \(\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}=1\), where \(x_{h,v,b}\) is the mass of type \((h,v)\) reporting \(b\). Among mechanisms satisfying the limiting, per-capita-scaled incentive and ex-post individual-rationality constraints, maximize expected winner value \(\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}v\); determine whether the optimum is attained or only approached.
A high-multiplicity one-item auction with a finite set of valuation and priority types, each given by a rational mass. Each agent reports one bit; the mechanism assigns one indivisible item by a lottery over report cells. Selection intensities and payments must preserve the incentive constraints of finite replications after scaling each agent's vanishing win probability.
The \(O(1/n)\) mechanism gives bidders distinct priority positions; finitely many repeated priority types change that rule, while retaining every position makes the number of types grow with \(n\).
fatal: False
The mirror covers the uniform-value, one-bit, growing-\(n\) welfare guarantee in Theorem 5.5 and its companion profit guarantee. It leaves the general \(n,k\) characterization, arbitrary priors, and finite-\(n\) mechanisms untouched.
The strongest positive mirror is the paper’s large population, one-bit single-item auction. It continuizes the bidders: the object remains one indivisible item, and each agent still sends one bit.
My anchor is Theorem 5.5, proved in this paper. For \(n\) bidders with independent uniform values in \([0,1]\), seller value \(v_0=0\), and two messages per bidder, the priority mechanism \(PG_2(\vec x)\) has welfare loss at most \(9/n\), while the modified priority mechanism \(MPG_2(\vec y)\) has profit loss at most \(9/n\), each relative to the corresponding unrestricted-communication optimum. The thresholds are those of Corollary 4.3: \(x_1=x_n/2\), \(x_{m+1}=1/2+x_m^2/2\) for \(1\le m\le n-2\), and \(x_n=\frac{\sum_{i=1}^{n-1}(\prod_{j=i+1}^{n-1}x_j)(1-x_i^2)}{2(1-\prod_{i=1}^{n-1}x_i)}\); for profit, \(y_1=1/2\) and \(y_{m+1}=1/2+y_m^2/2\). This is a named asymptotic performance result, not a P-versus-NP classification; the paper gives no standard complexity-hardness result.
A plausible high-multiplicity setting is a packet-routing auction with many requesters, few service-priority classes, and a modest number of willingness-to-pay tiers. People in the same priority and value class face the same prices and rules, so they can be grouped as one type. If there are \(N\) requesters and \(\tau\) such classes, the regime of interest is \(N\gg\tau\). A fine valuation grid can approximate the paper’s uniform prior. The class must include priority: the paper’s useful thresholds are discriminatory, so erasing priority would erase part of the problem.
I would hand a prover HM-1Bit Winner-Lottery Welfare. An instance gives a finite type set \(T=H\times V\), rational masses \(\mu_{h,v}\) summing to one, a single item, and a public priority order on \(H\). Each agent privately knows \(v\), sends one bit, and the mechanism sees the report and priority class, not the value within a report class. Write \(x_{h,v,b}\) for the mass of type \((h,v)\) reporting \(b\), with \(\sum_b x_{h,v,b}=\mu_{h,v}\). After reports, the mechanism selects a nonempty report cell \((h,b)\), then chooses one actual agent uniformly from that cell; it charges that winner a payment \(p_{h,b}\). Require one-bit incentive compatibility and ex-post individual rationality, understood as limits of the corresponding finite-population mechanisms. The objective is expected winner value, \(W=\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}v\), where \(\lambda_{h,b}\) is the per-unit-mass selection intensity and \(\sum_{h,v,b}x_{h,v,b}\lambda_{h,b}=1\). A solution is a report strategy, allocation and payment rule, and either a maximizing mechanism or a proof that only a supremum exists. Each realized outcome still awards the whole item to one person; the lottery over a report cell represents the winner’s identity.
The authors should recognize this as their question: the population gets large, the one-bit restriction remains per agent, and the objective is still expected welfare from allocating one item under incentive and participation constraints. The anchor covers the welfare half of Theorem 5.5 directly. The profit half is a natural companion objective, with the same rule and revenue replacing winner value.
I expect a continuum-specific issue for exact welfare optimization, rather than hardness transferring from a discrete problem. Under an atomless uniform value law, a one-bit threshold just below \(1\) can restrict the winner lottery to a top-value slice and make welfare arbitrarily close to \(1\). But any winner lottery absolutely continuous with respect to the population’s type mass has expected value strictly below \(1\), since the set of value-\(1\) agents has zero mass. Thus the supremum can be \(1\) without an attaining mechanism. The \(\epsilon\)-approximation question is simple; whether the exact optimum exists, and how the paper’s priority mechanisms converge, is the more interesting mirror question.
My weakest point is the priority boundary. The paper’s \(O(1/n)\) result uses distinct bidder priorities, while a type-mass model groups identical agents. If those priorities must all become distinct types, then \(\tau\) grows with \(N\), weakening the high-multiplicity case. And the finite mechanism may concentrate its winning probability on a vanishing set of top-priority agents, which a mass-only model may not represent. That is why I would present this as a precise limit question, not claim that Theorem 5.5 transfers unchanged.
Theorem 5.5 is the only proposed anchor, and its result is about a finite-\(n\) sequence: with two messages per bidder, the welfare and profit losses are at most \(9/n\) for the specified uniform-value mechanisms. The quantity \(n\) is doing essential work. It controls the order statistics of the bidders’ values and the number of distinct priority positions. A fixed society distribution \(\mu\) over value types contains neither the sample size nor those positions, so it cannot state the theorem’s convergence rate. Adding \(N\) back as a parameter recovers the family of finite auctions; it does not make the population continuous.
The packet-routing story does not remove that mismatch. With one packet to route, exactly one requester wins. In a mass model, that winner has zero population mass. A lottery over types can describe the winner’s value distribution, but it does not by itself preserve the individual incentives that make the one-bit thresholds meaningful. A single bidder’s report changes no aggregate mass. One can define a scaled selection intensity to recover nontrivial incentive constraints, but that introduces a new limiting mechanism. In the atomless uniform case, welfare can approach \(1\) by selecting from successively narrower top-value slices; the exact maximum is unattained by a lottery absolutely continuous with respect to population mass. The resulting question is mainly about a supremum and its approximation, not the \(9/n\) finite-population result.
Priority creates a separate choice with no satisfying high-multiplicity resolution. The paper’s asymmetric mechanisms assign different roles to bidders who are otherwise ex ante identical. To preserve those roles, priority must be part of the type: with a distinct priority for each bidder, the number of types grows with \(N\), defeating the proposed regime \(N\gg\tau\). A continuum of priority positions avoids finite support only by replacing repeated types with an atomless coordinate. If instead the model uses a fixed number of priority classes, it changes the mechanism and loses the paper’s individualized priority structure. The paper does show that symmetric one-bit mechanisms also become efficient as \(n\) grows, but that gives a limit of the same kind: once \(n\) is removed, the rate and finite-\(n\) comparison that motivated the anchor are gone.
There is also a mismatch with ChoCo’s computational target. Theorem 5.5 is a performance bound, not a complexity result: the paper gives no running-time classification, hardness result, or algorithmic problem over encoded instances. Its central restriction is how many messages bidders may send, not how hard it is to compute the auction. A continuous optimization problem over report masses and winner lotteries could be formulated, but that would be a new mechanism-design project; the proposed \(\lambda_{h,b}\) captures a lottery over winner types, not an algorithm for the paper’s finite-\(n\) problem.
This negative case is not airtight. A scaled-intensity model with a finite number of valuation and priority classes could be a sensible new model for repeated, large-population allocation, and its incentive-constrained optimization might admit useful study. But the more faithfully it preserves Theorem 5.5’s individualized priorities and single winner, the more its computational content depends on finite \(N\); the more it replaces those features with aggregate masses, the less it mirrors the result. I would not spend ChoCo’s time on this anchor.
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.