Complexity and inefficiency of pacing strategies in multi auction bidding
Nash Equilibria in Auctions with Pacing Strategies: Complexity and Inefficiency
Computer Science and Game TheoryComputational Complexity
Summary
Auctions with many items and bidders can be tricky because each bidder wants to win some items without overspending. This paper studies a simple bidding style where each bidder adjusts all their bids by the same percentage, called pacing. The authors show that sometimes there is no stable way everyone can pace their bids so no one wants to change. They also prove figuring out if a stable pacing setup exists is generally very hard, unless the number of bidders or items is small. When a stable solution exists, they describe exactly how inefficient it can be compared to the best possible outcome.
What this means in practice
- •For online ad auction designers: Identify when pacing-based bidding strategies will not yield stable outcomes, guiding auction design that manages inefficiencies in ad allocation.
- •For ecommerce marketplace engineers: Use complexity results to optimize platform rules when multiple buyers bid across many items with pacing, especially with few bidders or items.
A theory result. No direct application yet.
Authors
Aris Filos-Ratsikas, Charalampos Kokkalis, Mohamad Latifian
Abstract
We introduce and study Auctions with Pacing Strategies (APS) games, a full-information model in which utility-maximizing bidders compete across many simultaneous first-price auctions, each choosing a single pacing multiplier that uniformly scales their values into bids. We settle three central questions. First, we show that there are instances that admit no approximate pure Nash equilibria. Then, we prove that the problem of deciding whether an APS game admits an (approximate) equilibrium is NP-complete in general, but can be solved in polynomial time if either the number of bidders or the number of items is fixed. Finally, when an equilibrium does exist, we characterize its inefficiency exactly, showing that both the Price of Anarchy and the Price of Stability equal $\frac{e}{e-1}$.