Papers for

online ad auction designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Complexity and inefficiency of pacing strategies in multi auction bidding

Nash Equilibria in Auctions with Pacing Strategies: Complexity and Inefficiency

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}$.

Mon 28 SeptComputer Science and Game TheoryComputational Complexity

The gist

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.

Open → 2609.34515v1