Abstract: We study the price of anarchy of the first-price auction in the autobidding world, where bidders can be either utility maximizers (i.e., traditional bidders) or value maximizers (i.e., autobidders). We show that with autobidders only, the price of anarchy of the first-price auction is $1/2$, and with both kinds of bidders, the price of anarchy degrades to about $0.457$ (the precise number is given by an optimization). These results complement the recent result by Jin and Lu [2022] showing that the price of anarchy of the first-price auction with traditional bidders only is $1 - 1/e^2$. We further investigate a setting where the seller can utilize machine-learned advice to improve the efficiency of the auctions. There, we show that as the accuracy of the advice increases, the price of anarchy improves smoothly from about $0.457$ to $1$.
Introduction
The landscape of online advertising is undergoing a dual shift. First, major platforms like Google Ad Exchange have transitioned from second-price auctions (SPA) to first-price auctions (FPA). Second, the majority of bidding is now handled by "autobidders"—automated agents that maximize total value under Return-on-Investment (ROI) or budget constraints, rather than traditional utility-maximizing bidders who seek to maximize profit (value minus price).
This paper investigates the efficiency of first-price auctions in this evolving environment. Specifically, we analyze the Price of Anarchy (PoA), which measures the welfare loss in the worst-case equilibrium compared to the social optimum. A PoA of 1 indicates perfect efficiency, while lower values signify greater welfare loss.
Methodology
The study employs game-theoretic modeling to analyze two types of bidders:
- Utility Maximizers ($B_u$): Traditional bidders maximizing $Value - Payment$.
- Value Maximizers ($B_v$): Autobidders maximizing $\mathbb{E}[Value]$ subject to $\mathbb{E}[Value - Payment] \geq 0$.
The authors derive PoA bounds by constructing "hard instances" of auctions and developing a novel analytical framework using "proxy" bidding strategies. They also analyze "Value-Payment Frontiers" to bound total welfare in mixed-bidder scenarios. Finally, they model the impact of machine-learned (ML) advice, where a seller uses a signal about bidders' true values to set reserve prices.
Key Insights
- The Fragility of Mixed Environments: A world containing both traditional and automated bidders is less efficient (~0.457) than one with only autobidders (0.5). Traditional bidders can strategically exploit the ROI constraints of autobidders, leading to suboptimal social outcomes.
- Complexity of FPA Strategies: Unlike SPAs, where autobidders can use simple uniform bid multipliers, FPAs require complex, often randomized, and non-uniform strategies for autobidders to remain competitive.
- ML Advice as a Mitigation Strategy: The research demonstrates that even imperfect ML advice can significantly improve efficiency. By using a signal $\gamma$ to set reserve prices, the PoA can be improved smoothly from 0.457 toward 1 as the accuracy of the advice increases.
Key Results
The primary theoretical contributions are summarized in the table below, comparing the PoA of First-Price Auctions against Second-Price Auctions across different bidding populations.
The exact PoA for the mixed-bidding world in an FPA is determined by the optimization: $\min_{t \in [0,1]} \frac{1 + t \ln t}{2 - t + t \ln t} \approx 0.457$. This highlights a significant efficiency gap compared to the traditional "No Autobidding" scenario ($1 - 1/e^2 \approx 0.865$).
Limitations and Future Work
While the results for full autobidding extend to multi-slot auctions, the analysis of mixed-bidder environments in multi-slot settings remains an open challenge. Additionally, the model assumes a break-even ROI threshold; future research could explore how higher profit margin requirements affect equilibrium dynamics. Finally, the assumption of static values does not fully capture the dynamic nature of real-world ad-tech budgets and pacing algorithms.
Summary updated