Gradient ascent makes first-price auctions as efficient as second-price

A new paper from Mete Şeref Ahunbay, Weiqiang Zheng, and Tao Lin (accepted to EC'26) tackles a long-standing puzzle in auction theory: can simple learning algorithms make first-price auctions efficient? In many real-world settings—especially online advertising—first-price auctions have replaced second-price ones, but buyers often rely on gradient-based learning to set bids. The authors prove that when bidders use online gradient ascent, the time-averaged outcome approximates the efficient allocation of a second-price auction.

The mathematical innovation lies in two contributions: first, a potential-function argument that lets the authors iteratively eliminate dominated strategies over time, similar to iterative elimination in game theory. Second, a novel class of cubic candidate potential functions that guarantee no regret against certain quadratic strategy modifications on the probability simplex. While the result assumes discrete bid spaces and complete information, it opens the door to simpler auction designs—advertisers might not need complex bid shading strategies if gradient learning naturally converges to efficiency.