Randomized Learning-Augmented Auctions with Revenue Guarantees

Theorem 3 and Theorem 4 characterize when truthful auctions exist, but neither asserts polynomial-time solvability, hardness, approximation complexity, or parameterized complexity. Thus bit (a) fails under the explicit anchor rule, regardless of whether the proposed high-multiplicity formulation is recognizable and statable. The opponent also shows that the population masses are formally irrelevant to the universal \(v_{\max}(\mu)\)-based guarantees.

The objection that survived

The universal guarantees depend only on \(v_{\max}(\mu)\), so changing type masses does not change feasibility; the proposed mirror is therefore a high-multiplicity encoding with no population-level decision variable.

What the mirror covers

The proposed mirror covers the feasibility guarantees of Theorem 3 and Theorem 4. It leaves Corollary 5 as a derived application and supplies no qualifying named computational result.

Open questions for a prover

The case FOR (proponent)

The strongest honest positive case is narrow. The paper contains no named complexity result of the form NP-hard, in P, W[1]-hard, or FPT. Its strongest named results, Theorem 3 and Theorem 4, are constructive existence characterizations proved in this paper. Under ChoCo’s strict anchor rule, therefore, this paper has no qualifying computational anchor. Still, if constructive mechanism-design feasibility counts as an algorithmic anchor, the following is the best mirror.

My lead is a high-multiplicity consistency–robustness auction-design problem, mirroring Theorem 3, proved here. A type is a valuation \(v\in[1,H]\); a society is a finite-support rational distribution \(\mu\), where \(\mu_v\) is the fraction of bidders with valuation \(v\). Clearing denominators gives \(N\mu_v\) indistinguishable clones of type \(v\), with \(N\gg\tau\). The type contains the bidder’s complete relevant information; there are no hidden identity-specific prices or budgets. A plausible regime is a large advertising or procurement market with millions of bidders falling into a small number of standardized valuation cohorts.

The item remains indivisible, exactly as in the paper. Randomization is only over which highest bidder receives it. The action is one anonymous, intuitive DSIC auction \(A=(x,p)\), represented compactly by monotone allocation curves and their Myerson payment rules. The auction must be chosen before seeing the realized society \(\mu\); \(\mu\) is not supplied as Bayesian information to the designer. For every rational \(\mu\) and every clone count \(N\) realizing it, let \(v_{\max}(\mu)=\max\{v:\mu_v>0\}\) and let \(R_A(N,\mu)\) be expected total revenue under truthful bidding.

Call the problem HM-CRAD\(_\infty\):

Given \(H,\hat u,\gamma,\rho\), and a finite valuation alphabet \(V\subseteq[1,H]\), decide whether there exists a compact anonymous DSIC intuitive auction satisfying \(R_A(N,\mu)\ge\gamma v_{\max}(\mu)\) whenever \(v_{\max}(\mu)=\hat u\), and \(R_A(N,\mu)\ge\rho v_{\max}(\mu)\) otherwise, for every admissible \(\mu\) and \(N\). A solution is the auction’s allocation/payment formula together with a certificate of monotonicity, feasibility, and the two revenue guarantees. Equivalently, one can ask for the Pareto frontier of feasible \((\gamma,\rho)\).

This is author-recognizable: the bidder types, single item, DSIC constraint, anonymity, prediction \(\hat u\), consistency, robustness, and revenue-over-maximum-valuation objective are unchanged. Only the bidder population is represented through rational type masses. The expected classification is Class A. Theorem 3 already supplies a closed-form logarithmic allocation and payment rule, and its condition \( \gamma+\rho\ln\max\{\hat u,H\rho/\gamma\}\le1 \) gives the natural full-domain boundary. For a restricted finite alphabet \(V\), feasibility may become easier; proving the exact finite-support boundary would itself be a small high-multiplicity result.

A second, worthwhile extension mirrors Theorem 4, also proved here. Call it prediction-error-profile auction design. The input additionally contains a non-increasing robustness function \(\rho:[1,H]\to[0,1]\), represented, for example, by a piecewise rational/logarithmic formula. The question is whether one universal anonymous DSIC intuitive auction guarantees revenue at least \(\rho(\eta)v_{\max}(\mu)\), where \(\eta=\max\{v_{\max}(\mu)/\hat u,\hat u/v_{\max}(\mu)\}\), for every rational high-multiplicity society. Theorem 4 predicts feasibility exactly when \( \rho(H/\hat u)+\int_1^{\hat u}\rho(z)/z\,dz+\int_1^{H/\hat u}\rho(z)/z\,dz\le1 \). For well-represented function classes, this is again naturally Class A; arbitrary function representations could introduce a separate representation or integration problem. Corollary 5 need not be a third anchor: it is an application of Theorem 4 rather than an independent computational result.

The weakest point is substantial. The paper’s lower-bound argument for Theorem 3 and Theorem 4 uses a single bidder. Thus the population distribution may add no essential difficulty or insight: the same guarantee already has to survive a one-type society. Moreover, a literal atomless auction creates an incentive problem, since an individual has zero mass and cannot affect the aggregate outcome. The proposed mirror therefore needs rational-clone semantics, or a carefully defined cohort-level limit; that is an extension, not a direct atomless reformulation. Making \(\mu\) known to the designer would be worse, because it would turn the problem into a known-distribution or Bayesian auction problem absent from the paper.

So the best positive judgment is: an author-recognizable high-multiplicity extension exists, and it is plausibly tractable by the paper’s explicit allocation constructions. But strictly under the ChoCo rubric, the paper should be recorded as having no qualifying named computational anchor. Its mirror is a promising Class-A extension of constructive mechanism-design theorems, not evidence that the paper itself contributes to the computational continuization landscape.

The case AGAINST (opponent, writing after the proponent)

The strict negative verdict is decisive at the outset: this paper has no qualifying computational anchor. Theorem 3 and Theorem 4 are existence characterizations for truthful auctions, not complexity results about an input problem. They contain no claim of polynomial-time solvability, NP-hardness, parameterized complexity, or approximation complexity. Corollary 5 only instantiates Theorem 4. Under ChoCo’s stated anchor rule, there is therefore no theorem whose computational content needs a continuous mirror.

Even if constructive auction design is admitted as an anchor, the proposed mirror of Theorem 3 does not make the population a meaningful computational object. The guarantee is required for every valuation profile, and the auction is chosen independently of the realized society. Replacing a profile by a distribution \(\mu\) merely changes its encoding. The relevant constraints are already forced by societies supported on one bidder type: \(\mu=\delta_v\). The paper’s own necessity proof uses precisely that case. Adding millions of indistinguishable clones does not introduce a mass-transfer problem, a distributional optimization problem, or a new algorithmic degree of freedom.

This is more fundamental than saying that “continuization does not help.” The objective is revenue relative to \(v_{\max}\) from one indivisible item. It is an extremal, not an aggregate, objective. The mass of low-valued bidders is irrelevant to the benchmark, while the mass of high-valued bidders matters only through whether there is a highest bidder and whether there is competition. Thus the full society distribution is discarded by the paper’s objective before any algorithm is designed.

The proposed finite alphabet \(V\) does not repair this. If bidders still have the paper’s domain \([1,H]\), the distribution is redundant. If the valuation domain is restricted to \(V\), any changed feasibility boundary comes from deleting valuation points, not from high multiplicity. That is a finite-domain mechanism-design variant, not a continuous-population mirror. A finite list of valuation cohorts can be a sensible modelling choice, but it does not create the kind of population-level optimization that ChoCo is meant to study.

The atomless version is worse. In a genuinely nonatomic society, an individual highest-valued agent has measure zero. If the “intuitive” auction allocates only to exact highest bidders, the set receiving positive allocation can have measure zero, so aggregate allocation and revenue collapse. If one replaces the maximum by an essential supremum, or allocates to a positive-measure top quantile, that is a recognizable repair only by changing the auction’s benchmark and its “highest bidder(s)” structure. If one instead uses rational-clone semantics, as the proponent suggests, one has avoided the atomless limit—but then one is back to a finite-agent auction whose guarantees already hold profile by profile.

Theorem 4 fails for the same reason. Its integral condition

\[ \rho(H/\hat u) +\int_1^{\hat u}\frac{\rho(z)}{z}\,dz +\int_1^{H/\hat u}\frac{\rho(z)}{z}\,dz \le 1 \]

is an integral over valuation levels, not over a society distribution. It arises from the single-bidder allocation curve and remains valid independently of how many bidders occupy each valuation type. Calling \(\rho\) a piecewise rational or logarithmic input could produce a new real-arithmetic or representation-complexity question, but that question concerns encoding and integration of the robustness function, not continuizing the population.

There are two obvious ways to make \(\mu\) matter, but both cease to mirror the paper. One can let the auction depend on \(\mu\), or optimize expected revenue under a distribution over societies. That turns the problem into known-distribution or Bayesian mechanism design, whereas this paper explicitly assumes no statistical information and requires worst-case guarantees for every valuation profile. Alternatively, one can normalize revenue per capita or benchmark against aggregate welfare. With one indivisible item, per-capita revenue tends to zero as the population grows; avoiding that degeneration requires changing the environment to multi-unit or divisible allocation.

The honest weakness in this negative case is that large cohorts of equal-valued bidders are entirely plausible, so high multiplicity is not nonsensical here. But plausibility of cohorts is not enough. For this paper, anonymity, the maximum-value benchmark, and the single-item constraint ensure that cohort masses never become the object of the theorem. The best continuous-looking reformulations are either a redundant encoding of the existing universal auction problem, a degenerate atomless limit, or a new Bayesian/multi-unit problem. Neither Theorem 3 nor Theorem 4 therefore supports a worthwhile ChoCo mirror.

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.