Pacing Equilibria in Second-Price Auctions with Few Buyers

Abstract

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 computational barrier in the restricted setting, we adopt the cell-decomposition method. Specifically, we partition the solution space into polynomially many cells, each defined by hyperplanes corresponding to a fixed ordering of buyers’ scaled valuations across goods. Within each cell, the equilibrium computation reduces to solving a constant number of linear programs. Notably, our algorithm can also efficiently identify equilibria that optimize key objectives such as revenue or social welfare. To the best of our knowledge, this is the first algorithm that efficiently computes an exact SPPE for a simple and natural class of second-price pacing games.