Pacing Equilibrium in First-Price Auction Markets

Pacing Equilibrium in First-Price Auction Markets, Conitzer et al., arXiv 2019

Our first paper is relevant to Internet advertising as it studies the repeated auctioning of individual items within a larger system managing budgets and budget pacing. Recently, there has been a renewed interest in studying first price auctions in this context which this paper expands on by making the case for using first price auctions for selling individual items in certain settings. 

“single items are rarely sold in true isolation, so considering the broader context is critical when adopting a pricing strategy”

For example, an online advertising campaign usually is an aggregation of small individual events that are not always addressed individually by the advertisers. Rather, a system, such as a proxy bidder, is being used to address individual events via a pacing mechanism that either shades or suppresses bids for individual events to ensure an efficient budget allocation over time.

Apart from making the case for first price auctions in settings with pacing and a limited action set for bidders, the paper takes a different stance than most of the literature with respect to the perspective we usually see and study internet auctions. While it is crucial to study the properties of individual auctions, it is also relevant to understand the broader economic context in which the auctions are occurring.

“Any complex economic system can typically be viewed as the sum of many smaller parts; a microeconomic perspective starts from the smallest parts to build a solution to the whole. As mechanism designers, we often follow this paradigm, investing considerable effort to understand the incentives of a small part, assuming that our efforts will bear fruit in the final complex aggregation.”

In various practical instances, theoretical predictions about the incentives of auction participants actually became observable in practice and induced changes in market design. For example, Edelman and Ostrovsky (2007) showed evidence of cyclical bidding behavior in the early first price internet ad auctions, leading to revenue and efficiency losses. Those predictions, however, also depend on the (budget and time) constraints participants are operating in. Hence, it is useful to take a holistic perspective of the auctioning system and its actors.

Question to ask about real-world systems:

• At what level can bids be set? At the level of individual auctions or indicative for many auctions, together with a budget?
• What is the degree of targeting? 
• How strategic are its actors?

To study an online advertising auction market with budget constrained bidders, the authors define and characterise a first price pacing equilibrium (FPPE) and show it is unique, monotone and computable in polynomial time via the Eisenberg-Gale convex program. Using simulations, they find FPPE is not truthful when bidders are not budget constraint but deviations between valuations and bids vanishes as the market becomes thick. In terms of revenue, FPPE is expected to achieve the same expected revenue as a second price pacing equilibrium (SPPE) due to revenue equivalence.

The FPPE setting is characterised as a single-slot first-price auction market with many bidders and goods, where bidders have potentially heterogeneous valuations and a budget to be spent across all goods. Valuations and budgets are assumed known to the auctioneer. The goal of the auctioneer is to compute a set of pacing multiplier between zero and one that scale the valuations of each bidder to smooth out spending.  Compared to all possible and affordable (budget-feasible) first price pacing mechanism (BFPM), the FPPE has the additional property that there is no unnecessary pacing, meaning the pacing multiplier equals one if the budget exceeds the cost of the aggregate allocation for a bidder.

The key results of the paper are that FPPE

• is unique,
• is revenue-optimal for the seller over all BFPM,
• is a competitive equilibrium, consisting of prices such that (i) allocations maximise bidders utilities given prices and (ii) every item is sold completely (market clearing),
• has good monotonicity properties. In particular, revenue is monotone in the number of bidders, goods and the budget, but not in valuations. Social welfare is monotone in the number of goods only and
• can be computed in polynomial time.

In the final section, the authors study the incentive properties of FPPE by computing the ex-post regret a bidder has in FPPE relative to the situation where she can unilaterally deviate either by setting bids auction by auction or by setting a best response pacing multiplier. The main result is that regret decreases with the number of bidders in the market, as indicated by figure 1. This result is intuitive, as the opportunities for profitable deviations decrease with the number of bidders. 

Last words

While incentive challenges remain when using FPPE in today’s ad marketplaces and most mechanisms are ultimately revenue equivalent, the paper shows that first price auctions have attractive computational and monotonicity properties. Those properties can be practically very relevant, as they provide predictable ways to increase auction revenue and for computing auction outcomes in real-world systems.