Robust Auction Design in the Auto-bidding World

Santiago R. Balseiro, Yuan Deng, Jieming Mao, Vahab S. Mirrokni, Song Zuo

Introduction

In the modern landscape of online advertising, "auto-bidding" algorithms have largely replaced manual bidding. This shift has transitioned the market from a paradigm of utility-maximization to one of value-maximization. This paper demonstrates that by introducing reserve prices and additive boosts—even when based on noisy value signals—auctioneers can simultaneously increase both revenue and social welfare. This finding presents a compelling contrast to classic auction theory, where reserve prices typically improve revenue at the expense of total welfare.

The Challenge of Auto-Bidding

Classic auction theory, exemplified by the famous Vickrey-Clarke-Groves (VCG) auction, assumes bidders are "utility maximizers." Such bidders aim to maximize the difference between the intrinsic value of an ad slot and the price they pay for it. However, most modern advertisers utilize auto-bidding tools that act as "value maximizers." These automated agents strive to acquire as much total conversion value as possible while strictly adhering to a specific budget or Return on Spend (ROS) constraint.

The core problem arises because standard auctions like VCG, which are perfectly efficient and truthful for utility maximizers, become inefficient and non-truthful when value maximizers enter the market. In these auto-bidding scenarios, a bidder with a low actual value might outbid a high-value bidder simply to satisfy their spending constraints. This dynamic leads to a "welfare loss," where the most relevant ads are not shown to the optimal audience.

Proposed Mechanisms: Reserves and Boosts

The authors propose modifying standard auctions—specifically VCG, Generalized Second-Price (GSP), and First-Price auctions—using two primary mechanisms:

  1. Reserve Prices: Minimum bids required for an advertiser to participate in the auction.
  2. Additive Boosts: A "score" added to a bidder's bid to improve their ranking. To maintain proper incentives, this boost is subsequently subtracted from their final payment.

The foundation of their approach relies on the use of $\gamma$-approximate value signals. These are noisy estimates of a bidder's true value, typically generated by machine learning models. The authors develop a Main Technical Lemma: a mathematical framework that translates the accuracy of these noisy signals (denoted by $\gamma$) into guaranteed bounds for how much revenue and welfare the auction will retain compared to a theoretical optimum.

Theoretical Insights

  • The "Reaction" Effect: In a truthful VCG auction, traditional utility maximizers do not alter their behavior in response to reserve prices. However, value maximizers do. Because they operate with a target spend, introducing a reserve price forces them to adjust their bid multipliers, fundamentally changing the auction dynamics.
  • Eliminating Suboptimal Strategies: Properly calibrated reserve prices eliminate bidding strategies that lead to poor market outcomes. By "pruning" the strategy space, the auctioneer effectively guides the auto-bidders toward a more efficient equilibrium.
  • Robustness: The proposed auction designs are highly "robust." They perform well even in heterogeneous environments containing a mix of traditional utility maximizers and modern auto-bidders, and they remain effective even if the value signals provided to the auctioneer are somewhat inaccurate.
  • Welfare and Revenue Synergy: Unlike classic auctions where a strict trade-off often exists between maximizing auctioneer revenue and maximizing social welfare, the auto-bidding paradigm allows these two objectives to move in the same positive direction.

Performance Guarantees and Empirical Results

The paper provides concrete approximation guarantees for different auction types, where $\gamma$ represents the accuracy of the value signal.

Theoretical bounds for social welfare and revenue across different auction mechanisms.

To validate their theoretical bounds, the researchers utilized semi-synthetic data derived from a major search engine's real ad auction logs. They captured the natural variation in bidder values from real data and simulated value-maximizing behavior by creating artificial ROS targets, allowing agents to "learn" optimal bidding strategies via gradient descent.

In these empirical tests, combining reserve prices and boosts led to a welfare lift of up to 67.6% and a revenue lift of nearly 60% when signals were reasonably accurate ($\gamma = 0.7$). Remarkably, even with highly noisy signals ($\gamma = 0.3$), the modified auctions still demonstrated significant improvements over the baseline.

Limitations and Future Work

  • Signal Ceiling: The current theoretical framework requires that reserve prices do not exceed the bidder's actual value. While the authors suggest scaling down signals to mitigate this risk, it requires the auction designer to have prior knowledge of the upper limit of their signal's error.
  • Learning Dynamics: The paper assumes that bidders eventually reach a stable bidding strategy (equilibrium). While empirical results indicate the bounds hold during the "path to convergence," further research is necessary to understand how these auctions perform in highly volatile, non-stationary markets.
  • Signal Sourcing: The study is agnostic regarding how the value signals are generated. Future work could explore the complex interplay between the machine learning models predicting value and the auction mechanisms utilizing those predictions.

Summary updated

Abstract

In classic auction theory, reserve prices are known to be effective for improving revenue for the auctioneer against quasi-linear utility maximizing bidders. The introduction of reserve prices, however, usually do not help improve total welfare of the auctioneer and the bidders. In this paper, we focus on value maximizing bidders with return on spend constraints---a paradigm that has drawn considerable attention recently as more advertisers adopt auto-bidding algorithms in advertising platforms---and show that the introduction of reserve prices has a novel impact on the market. Namely, by choosing reserve prices appropriately the auctioneer can improve not only the total revenue but also the total welfare. Our results also demonstrate that reserve prices are robust to bidder types, i.e., reserve prices work well for different bidder types, such as value maximizers and utility maximizers, without using bidder type information. We generalize these results for a variety of auction mechanisms such as VCG, GSP, and first-price auctions. Moreover, we show how to combine these results with additive boosts to improve the welfare of the outcomes of the auction further. Finally, we complement our theoretical observations with an empirical study confirming the effectiveness of these ideas using data from online advertising auctions.
BibTeX
@inproceedings{balseiro2021robust,
  author = {Santiago R. Balseiro and Yuan Deng and Jieming Mao and Vahab S. Mirrokni and Song Zuo},
  title = {{Robust Auction Design in the Auto-bidding World}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=wgYVM80idI},
}
Figure