Revenue Efficiency of Correlated Equilibria in First Price Auctions

Summary

The paper studies revenue guarantees for approximate correlated equilibria (CE) in discrete first-price auctions and translates them into polynomial-in-$k$ convergence rates for no-swap-regret bid dynamics. The central move is to abandon the elegant Feldman-style cascade argument, which propagates a lower bound on the revenue up the bid ladder in $\log k$-many stages and thereby accumulates a $k^{\mathrm{poly}(\log k)}$ error factor, in favour of a dual-fitting analysis. Concretely, the authors formulate a linear program whose optimum $Z^{\star}_{\mathrm{LP}}$ lower-bounds the revenue of any $\epsilon$-approximate CE, exhibit a specific closed-form assignment $(\hat\mu, \hat\lambda)$ to the dual variables, verify it is dual-feasible for a four-way case analysis on which bidders realize the maximum, and use weak duality to conclude that revenue $\ge v_{2} - \Theta(1/k) - \Theta(\epsilon k^{2})$. Combined with the standard concentration argument that no-swap-regret time averages converge to an approximate CE, this yields the first polynomial convergence rate for revenue in this setting: $O(k^{5}/\epsilon^{2})$ rounds under Blum–Mansour, and $\tilde O(k^{2} n/\epsilon)$ under the more recent Anagnostides et al. algorithm. A separate construction shows a matching $\Theta(\epsilon)$ dependence is unavoidable, though the paper leaves the $k^{2}$-versus-constant gap between upper and lower bound open.

The contribution is genuinely useful. The prior quasi-polynomial-in-$k$ dependence made the finite-horizon guarantee essentially vacuous for realistic discretizations, and the dual-fitting approach — new in this context — replaces a delicate log-cascade with a single one-shot LP argument that may also transfer to other equilibrium-quality questions under approximate solution concepts. The two main conceptual limitations are: (i) the $k^{2}$ gap between Theorem 2.6's lower bound and Theorem 2.8's upper bound is neither closed nor accompanied by a plausible route to closing it, and the accompanying conjecture rests only on experiments; (ii) the Bayesian setting is handled purely experimentally, via an ad-hoc "parallel learner per type" construction that side-steps rather than addresses the type-conditional swap-regret question the dual-fitting analysis would need. The manuscript is also in an unusually rough state notationally: several cross-references point to the wrong lemma, one sub-lemma appears twice with different numbers, at least one proof concludes with a bound weaker than the statement it is proving, and a handful of appendix formulas contain slips that a referee cannot verify line-by-line.

Strengths

• Conceptual contribution. The dual-fitting analysis is a new way to bound equilibrium quality under approximate solution concepts, and it converts an inherently multi-stage cascade argument into a one-shot LP-plus-dual-feasibility check. This is a genuinely novel technique in the convergence-rate literature and is plausibly reusable outside first-price auctions.
• Concrete rate improvement. Moving from $k^{O(\log k)}/\epsilon^{2}$ to $O(k^{5}/\epsilon^{2})$ rounds is a real quantitative advance: the prior bound was quasi-polynomial and therefore vacuous for any realistic $k$, while the new bound is polynomial and matches typical horizons in ad-auction settings.
• Matching $\epsilon$-side lower bound. Theorem 2.8 rules out the "$-o(\epsilon)$" slack in $\epsilon$-CE revenue via an explicit two-bidder construction. Even if the $k$-dependence of the slack is left open, the $\Theta(\epsilon)$ lower bound is honest and useful.
• Careful positioning against prior work. Appendix A patiently reconstructs the Feldman-style cascade so the reader can see exactly where the $k^{\mathrm{poly}(\log k)}$ factor arises. The comparison with Dütting et al., Feldman et al., Kolumbus–Nisan, Deng et al., Feng et al., and Bichler et al. is well organized.
• Corroborating experiments. Figures 1–3 (and the Appendix E overlays with the mixed Bayes–Nash CDF) show that the empirical revenue converges near $v_{2}$ well before the theoretical worst case would predict, and provide a helpful sanity check that the LP bound is not artificially loose.

Weaknesses

• Cross-references between statements and their proofs are broken in several places. The sentence introducing the LP lower bound says "In Lemma 3.9 we establish that $Z^{\star}_{\mathrm{LP}}$ lower-bounds the revenue" but that statement is Lemma 3.2; the label "Lemma 3.9" is later reused for the sub-case bound $b_{s}\ge v_{2}-2/k$, which then appears a second time as Lemma 3.13; and the header of Section 3.2 reads "Proof of Lemma 3.9" but immediately opens with a proof of Lemma 3.8. The proof map is real work to reconstruct.
• Lemma 3.11 and its restatement (Lemma D.4) do not agree. Lemma 3.11 targets $b_{s}\ge v_{1}-2/k$ for the tie case $s_{1}=s_{2}=\max$, and this $v_{1}$-bound is what the intermediate inequality $U^{1}(s_{1},s_{-1})+U^{2}(s_{1},s_{-2})\le v_{1}-s_{1}$ points toward. Yet the final line of the printed proof concludes $b_{s}\ge v_{2}-2/k$. Either the lemma should be softened to the $v_{2}$-bound (which is what actually threads through Lemma 3.7's calculation) or the last step needs an extra sentence recovering $v_{1}$. As printed, this is a mismatch inside a load-bearing proof.
• Overlap in the case partition of Lemmas 3.9–3.12. As stated in the main text, Lemma 3.11 covers "$s_{2}=\max$ and $s_{1}=s_{2}$" and Lemma 3.12 covers "$s_{1}=\max$ and $s_{2}=\max$", but these hypotheses are identical while the conclusions differ ($v_{1}-2/k$ vs $v_{2}-3/k$). The intended distinction is presumably that some $i\ge 3$ also achieves the max in Lemma 3.12, but this is only signalled by footnote [4] and not by the lemma statement itself. As written the four cases are not visibly mutually exclusive and exhaustive.
• Elided arithmetic in the dual-feasibility case analysis. The proof of Lemma 3.9 (Section 3.2) never displays the (A) and (B) bounds it "puts together" to reach $s_{1}-(A)-(B)\ge v_{2}-2/k$. Since $s_{1}$ can be as large as $v_{1}$, closing on a $v_{2}$-bound requires a specific intermediate cancellation that is not shown. This is the arithmetic on which the whole $Z^{\star}_{\mathrm{LP}}\ge v_{2}-3/k-\Theta(\epsilon k^{2})$ conclusion rests.
• Inconsistent statement of the prior bound. Theorem 1.4 writes the error factor as $k^{\mathrm{poly}(\log k)}$, while Section 2.2 and Appendix A write $k^{\Theta(\log k)}/k^{O(\log k)}$. Since the paper's central quantitative claim is measured against this factor, using both forms interchangeably is confusing. The intro comparison also silently drops the $\epsilon^{-2}$ factor of the prior $T$-bound, making the improvement look purely on the $k$ side.
• Errors in the Appendix A restatements of the Feldman argument. The "partition" of $\mathcal{S}'$ is written as $(\mathcal{S}', \mathcal{S}'/\mathcal{S}'')$ (self-referential); the switching utility for $s\in \mathcal{S}'\setminus\mathcal{S}''$ is written as $v_{j}-s_{j}$ instead of $v_{j}-\delta(s_{j})$; the switching gain $A$ is defined with a missing $U_{j}(\,\cdot\,)$ around the second expectation; and Claim A.1's quantifier binds $\alpha$ but its body uses $a$. Individually these are typos, but together they make an already sketch-only appendix difficult to check.
• The $\Theta(\epsilon k^{2})$ slack becomes vacuous unless $\epsilon$ is tied to $k$. For fixed $\epsilon$ and growing $k$, the bound collapses to $v_{2}-\Omega(1)$. Meaningful guarantees require $\epsilon = o(1/k^{2})$, which via the swap-regret rate demands $T = \Omega(k^{7})$ — the same $k^{7}$ that appears without derivation in Section 4. Making the joint $(\epsilon, k, T)$ regime explicit would clarify both the theory and the experimental commentary.
• The $k^{2}$ gap between Theorems 2.6 and 2.8 is left entirely open. The upper-bound construction only rules out $-o(\epsilon)$ — nothing in the paper excludes $-\Omega(\epsilon k)$ or $-\Omega(\epsilon k^{2})$. The conjecture that the tight rate is $\Theta(\epsilon)$ is speculative, and the experimental "faster than predicted" behaviour is consistent with any exponent between $0$ and $2$.
• Bayesian setting is only handled empirically, via an ad-hoc device. The "each bidder runs on parallel two different no-swap-regret algorithms, one per valuation" construction decouples types rather than defining a genuine Bayesian-swap-regret analogue. The paper offers no sketch of how the LP or dual-fitting analysis would extend once types are entangled through the type distribution.
• Only Blum–Mansour is exercised in the experiments. Corollary 2.7 quotes concrete round complexities for Anagnostides et al. 2022b (giving $\tilde O(k^{2}n/\epsilon)$), but no head-to-head comparison is shown. Without this, one cannot tell whether the empirically fast convergence is a property of no-swap regret in first-price auctions or a Blum–Mansour-specific artefact.
• Minor notation issues. $\delta$ is simultaneously a failure probability, a switching function, and a Chernoff scale in the Theorem 2.3 proof; Proposition D.6 states the middle term with a bare $s$ where $s^{\star}$ is intended; the Proposition D.6 monotonicity threshold is stated as $2/k$ where the correct threshold from the derivative is $1/k$ (the conclusion still holds but for a different reason); Theorem 2.3's statement drops the $k\log k/\epsilon$ term that its own proof needs from the union bound over $k^{k}$ switching functions.
• The Bayes Mixed Nash CDF is written two different ways. Section 4 gives $F_{P}(x) = 1/(1-x)-1$ (correct), but the very next sentence writes "closely approximates $F_{P}(x)=1-1/x$", which is negative on $[0,1/2]$ and cannot be a CDF. A reader trying to overlay the empirical curve on the analytic target would be misled.

Reproducibility & code

• Missing hyperparameters and seeds. The manuscript states only that Blum–Mansour is used with swap regret $O(\sqrt{kT})$. It never specifies the base no-external-regret learner's step size, the initial mixed strategy, the number of trials, or a random seed. The veritas assessment flags this omission uniformly across all ten headline empirical claims — every claim's reproducibility risk is rated "medium" because a reasonable Hedge-based implementation should approximately reproduce the qualitative inequalities but exact numerical values will differ. Please add a hyperparameter table with the step-size rule and enough seeds to report variance.
• Undefined Bayesian simulation loop. The Appendix E setup runs "parallel" learners per valuation type, but the manuscript does not say whether valuations are resampled each round or held within an epoch, and does not say whether the inactive type-conditional learner receives counterfactual updates. Both of these choices materially affect the effective sample size and hence the convergence transients, and the veritas evaluation lists this as a modest reproducibility gap.
• Horizon discrepancy in the 3-atom Bayesian experiment. The Appendix E text says "$k=30$ and $T=50000$", but the corresponding revenue plot on page 22 extends to roughly $5\times 10^{5}$ rounds. Reproducers cannot tell which horizon produced the reported $\simeq 0.4026$ figure.
• Estimation procedure for the empirical conditional CDF is unspecified. The Appendix E overlays plot a "time-averaged CDF played by bidder $1$ conditional on $v_{1}=1$" against the analytic $F_{P}$. The estimator (which rounds are included, whether smoothed, how the two parallel learners are combined) is never defined, so "closely approximates" is not falsifiable.
• No code/data availability statement. The manuscript does not point to a repository or a data-availability note. Given the number of unspecified hyperparameters above, even a footnote linking to a script with fixed seeds and step-size rules would substantially reduce the medium reproducibility risk the veritas assessment flags across every experimental claim.

Recommended Changes

Essential

• Fix the internal cross-references and lemma numbering. Change the introductory sentence "In Lemma 3.9 we establish that $Z^{\star}_{\mathrm{LP}}$ …" to point to Lemma 3.2, remove the duplicate Lemma 3.13 (or renumber it), and either rename Section 3.2 or move the Lemma 3.8 proof next to its statement so the header matches the body. This addresses the cross-reference weakness above.
• Reconcile the Lemma 3.11 / Lemma D.4 statement and its proof. Either weaken the lemma to $b_{s}\ge v_{2}-2/k$ (matching the concluding line and Lemma 3.7's calculation) or add the missing line that recovers $v_{1}-2/k$ from the intermediate bound. As printed the statement and the proof do not agree.
• Display the intermediate arithmetic in the proof of Lemma 3.9 (Section 3.2). Write out the explicit upper bounds on (A) and (B), so the reader can see how $s_{1}-(A)-(B)\ge v_{2}-2/k$ closes even when $s_{1}=v_{1}\ge v_{2}$.
• Rewrite the case partition of Lemmas 3.9–3.12 so it is visibly exhaustive and disjoint. Put the condition currently hidden in footnote [4] into the Lemma 3.12 hypothesis (e.g. "$s_{1}=s_{2}=\max$ and some $s_{i}$ with $i\ge 3$ also equals the max"), so Lemmas 3.11 and 3.12 no longer look identical.
• Fix the Appendix A slips. In the extended Feldman argument correct the partition to $\mathcal{S}'=\mathcal{S}''\sqcup(\mathcal{S}'\setminus\mathcal{S}'')$, correct the utility to $U_{j}(\delta(s_{j}),s_{-j})=v_{j}-\delta(s_{j})=v_{j}-p-1/k$ in the $\mathcal{S}'\setminus \mathcal{S}''$ case, close the parenthesis around $U_{j}$ in the definition of $A$, and unify the quantifier symbol $\alpha$/$a$ in Claim A.1.
• Reconcile the two forms of the Bayes Mixed Nash CDF in Section 4 / Appendix E. Replace "$F_{P}(x)=1-1/x$" with the correct $F_{P}(x)=1/(1-x)-1=x/(1-x)$ (and cross-check the analogous three-atom formulas $F_{P_{0.5}}$, $F_{P_{1}}$).
• State the prior bound consistently. Choose one of $k^{\mathrm{poly}(\log k)}$ or $k^{O(\log k)}$ for the extended-Feldman error factor and use it everywhere, and include the $\epsilon^{-2}$ factor when quoting the prior $T$-bound so the head-to-head with $O(k^{5}/\epsilon^{2})$ is honest.
• Add the deviation-gain calculation to the proof of Theorem 2.8 (Appendix B). The current text describes the shape of the best deviation but never bounds it by $\epsilon$ against the specific constructed $\mu$; without that step the $\epsilon$-CE property is asserted rather than proved.

Suggested

• Address the $\Theta(\epsilon k^{2})$ vs $\Theta(\epsilon)$ gap. At minimum, add a remark on the joint regime $(\epsilon, k, T)$ where the guarantee is meaningful (e.g. $\epsilon = o(1/k^{2})$, i.e. $T = \Omega(k^{7})$). Ideally, sketch a partial lower bound (an instance family for which the dual-fitting analysis is tight up to constants), or explain what obstructs closing the gap. This directly addresses the "conjecture is speculative" weakness.
• Explain the $k^{7}$ figure in Section 4. Either replace it with the paper's advertised $O(k^{5}/\epsilon^{2})$, or state explicitly that setting $\epsilon = \Theta(1/k)$ (for a fixed $1/k$ target gap) gives the $k^{7}$ number.
• State Claim 1.7 as a high-probability result with a $\log(n/\delta)$ term, matching Corollary 2.7, so the intro claim is not stronger than the formal statement it paraphrases.
• Fix the missing $k\log k/\epsilon$ term in Theorem 2.3. Either add it to the statement or explain why it is absorbed. Please also disambiguate the three uses of $\delta$ (failure probability, switching function, Chernoff scale) in the proof.
• Correct Proposition D.6 — write $k(v_{2}-s^{\star})^{2}$ in the statement, and either restate the monotonicity step with the correct threshold $v_{2}-s^{\star}\ge 1/k$ or replace the case split with "$A$ is convex in $s^{\star}$, minimized at $s^{\star}=v_{2}-1/k$ with value $-1/k$".
• Add a Bayesian sketch. Even a short remark on what "$\epsilon$-approximate Bayes correlated equilibrium" would mean for the LP, or how the parallel-learner architecture relates to a genuine Bayesian-swap-regret guarantee, would let the reader assess whether the Appendix E experiments are evidence for a Bayesian analogue of Theorem 2.6.
• Add an experimental head-to-head with a modern no-swap-regret algorithm. A single panel comparing Blum–Mansour with Anagnostides et al. 2022b would test whether the observed "faster than theory" convergence is algorithm-agnostic.
• Release a script with fixed seeds, learning rates, and initial distributions, and reconcile the $T=50000$ vs $T\simeq 5\times 10^{5}$ discrepancy in Appendix E. Report per-seed variance for Figures 1–3. This addresses the reproducibility gaps flagged above.