Multiplicative Pacing Equilibria in Auction Markets

Vincent Conitzer (), Christian Kroer (), Eric Sodomka () and Nicolas E. Stier-Moses ()
Additional contact information
Vincent Conitzer: Econorithms, LLC, Durham, North Carolina 27708; Computer Science Department, Duke University, Durham, North Carolina 27708
Christian Kroer: Industrial Engineering and Operations Research Department, Columbia University, New York, New York 10027
Eric Sodomka: Core Data Science, Facebook Inc., Menlo Park, California 94025
Nicolas E. Stier-Moses: Core Data Science, Facebook Inc., Menlo Park, California 94025

Operations Research, 2022, vol. 70, issue 2, 963-989

Abstract: Budgets play a significant role in real-world sequential auction markets such as those implemented by internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. Motivated by a mechanism used in practice by several companies, this paper considers a smoothing procedure that relies on pacing multipliers : on behalf of each buyer, the auction market applies a factor between 0 and 1 that uniformly scales the bids across all auctions. Reinterpreting this process as a game between buyers, we introduce the notion of pacing equilibrium , and prove that they are always guaranteed to exist. We demonstrate through examples that a market can have multiple pacing equilibria with large variations in several natural objectives. We show that pacing equilibria refine another popular solution concept, competitive equilibria, and show further connections between the two solution concepts. Although we show that computing either a social-welfare-maximizing or a revenue-maximizing pacing equilibrium is NP-hard, we present a mixed-integer program (MIP) that can be used to find equilibria optimizing several relevant objectives. We use the MIP to provide evidence that: (1) equilibrium multiplicity occurs very rarely across several families of random instances, (2) static MIP solutions can be used to improve the outcomes achieved by a dynamic pacing algorithm with instances based on a real-world auction market, and (3) for the instances we study, buyers do not have an incentive to misreport bids or budgets provided there are enough participants in the market.

Keywords: Revenue Management and Market Analytics; ad auctions; repeated auctions; game theory; Nash equilibrium; market equilibrium (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2167 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:2:p:963-989

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().