Source-linked AI summary
Pacing Equilibrium in First-Price Auction Markets
Vincent Conitzer, Christian Kroer, Debmalya Panigrahi, Okke Schrijvers, Eric Sodomka, Nicolas E. Stier-Moses, Chris Wilkens
TL;DR
The paper asks how to allocate and price ads when proxy bidders manage advertiser budgets and standard auction incentive analyses do not directly apply. It compares first- and second-price pacing equilibria, finding theoretical guarantees for FPPE and small simulated incentives to deviate or misreport.
Problem
Proxy bidders manage campaigns through budgets and aggregate goals, so standard incentive analyses of individual auctions do not directly address which auction rule best allocates and prices ads.
Source: §1 · pp. 2–3Method
Results
FPPE has essentially unique multipliers and monotonicity guarantees, while simulations find very small ex-post shading incentives and vanishingly small incentives to misreport value per conversion or budget.
Source: §1 · pp. 3–4, §8 · p. 31Takeaways & Limitations
The paper concludes that first-price auctions retain useful equilibrium guarantees under budget pacing, and observed incentive concerns are not a major barrier in its simulations.
Source: §1 · p. 4, §8 · p. 31The analysis treats items as sold in isolation rather than modeling multi-slot auctions, which would require substantial changes to the analysis.
Source: §7 · p. 30
Abstract
from arXiv · showhide
Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives -- instead of individual auctions -- and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg-Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex-post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers and regrets all have a positive association in statistical terms.
1. Introduction
The paper studies auction design when advertisers rely on proxy bidders to manage campaign budgets rather than bidding directly on individual impressions. It introduces FPPE and compares its theoretical properties and simulated incentives with SPPE.
1. Introduction
- Modern platforms abstract auction details through proxy bidders, leaving advertisers to specify campaign goals, audience, placement, and budget rather than a per-person bid.The paper frames its question around which auction format best allocates and prices ads when budget is a primary or only strategic lever.Source: §1 · pp. 2–3
1.2. Contributions
- Simulations report very small ex-post incentives to shade bids and vanishingly small incentives to misreport value per conversion or budget.The authors hypothesize that limited ability to manipulate bids coarsely may contribute to the small misreporting incentive.Source: §1 · p. 4
1.1. Pacing Equilibria in Internet Advertising
- Budget management can shade bids with pacing multipliers or throttle bidder participation, trading cheaper impressions for a more representative sample of opportunities.The paper focuses on bid modification and studies pacing in first-price auctions, alongside prior work on second-price pacing.Source: §1.1 · pp. 4–5
1.2. Contributions
- FPPE is defined for buyers participating in many first-price auctions under cross-auction budgets, with multipliers scaling bids and fractional allocation allowed for ties.The paper also reports that monotonicity rules out a platform incentive to enter fake bids.Source: §1.2 · pp. 6, 8
- FPPE has essentially unique pacing multipliers, is revenue-maximizing among budget-feasible pacing multipliers, and yields a competitive equilibrium.Equivalent allocations may differ because of tie-breaking, but the passage says this does not affect revenue, welfare, or utilities.Source: §1.2 · p. 7
- FPPE can be computed through a generalization of the Eisenberg-Gale convex program, yielding a weakly polynomial algorithm and a connection to scalable first-order methods.The passage contrasts this with SPPE, for which the general problem is PPAD-complete.Source: §1.2 · p. 7
- FPPE satisfies monotonicity properties: adding a good weakly increases revenue and welfare, while adding a bidder or increasing a budget weakly increases revenue.Increasing a budget by ∆ can increase FPPE revenue by at most ∆; the passage contrasts this smoothness with SPPE.Source: §1.2 · p. 7
- The simulations find very small ex-ante and ex-post regret when bidders can change only the scale of their utilities, and FPPE always provides higher revenue than SPPE.Welfare splits about evenly between which solution concept performs better.Source: §1.2 · p. 8
2. First price Pacing Equilibria
First-price pacing equilibria model budget management through bid multipliers, with no bidder paced unnecessarily. They exist, have uniquely determined maximal pacing multipliers, and maximize revenue among budget-feasible first-price pacing multipliers.
2. First price Pacing Equilibria
- A pacing multiplier scales each bidder’s value across auctions, while a BFPM requires goods to go to highest paced bidders at the highest paced-bid prices.The market consists of bidders with values and budgets competing for divisible goods in independent single-slot first-price auctions.Source: §2 · pp. 8–9
- An FPPE is a BFPM in which any bidder spending less than their budget is unpaced, with multiplier 1.This rules out pacing an advertiser who is not spending the full budget.Source: §2 · p. 9
2.1. Existence, uniqueness, and structure of FPPE
- The maximal BFPM is an FPPE, and any BFPM with a lower multiplier for at least one bidder has an unnecessarily paced bidder.The maximal multiplier vector is Pareto-dominant among BFPMs.Source: §2.1 · pp. 9–11
- FPPE exist, and their uniquely determined maximal pacing multipliers maximize revenue among all BFPM.The pacing multipliers are unique; allocation may vary with tie-breaking, but bidder utilities, prices, revenue, and the set of budget-constrained bidders remain fixed.Source: §2.1 · pp. 11–12
3. Properties of First-Price Pacing Equilibria
FPPE coincide with equal-rates competitive equilibria, and the paper establishes additional market properties including shill-proofness, price predictability, and core membership. However, FPPE do not necessarily satisfy credibility.
3. Properties of First-Price Pacing Equilibria
- A price-allocation outcome is an FPPE if and only if it is an equal-rates competitive equilibrium (ERCE).In an ERCE, each bidder has a rate describing utility per dollar; bidders who leave budget unspent have rate 1.Source: §3 · p. 12
- FPPE are shill-proof: the seller cannot benefit from adding fake bids.The result follows by comparing revenue with and without shill bids, using the revenue-maximizing property of FPPE.Source: §3 · pp. 13–14
- FPPE do not necessarily satisfy credibility, the property that the platform cannot benefit by misrepresenting what other agents did.The paper gives an example in which the auctioneer can lie about another bid and obtain higher revenue.Source: §3 · p. 14
- FPPE provide price predictability: for any allocation, a bidder either pays her full value or pays her budget.Individual item prices may remain unknown to bidders.Source: §3 · p. 14
- FPPE are in the core, so no bidder group can profitably form a coalition with the seller to make every coalition member strictly better off.The result follows from FPPE being competitive equilibria.Source: §3 · pp. 12, 14
4. Monotonicity and Sensitivity Analysis
This section analyzes monotonicity and sensitivity in FPPE and SPPE, examining how revenue and social welfare respond to changes in bidders, goods, budgets, and valuations. It also bounds spending and social welfare for bidders in S1 under the stated conditions.
4. Monotonicity and Sensitivity Analysis
- FPPE are essentially unique, whereas SPPE may have drastically varying revenue and welfare across equilibria, and budget changes can shift SPPE revenue by at least a factor of 100.The paper contrasts FPPE’s budget stability with this SPPE sensitivity.Source: §4 · p. 15, §4.2 · p. 18
4.1. Monotonicity
- Revenue weakly increases when bidders or goods are added or a budget is increased, but increasing a bidder’s valuation can decrease revenue.The monotonicity proofs rely on FPPE multipliers being maximal among BFPM; for bidders and budgets, the original solution remains a BFPM.Source: §4.1 · pp. 15–16
- Adding a bidder can reduce social welfare by a factor of 1/2, and increasing a bidder’s budget or valuation can also decrease it.The bidder example approaches a 1/2 welfare loss as K grows.Source: §4.1 · pp. 16–17
- Adding a good weakly increases social welfare, but budget and valuation mismatches can make welfare non-monotonic under other changes.A high-value, low-budget bidder can lose out to a low-value, high-budget bidder.Source: §4.1 · pp. 16–17
4.2. Sensitivity Analysis
- Adding ∆ to a bidder’s budget changes revenue by 0 to ∆, while a relative budget increase of 1+∆ bounds new social welfare by (1+∆)SW old.When a budget changes by a factor of 1+∆, pacing multipliers satisfy α ≤ α′ ≤ (1+∆)α.Source: §4.2 · pp. 18–20
- Bidders in S1 cannot increase spending or social welfare, since their bang-per-buck is 1.The passage also states that the pacing multipliers of bidders in S−∪S1 stayed the same.Source: §4.2 · pp. 20–21
5. Algorithms via Convex Programming
The paper adapts the Eisenberg-Gale convex program for quasi-linear utilities to compute first-price pacing equilibria (FPPE). An optimal solution to the program corresponds to an FPPE, and vice versa.
Algorithms via Convex Programming
- Fenchel duality links the program’s single utility rate per bidder to the price-per-utility rate of every item allocated to that bidder.The resulting correspondence lets the authors use the program to compute an FPPE.Source: §5 · p. 21
- An optimal solution to the convex program corresponds to an FPPE with pacing multipliers β_i = α_i and allocation x_ij, and vice versa.The equivalence also gives an alternative route to results about FPPE, including existence and correspondence with ERCE.Source: §5 · pp. 21, 23
- The program’s KKT conditions encode budget expenditure, first-price payments, highest bids on allocated goods, and the rule that leftover budget implies an unpaced bidder.A bidder with leftover budget is unpaced; a bidder who wins an item pays their bid for it.Source: §5 · p. 22
- With rational inputs, the program yields a polynomial-time FPPE algorithm via the ellipsoid method and can also be solved with convex-programming packages or scalable first-order methods.The formulation also supports applying online convex optimization to online FPPE variants, unlike the feasibility-constraint program of Borgs et al. (2007).Source: §5 · p. 23
6. Experiments
The experiments evaluate incentive behavior under FPPE and compare FPPE with SPPE using realistic auction data and synthetic instances. They find low regret in most cases, while FPPE revenue is higher and welfare is usually similar.
6.1. Data
- The realistic instances are built by clustering real auctions into goods and setting bidder budgets to expected value under a uniform random allocation.This budget choice yields a mixture of budget-constrained and unconstrained bidders.Source: §6.1 · p. 24
- The study includes 210 FPPE instances and 420 smaller SPPE instances, which are smaller because SPPE equilibria are harder to compute.Instances draw on seven days of Facebook and Instagram data and vary the numbers of bidders and goods.Source: §6.1 · p. 24
- About 12 minutes sufficed to solve a synthetic instance with 4,000 buyers and 4,000 items, with runtime scaling approximately linearly with valuation-matrix size.Source: §6.1 · p. 24
6.2. Incentive Properties
- 0% median relative ex-post regret across all bidder-and-good breakdowns, with every upper quartile below 2%.The benefit of deviating increases somewhat with the number of goods, but shows no strong dependence on the number of bidders.Source: §6.2 · p. 25, Figure 2 · p. 26
- Of the order of 0.001 relative regret from misreporting, versus 0.01 from ex-post shading; misreporting yields no or negligible gain in almost all cases.Bidders scale reported values and budgets while other bidders’ inputs remain unchanged.Source: §6.2 · p. 26, Figure 3 · p. 27
- Typical relative regret rises with the pacing multiplier, while budgets, pacing multipliers, and regrets show a positive association.The absolute-regret view removes the apparent high-regret point for unpaced bidders; on average, the benefit of positive deviations is small.Source: §6.2 · pp. 27–28, Figure 4 · p. 27
6.4. Robustness
- Synthetic instances with values drawn from unif(0,1) produce qualitatively similar results, though regret tends to be higher.Source: §6.4 · p. 28
6.3. Revenue and Social Welfare
- FPPE revenue is always higher than SPPE revenue, while social welfare is similar in most instances and slightly favors FPPE.The revenue ratios coincide in about 30% of instances and are almost never more than 4.5; welfare comparisons are qualified because the welfare-maximizing SPPE was not computed and many FPPE bidders are budget constrained.Source: §6.3 · p. 28, Figure 5 · p. 29
7. Discussion of Modeling Assumptions
The model represents a static market with known valuations and budgets, capturing valuation correlations but not stochastic arrivals or multi-slot auctions. Its equilibria describe a hoped-for steady state rather than the platform’s evolving control process.
Stochastic valuations
- The model uses deterministic valuations known in advance, capturing correlations but not the stochastic aspect of user valuations.The authors describe it as a discrete approximation to a model that would capture both correlation and stochasticity.Source: §7 · p. 29
Dynamics
- The model does not represent auctions materializing sequentially or the control algorithm tuning pacing multipliers as the day unfolds.The static equilibrium can represent a hoped-for steady state and can provide multipliers for or an initial seed to a dynamic control process.Source: §7 · pp. 29–30
Multiple slots
- The model assumes each item is sold in isolation rather than allocating multiple slots in one auction.Modeling multiple slots would require substantial changes to the mechanism analysis and make the market-equilibrium connection harder to use.Source: §7 · p. 30
8. Conclusion
The paper argues that first-price auctions can yield favorable steady-state properties in pacing-based budget management, while second-price auctions retain advantages. It presents an end-to-end comparison framework rather than claiming one budget-management design dominates all others.
8. Conclusion
- Auction rules must be assessed by their effects on the platform’s aggregate behavior, not only by the properties of individual auctions.The conclusion applies this system-level perspective to feed-based platforms where advertisers commonly control budgets and targeting rather than individual auctions.Source: §8 · p. 30
- First-price auctions provide uniqueness, monotonicity, and computability, while second-price pacing equilibria avoid static shading incentives.Experiments on real ad-auction data suggest static shading incentives may not be a major concern for first-price auctions either.Source: §8 · p. 31
- The authors relate first-price auctions’ strengths in complex advertising systems to uniqueness of equilibria and other properties seen in complex auction settings.They suggest first-price auctions may have a serious role in advertising platforms, while noting the analogy to other settings.Source: §8 · p. 31
- Budget-management design has no one-size-fits-all solution because no system class strictly dominates and trade-offs remain.The paper offers an end-to-end framework for comparing auction formats and other design choices in real-world advertising platforms.Source: §8 · p. 31
Appendix A: Supplemental Experiments on Realistic Instances
The appendix tests a stronger deviation model in which a bidder can effectively choose each individual bid by influencing conversion-rate estimates. Even under this control, FPPE yields more than 70% of optimal utility for nearly all instances.
Appendix A: Supplemental Experiments on Realistic Instances
- The appendix models a bidder’s stronger deviation as choosing optimal individual bids by influencing the platform’s conversion-rate estimates for bidder-good pairs.The platform’s effective bid is conversion rate × value per conversion × pacing multiplier; in practice, advertisers set value per conversion.Source: Appendix A · p. 31
- More than 70% of optimal utility is achieved by FPPE for virtually all instances when bidders can choose individual bids; 75% have less than 30% relative regret.With at least 12 advertisers and 10 users, median regret is zero; regret quartiles generally shrink as competition increases.Source: Appendix A · p. 32
Appendix B: Supplemental Experiments on Synthetic Instances
The appendix repeats the analysis on synthetic data with uniformly drawn valuations as a robustness check against the realistic data’s possible valuation correlations and long tails. It uses a complete-graph model and compares FPPE computed by convex programming with SPPE computed by mixed-integer programming.
Appendix B: Supplemental Experiments on Synthetic Instances
- The synthetic-data experiments test whether low regret and FPPE’s revenue and welfare comparisons with SPPE persist beyond realistic data, and report qualitatively similar insights.The synthetic valuations are uniformly distributed, unlike realistic data that may contain correlated valuations and long tails.Source: Appendix B · p. 32
- Each synthetic instance gives every bidder interest in every good, with valuations drawn independently from unif(0,1).The experiment uses five instances per combination of 2, 4, 6, or 8 bidders and 4 to 14 goods in increments of two.Source: Appendix B · p. 32
- FPPE instances were solved with the convex program using CVX, while SPPE instances were computed with the mixed-integer program; all convex-program instances solved in under 2 ms.SPPE computations were limited to at most 8 bidders and 14 goods because of the mixed-integer program’s scalability.Source: Appendix B · p. 32
B.1. Incentive Properties
The synthetic-instance experiments compare bidder regret under a best-response pacing multiplier and under individual-bid control, then examine misreporting and budget tightness. Regret decreases with market density, while misreporting regret is generally lower than regret from alternative pacing multipliers.
B.1. Incentive Properties
- The appendix compares two deviations: jointly choosing bids through a best-response pacing multiplier or setting individual bids in each auction.The reported maximum relative ex-post regret is computed for each bidder’s optimal budget-constrained response, then summarized across instances.Source: §B.1 · p. 33
- Regret decreases with market density; for 6, 8, and 10 bidders, median regret for alternative multipliers is zero, while individual-bid deviations perform poorly in 2- and 4-bidder instances.The authors attribute the small-market pattern as likely due to the expected gap between the highest and second-highest of uniform draws, which shrinks as O(1/n).Source: §B.1 · p. 33
- Misreporting valuation and budget inputs generally produces lower regret than using an alternative pacing multiplier.The misreports scale reported valuations and budgets by factors from 0.1 to 1.1.Source: §B.1 · p. 33
- When budgets are doubled to create larger pacing multipliers, the regret uptick is slightly higher than for realistic data but qualitatively similar.The modified instances match the preceding experiments except for the twofold budget scaling.Source: §B.1 · p. 33
B.2. Revenue and Welfare
Across instances, FPPE revenue is more often equal to SPPE revenue and is almost never much higher. The welfare-ratio distribution has the same shape as for realistic instances, but on a different scale.
B.2. Revenue and Welfare
- FPPE revenue is the same as SPPE revenue for about 75% of instances, compared with 30% for realistic instances.The comparison is instance by instance.Source: §B.2 · p. 34
- FPPE revenue is almost never more than 1.5 times SPPE revenue, compared with 4.5 times for realistic instances.Source: §B.2 · p. 34
- The FPPE-to-SPPE welfare-ratio CDF has the same shape as for realistic instances, though its ratio axis is at a different scale.Source: §B.2 · p. 34