arXiv · Sep 30, 2026
Efficiency of Generalized Proportional First-Price Auctions Under Auto-bidding
By Yang Cai, Vineet Gupta, Yanchen Jiang et al.
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 ≥ 3 bidders? We resolve both questions using the family of r-proportional first-price auctions (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 PoA ≤ 1.5, complemented by a matching lower bound showing that no anonymous, monotone mechanism can do better. Second, for general n ≥ 2 bidders, setting $r = 2n$ achieves PoA ≤ 2 - 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.