TL;DR
This paper tackles the challenge of advertisers optimizing their bids in online auctions when they have both budget and return-on-investment (ROI) constraints. They propose a novel auto-bidding system that ensures truthful reporting of these constraints is an optimal strategy, and they develop an efficient algorithm to compute these optimal bids, even for non-convex problems.
What Problem Does This Paper Address?
Online advertising is a massive market where advertisers bid for ad slots, often using automated systems. While simple second-price auctions incentivize truthful bidding on value, real-world advertisers face practical limitations: they have a budget they cannot exceed and a desired Return on Investment (ROI) they need to achieve. These constraints mean simply bidding their true value might lead to overspending or insufficient profit. Existing auto-bidding systems often focus on just one of these constraints (budget or ROI), or assume some constraints are public while others are private. This paper addresses the more complex scenario where advertisers have both private budget and private ROI constraints, and the auction mechanism is a standard second-price auction. The core problem is how to design an auto-bidding system that helps advertisers navigate these dual constraints optimally, ensuring they maximize their utility while respecting their financial limits.
Methods
The authors formulate the auto-bidding system design as a mathematical program for each advertiser. This program aims to maximize the advertiser's expected utility subject to their reported budget and ROI constraints. A key contribution is proving that, under their proposed system, advertisers are incentivized to truthfully report their budget and ROI targets. They develop an efficient algorithm to compute the optimal bidding strategy (represented by a "shading parameter" $\beta_i$) for each advertiser, even though the underlying optimization problem is non-convex. They also analyze the system's social welfare and provide a lower bound for the "price of anarchy" (PoA), which measures the inefficiency of equilibria. Furthermore, they prove the existence of a Bayesian Nash equilibrium when all bidders use their auto-bidding system and provide conditions for convergence of an iterated best-response process.
Datasets
The paper uses two types of data for experiments:
- Synthetic Data: Generated by simulating buyers with values drawn from uniform distributions.
- iPinYou Dataset: A real-world dataset from a major demand-side platform containing auction logs. They use this data to estimate competitor bid distributions and buyer value distributions.
Key Insights and Ideas
- Truthfulness is Optimal: The most significant insight is that their auto-bidding system makes it optimal for advertisers to report their budget and ROI constraints truthfully, even when considering mixed strategies. This simplifies strategic decision-making for advertisers.
- Non-Convexity Solved: The core optimization problem is non-convex, which is typically hard to solve. The paper provides a theoretical analysis that allows for an efficient algorithm to find the optimal "shading parameter" $\beta_i$.
- Dual Constraints Matter: The interaction between budget and ROI constraints is crucial. The paper shows how these constraints define a feasible region for bidding strategies and how the optimal strategy balances them.
- Equilibrium Guarantees: The work proves that a stable state (Bayesian Nash Equilibrium) exists when all advertisers use this system, which is important for the system's overall stability and predictability.
- Welfare Analysis: The auto-bidding system achieves a significant fraction of the optimal social welfare, indicating it's not only good for individual advertisers but also reasonably efficient for the market as a whole.
Key Results
- The proposed auto-bidding system ensures truthful reporting of budget and ROI constraints is an optimal strategy for advertisers.
- An efficient algorithm is provided to compute the optimal bidding strategy, which is characterized by a shading parameter $\beta_i$.
- The paper proves the existence of a Bayesian Nash Equilibrium for the auto-bidding system.
- The price of anarchy (PoA) of the mechanism is shown to be at least $\beta$, meaning it achieves at least a $\beta$ fraction of the optimal social welfare.
- Experiments on both synthetic and real-world data (iPinYou) demonstrate that the system effectively respects budget and ROI constraints while maximizing advertiser utility. For instance, actual payments are always below budget, and actual ROIs are above target ROIs.
Limitations and Future Work
- Assumptions on Distributions: The theoretical analysis for equilibrium existence relies on specific assumptions about the value distributions (boundedness and Lipschitz continuity). While these are common in auction literature, they might not hold for all real-world scenarios.
- Single Buyer Constraints: The experimental analysis often focuses on a single constrained buyer interacting with unconstrained buyers. Future work could explore scenarios with multiple constrained buyers.
- Specific Auction Type: The paper focuses on second-price auctions. Extending the framework to other auction types (e.g., first-price) would be valuable.
- Dynamic Environments: The current model assumes static constraints. Investigating how the system performs in dynamic environments where constraints or competitor behaviors change over time is a promising direction.
Summary updated