# Learning to Coordinate Bidders in Non-Truthful Auctions

arXiv: https://arxiv.org/abs/2507.02801 · HTML: https://mlsanity.com/paper/2507.02801/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 60 references that are in the map.
- First posted on arXiv 3 Jul 2025.

## Builds on (most cited first, 28 of 28)

- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Auto-bidding and Auctions in Online Advertising: A Survey](https://mlsanity.com/paper/2408.07685/) (2024)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Settling the Sample Complexity of Single-parameter Revenue Maximization](https://mlsanity.com/paper/1904.04962/) (2019)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Multi-Item Mechanisms without Item-Independence: Learnability via Robustness](https://mlsanity.com/paper/1911.02146/) (2019)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015)
- [Artificial Intelligence and Auction Design](https://mlsanity.com/paper/2202.05947/) (2022)
- [The Sample Complexity of Up-to-varepsilon Multi-Dimensional Revenue Maximization](https://mlsanity.com/paper/1808.02458/) (2018)
- [Efficient Empirical Revenue Maximization in Single-Parameter Auction Environments](https://mlsanity.com/paper/1610.09976/) (2016)
- [A Sample Complexity Measure with Applications to Learning Optimal Auctions](https://mlsanity.com/paper/1704.02598/) (2017)
- [Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces](https://mlsanity.com/paper/1911.07755/) (2019)
- [Learning Utilities and Equilibria in Non-Truthful Auctions](https://mlsanity.com/paper/2007.01722/) (2020)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Swap Regret and Correlated Equilibria Beyond Normal-Form Games](https://mlsanity.com/paper/2502.20229/) (2025)
- [Estimating Approximate Incentive Compatibility](https://mlsanity.com/paper/1902.09413/) (2019)
- [Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions](https://mlsanity.com/paper/1906.09403/) (2019)
- [Why Do Competitive Markets Converge to First-Price Auctions?](https://mlsanity.com/paper/2001.06074/) (2020)
- [On the Complexity of Equilibrium Computation in First-Price Auctions](https://mlsanity.com/paper/2103.03238/) (2021)
- [Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules](https://mlsanity.com/paper/2303.16388/) (2023)
- [Is Nash Equilibrium Approximator Learnable?](https://mlsanity.com/paper/2108.07472/) (2021)
- [Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets](https://mlsanity.com/paper/2306.07709/) (2023)
- [Complex Dynamics in Autobidding Systems](https://mlsanity.com/paper/2406.19350/) (2024)
- [The Power of Media Agencies in Ad Auctions: Improving Utility through Coordinated Bidding](https://mlsanity.com/paper/2204.13772/) (2022)
- [On the Computation of Equilibria in Discrete First-Price Auctions](https://mlsanity.com/paper/2402.12068/) (2024)
- [Mechanism Redesign](https://mlsanity.com/paper/1708.04699/) (2017)
- [Bidders' Responses to Auction Format Change in Internet Display Advertising Auctions](https://mlsanity.com/paper/2110.13814/) (2021)

## Abstract (arXiv)

In non-truthful auctions such as first-price and all-pay auctions, the independent strategic behaviors of bidders, with the corresponding Bayes-Nash equilibrium notion, are notoriously difficult to characterize and can cause undesirable outcomes. An alternative approach to achieve better outcomes in non-truthful auctions is to coordinate the bidders: let a mediator make incentive-compatible recommendations of correlated bidding strategies to the bidders, namely, implementing a Bayes correlated equilibrium (BCE). The implementation of BCE, however, requires knowledge of the distributions of bidders' private valuations, which is often unavailable. We initiate the study of the sample complexity of learning Bayes correlated equilibria in non-truthful auctions. We prove that the set of strategic-form BCEs in a large class of non-truthful auctions, including first-price and all-pay auctions, can be learned with a polynomial number tilde O(fracnvarepsilon2) of samples of bidders' values. This moderate number of samples demonstrates the statistical feasibility of learning to coordinate bidders. Our technique is a reduction to the problem of estimating bidders' expected utility from samples, combined with an analysis of the pseudo-dimension of the class of all monotone bidding strategies.