Yonglei Yan

Pacing Equilibria in Second-Price Auctions with Few Buyers

We present a polynomial-time algorithm for exactly computing second-price pacing equilibria (SPPE) in auction markets with a constant number of buyers. SPPE plays a central role in modern advertising auctions; however, computing or even approximating it is PPAD-hard in general. To overcome this comp