| paper | Optimal Auction Design for Mixed Bidders |
| authors | Xiaohui Bei, Pinyan Lu, Zhiqi Wang, Tao Xiao, Xiang Yan |
| venue | AAAI 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's numbered results are structural mechanism characterizations or cited prior work, while Algorithms 1 and 2 provide no exact complexity or approximation theorem. The proposed mass advertising model is plausible, but it changes fixed single-item supply into per-capita supply and does not restore the paper's profile-level feasibility structure. Under the mandatory computational-anchor gate, the verdict is red.
fails bit a — no named computational result to mirror
The extension covers the paper's single-bidder IC/payment structure and finite-support revenue optimization, but not a computational theorem, the multi-bidder Border feasibility problem, or the conjectured optimality of lookahead auctions.
The strongest honest positive case is conditional, because this paper fails the programme’s named-anchor gate. It contains no numbered theorem, lemma, corollary, or proposition asserting NP-hardness, membership in P, FPT, W[1]-hardness, or a comparable computational classification.
The closest candidate—and my conditional lead—is Theorem 1, proved in this paper. It characterizes the revenue-optimal payments and VM allocation once the UM allocation is fixed. Lemma 4, also proved here, gives the necessary-and-sufficient IC conditions supporting the same reduction. Proposition 1 is Border’s theorem, cited from Border (1991), and is not a new computational result. Algorithms 1 and 2 are numerical procedures without an exact bit-complexity or polynomial-time theorem; moreover, the paper explicitly leaves optimality of the multi-bidder lookahead auction as a conjecture.
If structural algorithmic results are admitted as anchors, I would lead with the following extension of Theorem 1.
Call it Mass Mixed-Bidder Revenue Maximization\(_\infty\). An instance consists of a finite rational type set
\[ \Theta=\{(U,v_j),(V,v_j):j\in[r]\}, \]
where the value \(v_j\) is part of the complete bidder type, a rational population distribution \(\mu\in\Delta_{\mathbb Q}(\Theta)\), and a rational per-capita supply \(\rho\in(0,1)\) of identical advertising impressions. A solution is an anonymous direct mass mechanism, represented by allocation \(x_\theta\in[0,1]\) and payment \(p_\theta\ge0\) for every reported type, satisfying
\[ \sum_{\theta\in\Theta}\mu_\theta x_\theta\le \rho, \]
truthful IR,
\[ 0\le p_{(t,v)}\le v x_{(t,v)}, \]
and, for every true type \(\theta=(t,v)\) and report \(\hat\theta\),
\[ u_\theta(x_\theta,p_\theta)\ge u_\theta(x_{\hat\theta},p_{\hat\theta}), \]
where \(u_{(U,v)}(x,p)=vx-p\) and \(u_{(V,v)}(x,p)=vx\). The objective is to maximize aggregate revenue
\[ \sum_{\theta\in\Theta}\mu_\theta p_\theta. \]
The regime is a large advertising market with \(N\mu_\theta\) near-identical advertisers of each type and \(\rho N\) impression units, with \(N\gg|\Theta|\). Thus mass is actual advertiser-cohort mass, not merely a Bayesian noise distribution. Clearing denominators recovers finite clone markets, while aggregate allocations remain meaningful because supply scales with population. The underlying impression remains indivisible; fractional \(x_\theta\) records allocation across many clones.
This is author-recognizable: it preserves the UM/VM distinction, private class information, private values, IR, IC, allocation, payments, and revenue. It is not a literal mirror of the paper’s one-item model, because a fixed single item becomes a per-capita impression supply. That makes it an extension rather than a direct mirror, but it is strongly motivated by the paper’s own online-advertising setting.
I would expect this finite-support version to be Class A. The IC, IR, supply, and revenue constraints form a polynomial-size rational LP. Theorem 1 supplies the stronger structural reduction: UM payments obey the Myerson envelope, VM payments are first-price, and VM allocations are tied to the function \(g\). Further questions are whether the exact reduction survives continuous value distributions, what approximation rate relates the mass LP to finite-\(N\) markets, and whether a genuine continuum Border theorem is needed for the multi-bidder version.
The weakest point is decisive: under the strict ChoCo rules, Theorem 1 is not a qualifying computational anchor. In addition, keeping one item while letting the bidder population grow makes per-capita allocation vanish and destroys the auction’s scarcity; scaling supply repairs that problem but changes the original optimization problem. So the paper offers a plausible, natural continuous extension, but not a formally admissible positive case unless the anchor rule is broadened to include proved structural algorithms.
The proponent’s own concession is decisive under ChoCo’s anchor rule: this paper has no qualifying computational result. Theorem 1 and Lemma 4 are structural characterizations of IC mechanisms, not complexity or algorithmic theorems. Algorithm 1 is a numerical ODE procedure with no exact bit-complexity or approximation guarantee, while Algorithm 2 optimizes only the proposed lookahead family whose global optimality the paper explicitly leaves as a conjecture. Proposition 1 is cited prior work. Thus there is no named computational theorem here whose population continuization could anchor the programme.
Even if structural results were admitted, the proposed mass model is not really a mirror of Theorem 1. The theorem concerns finitely many named bidders, each privately reporting a value and UM/VM class, competing for one indivisible item. Its allocation \(x_i^t(v)\) is an interim object induced by a mechanism depending on the entire report profile; multi-bidder feasibility is governed by Border-type constraints. A vector of type-level allocations and payments satisfying only
\[ \sum_\theta \mu_\theta x_\theta\le \rho \]
is instead an anonymous quota or screening problem. It does not specify how reports by many agents jointly determine a feasible winner, nor does it preserve the reduced-form feasibility structure that makes the paper’s auction problem an auction problem.
Keeping one item exposes a genuine continuum degeneration. With \(N\) clones and fixed total supply, per-capita allocation and revenue tend to zero. Scaling supply to \(\rho N\) repairs the limit, but it changes the resource model from a single-item auction to a multi-unit market with divisible per-capita supply. That may be a sensible new problem, especially for advertising, but it is not a continuization of the paper’s single-item result. Clearing denominators does not recover the original auction; it recovers a different market whose mechanisms and feasibility constraints must be developed afresh.
The strongest rescue would retain a random finite report profile and study a large-\(N\) limit with scaled supply, using measure-valued mechanisms and a continuum analogue of Border’s theorem. That could be worthwhile auction theory. But it is a new mean-field or multi-unit mechanism-design programme, not a computational mirror of any theorem proved in this paper. Conversely, forcing the model into the proposed finite-support LP produces a well-posed object, but one whose connection to Theorem 1 is only thematic.
So the negative case is strong as a ChoCo screening verdict: the paper supplies no admissible computational anchor, and its natural high-multiplicity repair either degenerates or changes the auction. It is not honest, however, to claim that no continuous advertising-auction model could ever be worthwhile; the online-advertising setting gives a credible high-multiplicity scenario. The defensible conclusion is narrower: this paper does not presently justify a 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.