Pacing Equilibria in Second-Price Auctions with Few Buyers

We present a polynomial-time algorithm for exactly computing second-price pacing equilibria (SPPE) in multi-buyer auction markets with a constant number of buyers. In addition, our algorithm can efficiently find a pacing equilibrium which optimizes key metrics such as revenue or social welfare. SPPEs are central to modern advertising auctions, yet computing or even approximating them is PPAD-hard in general. To overcome this challenge in the restricted setting, we apply the cell-decomposition method. Specifically, we partition the solution space into polynomially many cells defined by hyperplanes, each corresponding to a fixed ordering of buyers' scaled valuations across goods. Within each cell, finding an equilibrium can be reduced to solving a linear program. To the best of our knowledge, our work identifies the first class of second-price pacing games for which an exact SPPE can be computed efficiently.