Smoothness Meets Autobidding: Tight Price of Anarchy Bounds for Simultaneous First-Price Auctions

Riccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schäfer, Artem Tsikiridis · 2025

Read Smoothness Meets Autobidding: Tight Price of Anarchy Bounds for Simultaneous First-Price Auctions by Riccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schäfer, Artem Tsikiridis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-20908.txt.

Introduction

Riccardo Colini-Baldeschi and co-authors study how well ad auctions work when automated agents place the bids. Advertisers now hand bidding to agents bound by budgets and return targets. The key question is how much welfare is lost versus the best possible outcome.

The team builds a smoothness framework that depends on agent type. Careful balancing of its parameters yields bounds on the price of anarchy. A math program then pins down tight bounds for coarse correlated equilibria. The hosted text is headed as a study of liquid welfare guarantees for autobidding agents. It extends to mixed agent types and richer auction settings. The results guide design of fairer ad markets.

Catalog record

CREATORRiccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schäfer, Artem Tsikiridis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE143 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-20908

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Smoothness Meets Autobidding: Tight Price of Anarchy Bounds for Simultaneous First-Price Auctions Riccardo Colini-Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schäfer, Artem Tsikiridis Abstract Online advertising systems have recently transitioned to autobidding, enabling advertisers to delegate bidding decisions to automated agents. Each advertiser directs their agent to optimize a valuation-dependent objective function subject to return-on-investment (ROI) or budget constraints . Given their relevance, there has been a surge in literature studying the liquid welfare price of anarchy (POA) of fundamental auction formats in autobidding, among which simultaneous first-price auctions (FPA) . These models capture a large range of heterogeneous agent behaviors, requiring advanced proofs to derive tight POA bounds. Recently, Deng et al. (NeurIPS 2024) showed that the POA of FPA for mixed autobidders (i.e., value and utility maximizers) under ROI is 2.18 for additive valuations. We extend the smoothness framework of Syrgkanis and Tardos (STOC 2013) to autobidding. A key contribution in our Extension Theorem is a new technique to balance smoothness parameters across heterogeneous agent types. Determining the best POA bound then reduces to solving a POA-revealing mathematical program. Our approach has three main strengths: (1) Simplicity: We prove smoothness for single-item FPA only. The results for simultaneous FPA follow via our Extension Theorem. For example, by showing smoothness for value and utility maximizers, we obtain the tight POA of 2.18 2.18 for mixed autobidding. (2) Extendibility: Our Extension Theorem adapts to simultaneous FPA with reserve prices and agents with fractionally subadditive valuations and heterogeneous payment sensitivities and target ROI parameters. We establish the first (mostly) tight POA bounds for several models beyond the current autobidding state of the art. (3) Generality: Our Extension Theorem bounds the POA of coarse correlated equilibria (CCE) , which are especially relevant as they naturally arise when agents employ regret-minimizing algorithms. Building on Kolumbus and Nisan (WWW 2022), we show theoretically that CCE arising from hybrid regret-minimizing agents exhibit properties that keep their POA low. 1 Introduction Over the past few decades, the online advertising landscape has undergone a significant transformation with the emergence of autobidding. This paradigm shift enables advertisers to delegate complex bidding strategies to automated agents that consider various factors such as ad performance, campaign constraints, and market dynamics. As a result, advertisers can efficiently manage their campaigns and maximize their return on investment. Autobidding has become increasingly important in the online advertising ecosystem, with a growing number of platforms offering this functionality and the vast majority of advertisers adopting it. According to recent estimates, more than 80% of online advertising traffic is now managed through autobidding agents ( Deng et al. 2024 ). The widespread adoption of autobidding has far-reaching implications for the online advertising industry, influencing the behavior of advertisers, publishers, and ad exchanges alike. In the autobidding world, agents are primarily concerned with reporting high-level constraints for their campaigns, including budget and return-on-investment (ROI) constraints. The budget constraint specifies the maximum payment an agent is willing to make for a given campaign, while the ROI constraint determines the maximum amount an agent is willing to pay for a conversion or impression. This constraint is distinct from the traditional notion of an agents’s valuation, which represents the true value they place on an item. In contrast, the ROI constraint reflects the agent’s budgetary limitations and their desire to achieve a positive return on their investment. Beyond constraints, agents may also be of different types with respect to the objective they want to maximizes. The two most prominent types that have been considered in the autobidding literature are value maximizer and utility maximizers. Value maximizers focus on maximizing the value of the outcome (e.g., high-value conversions), while controlling costs through budget and ROI constraints. On the other hand, utility maximizers want to maximize the difference between the value obtained and price paid. These objectives sit at the extremes of a spectrum that defines the agents’ trade-off between value and payment. Therefore, we also allow agents to express their objectives continuously along this spectrum, enabling them to choose an objective that sits anywhere between value-maximization and utility-maximization. In addition to the shift in bidding strategies, the online advertising industry has also seen a significant transition in auction formats in recent years, particularly with the move from second-price to first-price auctions ( FPA ). This shift has been especially pronounced in display ad markets, culminating in the adoption of first-price auctions by Google Ad Exchange in September 2019 ( Paes Leme et al. 2020 ). The combination of first-price auctions and the increasing reliance on autobidding raises essential questions about the efficiency and performance of FPA within this new autobidding framework. To analyze the efficiency of FPA in the autobidding world, we consider the Price of Anarchy ( POA ) initially introduced by Koutsoupias and Papadimitriou 1999 . Given a valuation and equilibrium class, the POA measures the ratio of the optimal liquid welfare against the liquid welfare achieved in the worst equilibrium. This metric provides a quantitative assessment of the efficiency loss due to selfish behavior in auctions. The notion of liquid welfare was first introduced by Dobzinski and Leme 2014 . In the context of mechanism design, liquid welfare serves as a widely accepted efficiency metric that extends social welfare to scenarios where players are subject to budget constraints. Specifically, a player’s liquid welfare is defined as the minimum value between the utility they derive from an outcome and their available budget. This metric provides a more nuanced understanding of a player’s ability to achieve high values, taking into account their limited financial resources. Encoding the notion of budget in its definition, the optimal liquid welfare represents a meaningful benchmark for measuring the social value of an auction allocation. It acknowledges that players with limited budgets cannot be expected to pay for outcomes that yield extremely high values. By considering the interplay between a player’s budget and the value they receive, liquid welfare offers a more realistic assessment of the social welfare achieved by a mechanism. The POA of FPA in the autobidding world was recently studied by Deng et al. 2024 , both for the model with only value maximizers and the mixed model comprising both value and utility maximizers. Surprisingly, they established a tight bound of 2.18 on the POA for mixed Nash equilibria (MNE) in the mixed-agent model. Their proof employs advanced techniques and leverages deep structural insights into mixed Nash equilibria to achieve this result. A powerful general technique for bounding the POA of games is the smoothness technique . Originally introduced by Roughgarden 2015 for strategic games and later extended by Syrgkanis and Tardos 2013 to composable auctions and mechanism design, its strength lies in its Extension Theorems . In the context of composable mechanisms Syrgkanis and Tardos 2013 , these theorems allow simple POA proofs for pure Nash equilibria in a ‘base mechanism’ (e.g., a single-item first-price auction) to extend to more complex compositions (e.g., simultaneous or sequential auctions) and broader equilibrium concepts (e.g., mixed and correlated equilibria). The combination of being easily applicable and providing strong general bounds makes it particularly appealing. As a result, the smoothness technique has been successfully applied in various settings. However, its application to the

Read the complete text