No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints

Read original: arXiv:2404.09832 - Published 4/16/2024 by Gagan Aggarwal, Giannis Fikioris, Mingfei Zhao

👨‍🏫

Overview

The paper explores the problem of designing automated bidding algorithms for online advertising platforms that run a mixture of first-price and second-price auctions.
The goal is to optimize the advertiser's objective (e.g., value, revenue) while satisfying constraints like average return on investment (ROI) and budget.
The authors consider a stochastic setting where the advertiser's value and the highest competing bid are drawn from an unknown distribution in each round.
They design a low-regret bidding algorithm that can achieve near-optimal performance compared to the best possible Lipschitz function that maps values to bids.
The result applies to a wide range of auction types, including any mixture of first-price and second-price auctions.

Plain English Explanation

Online advertising platforms often use automated bidding to help advertisers optimize their ad campaigns. Automated bidding, or "autobidding," allows advertisers to set their objective (e.g., maximizing value or revenue) and constraints (e.g., average ROI, budget), and the platform's algorithms will automatically adjust the advertiser's bids to achieve the best outcome.

In this paper, the researchers are looking at how to design these autobidding algorithms to work well in situations where the platform is running a mixture of first-price and second-price auctions. In a first-price auction, the winner pays their own bid, while in a second-price auction, the winner pays the second-highest bid.

The researchers consider a setting where the advertiser's value for the ad and the highest competing bid are drawn from an unknown distribution each time an ad is auctioned. They develop a bidding algorithm that can achieve near-optimal performance compared to the best possible way the advertiser could map their value to a bid, while still satisfying their constraints. This algorithm works well across a wide range of auction types, including any combination of first-price and second-price auctions.

Technical Explanation

The paper studies the problem of designing online autobidding algorithms to optimize an advertiser's objective (e.g., value, revenue) subject to ROI and budget constraints when the platform is running a mixture of first-price and second-price auctions.

The authors consider a stochastic setting where there is an item for sale in each of T rounds, and in each round, buyers submit bids and a auction is run to sell the item. They focus on one buyer (the advertiser) who may have budget and ROI constraints. They assume the buyer's value and the highest competing bid are drawn i.i.d. from some unknown (joint) distribution in each round.

The authors design a low-regret bidding algorithm that satisfies the buyer's constraints. Their benchmark is the objective value achievable by the best possible Lipschitz function that maps values to bids, which is rich enough to best respond to many different correlation structures between value and highest competing bid.

The main result is an algorithm with full information feedback that guarantees a near-optimal $\tilde{O}(\sqrt{T})$ regret with respect to the best Lipschitz function. This result applies to a wide range of auctions, most notably any mixture of first-price and second-price auctions (where the price is a convex combination of the first and second price). The result holds for both value-maximizing and quasi-linear utility-maximizing buyers.

The authors also study the more challenging bandit setting, where the algorithm only observes the auction outcome (e.g., the winning bid) and not the full information about the bids and values. They show an $\Omega(T^{2/3})$ lower bound on the regret for first-price auctions, demonstrating a large gap between the full information and bandit settings. They also design an algorithm with $\tilde{O}(T^{3/4})$ regret for the bandit setting when the value distribution is known and independent of the highest competing bid.

Critical Analysis

The paper makes several important contributions to the problem of automated bidding in online advertising auctions. The authors' insights on the differences between the full information and bandit settings are particularly noteworthy, as they highlight the challenges of making decisions with limited feedback.

One potential limitation of the research is that it assumes the advertiser's value and the highest competing bid are drawn from an unknown but fixed distribution. In reality, these values may change over time due to factors like seasonality or market conditions. An extension of this work to handle non-stationary distributions could be valuable.

Additionally, the paper focuses on optimizing a single advertiser's objective, but in practice, online platforms must balance the objectives of many different advertisers. Exploring how to design autobidding algorithms that can manage these competing interests would be an interesting direction for future research.

Overall, this paper provides valuable insights into the design of practical autobidding algorithms and represents an important step forward in understanding the theoretical limits of what is possible in this domain.

Conclusion

This paper presents a novel approach to designing automated bidding algorithms for online advertising platforms that run a mixture of first-price and second-price auctions. The authors develop a low-regret bidding algorithm that can optimize the advertiser's objective while satisfying constraints like ROI and budget.

The key contributions of this work include the theoretical guarantees on the algorithm's performance, the insights on the differences between the full information and bandit settings, and the broad applicability of the results to a wide range of auction types. These findings have important implications for improving the efficiency and effectiveness of online advertising platforms, which play a crucial role in the digital economy.

As online advertising continues to evolve, research like this will help ensure that automated bidding systems can keep pace with the growing complexity of the market, ultimately benefiting both advertisers and consumers.

This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!

Follow @aimodelsfyi on 𝕏 →

Related Papers

👨‍🏫

No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints

Gagan Aggarwal, Giannis Fikioris, Mingfei Zhao

Advertisers increasingly use automated bidding to optimize their ad campaigns on online advertising platforms. Autobidding optimizes an advertiser's objective subject to various constraints, e.g. average ROI and budget constraints. In this paper, we study the problem of designing online autobidding algorithms to optimize value subject to ROI and budget constraints when the platform is running any mixture of first and second price auction. We consider the following stochastic setting: There is an item for sale in each of $T$ rounds. In each round, buyers submit bids and an auction is run to sell the item. We focus on one buyer, possibly with budget and ROI constraints. We assume that the buyer's value and the highest competing bid are drawn i.i.d. from some unknown (joint) distribution in each round. We design a low-regret bidding algorithm that satisfies the buyer's constraints. Our benchmark is the objective value achievable by the best possible Lipschitz function that maps values to bids, which is rich enough to best respond to many different correlation structures between value and highest competing bid. Our main result is an algorithm with full information feedback that guarantees a near-optimal $tilde O(sqrt T)$ regret with respect to the best Lipschitz function. Our result applies to a wide range of auctions, most notably any mixture of first and second price auctions (price is a convex combination of the first and second price). In addition, our result holds for both value-maximizing buyers and quasi-linear utility-maximizing buyers. We also study the bandit setting, where we show an $Omega(T^{2/3})$ lower bound on the regret for first-price auctions, showing a large disparity between the full information and bandit settings. We also design an algorithm with $tilde O(T^{3/4})$ regret, when the value distribution is known and is independent of the highest competing bid.

4/16/2024

📉

Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang

We study a game between autobidding algorithms that compete in an online advertising platform. Each autobidder is tasked with maximizing its advertiser's total value over multiple rounds of a repeated auction, subject to budget and return-on-investment constraints. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret. Our algorithm uses only bandit feedback and can be used with the first- or second-price auction, as well as with any intermediate auction format. Our main result is that when these autobidders play against each other, the resulting expected liquid welfare over all rounds is at least half of the expected optimal liquid welfare achieved by any allocation. This holds whether or not the bidding dynamics converges to an equilibrium.

6/13/2024

Selling Joint Ads: A Regret Minimization Perspective

Gagan Aggarwal, Ashwinkumar Badanidiyuru, Paul Dutting, Federico Fusco

Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand). This problem captures, for example, situations where a merchant and a brand cooperatively bid in an auction to advertise a product, and both benefit from the ad being shown. A mechanism collects bids from the two and decides whether to allocate and which payments the two parties should make. This gives rise to intricate incentive compatibility constraints, e.g., on how to split payments between the two parties. We approach the problem of finding a revenue-maximizing incentive-compatible mechanism from an online learning perspective; this poses significant technical challenges. First, the action space (the class of all possible mechanisms) is huge; second, the function that maps mechanisms to revenue is highly irregular, ruling out standard discretization-based approaches. In the stochastic setting, we design an efficient learning algorithm achieving a regret bound of $O(T^{3/4})$. Our approach is based on an adaptive discretization scheme of the space of mechanisms, as any non-adaptive discretization fails to achieve sublinear regret. In the adversarial setting, we exploit the non-Lipschitzness of the problem to prove a strong negative result, namely that no learning algorithm can achieve more than half of the revenue of the best fixed mechanism in hindsight. We then consider the $sigma$-smooth adversary; we construct an efficient learning algorithm that achieves a regret bound of $O(T^{2/3})$ and builds on a succinct encoding of exponentially many experts. Finally, we prove that no learning algorithm can achieve less than $Omega(sqrt T)$ regret in both the stochastic and the smooth setting, thus narrowing the range where the minimax regret rates for these two problems lie.

9/14/2024

💬

Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions

Rachitesh Kumar, Jon Schneider, Balasubramanian Sivan

Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning, which has seen a recent surge in interest due to the transition of display advertising to first-price auctions. In this work, we propose a novel concave formulation for pure-strategy bidding in first-price auctions, and use it to analyze natural Gradient-Ascent-based algorithms for this problem. Importantly, our analysis goes beyond regret, which was the typical focus of past work, and also accounts for the strategic backdrop of online-advertising markets where bidding algorithms are deployed -- we provide the first guarantees of strategic-robustness and incentive-compatibility for Gradient Ascent. Concretely, we show that our algorithms achieve $O(sqrt{T})$ regret when the highest competing bids are generated adversarially, and show that no online algorithm can do better. We further prove that the regret reduces to $O(log T)$ when the competition is stationary and stochastic, which drastically improves upon the previous best of $O(sqrt{T})$. Moving beyond regret, we show that a strategic seller cannot exploit our algorithms to extract more revenue on average than is possible under the optimal mechanism. Finally, we prove that our algorithm is also incentive compatible -- it is a (nearly) dominant strategy for the buyer to report her values truthfully to the algorithm as a whole. Altogether, these guarantees make our algorithms the first to simultaneously achieve both optimal regret and strategic-robustness.

7/9/2024