Multiplicative Pacing Equilibria in Auction Markets
From MaRDI portal
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 {em 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 {em 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 auction.
Recommendations
- Equilibrium bids in practical multi-attribute auctions
- An equilibrium analysis of the simultaneous ascending auction
- Equilibrium of a sequence of auctions when bidders demand multiple items
- Characterization of equilibrium in pay-as-bid auctions for multiple units
- Monotone Equilibrium in Multi-Unit Auctions
- Equilibrium models for multi-commodity auction market problems
- Towards competitive equilibrium by double auctions
- A new characterization of equilibrium in multiple-object uniform-price auctions
- On the incentive properties of multi-item auctions.
Cites work
- A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium Points
- A Social Equilibrium Existence Theorem*
- AdWords and generalized online matching
- An auction-based market equilibrium algorithm for a production model
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Auction Algorithms for Market Equilibrium
- Budget-management strategies in repeated auctions
- Clinching auctions with online supply
- Computation of Fisher-Gale equilibrium by auction
- Computing large market equilibria using abstractions
- Consensus of Subjective Probabilities: The Pari-Mutuel Method
- Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces
- scientific article; zbMATH DE number 5764830 (Why is no real title available?)
- scientific article; zbMATH DE number 6297730 (Why is no real title available?)
- scientific article; zbMATH DE number 7053386 (Why is no real title available?)
- Multi-unit auctions with budget limits
- Online Optimization with Uncertain Information
- Online Stochastic Matching: Beating 1-1/e
- Online stochastic packing applied to display ad allocation
- Position Auctions with Budgets: Existence and Uniqueness
- Strategy-proofness in the large
- Tractable equilibria in sponsored search with endogenous budgets
Cited in
(6)- Computing large market equilibria using abstractions
- Large-scale contextual market equilibrium computation through deep learning
- The price of anarchy of strategic queuing systems
- Price competition in linear Fisher markets: stability, equilibrium and personalization
- Proportional dynamics in linear Fisher markets with auto-bidding: convergence, incentives and fairness
- Repeated bidding with dynamic value
This page was built for publication: Multiplicative Pacing Equilibria in Auction Markets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080654)
