Generalized proportional first-price auctions improve efficiency with auto-bidding
Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding
Computer Science and Game Theory
Summary
Online ads often use auctions where advertisers let automated systems bid for them to meet goals like value or spending limits. The authors studied a type of auction where winning chances depend on bids raised to a power, finding the best efficiency possible when there are two bidders. They also found a way for any number of bidders to get better than previously believed efficiency by adjusting the power parameter. This means online ad auctions can be both fair and efficient even with automated bidding.
What this means in practice
- •For online advertising platforms: Design auction formats that achieve near-optimal efficiency under auto-bidding by tuning allocation probabilities with bidder count.
- •For auction system engineers: Build auction rules breaking the efficiency barrier of 2 in multi-bidder settings using generalized proportional first-price mechanisms.
A theory result. No direct application yet.
Authors
Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang
Abstract
Auto-bidding is now widely adopted in online advertising platforms, allowing advertisers to specify high-level campaign objectives--such as maximizing total value subject to a return-on-spend (ROS) constraint--rather than manual per-query bids. A central question in algorithmic mechanism design is characterizing the worst-case efficiency loss, or Price of Anarchy (PoA), across auction formats in this prior-free setting. While randomized auctions are known to strictly improve efficiency over deterministic mechanisms for two bidders, two fundamental questions have remained open: (1) what is the optimal PoA for two bidders, and (2) can any mechanism beat the barrier of 2 for general $n \ge 3$ bidders? We resolve both questions using the family of $r$-proportional first-price auctions ($\text{pFPA}_r$), in which each bidder wins with probability proportional to their bid raised to an exponent $r > 0$ and pays their bid upon winning. First, for two bidders, we prove that the standard proportional first-price auction ($r = 1$) achieves a tight $\text{PoA} \le 1.5$, complemented by a matching lower bound showing that no anonymous, monotone mechanism can do better. Second, for general $n \ge 2$ bidders, setting $r = 2n$ achieves $\text{PoA} \le 2 - \frac{1}{4n+1} = 2 - Ω(1/n)$ across all undominated bid profiles, breaking the deterministic barrier of 2 for every finite $n$ and asymptotically matching the known $2 - Θ(1/n)$ lower bound.