Dynamic Budget Throttling in Repeated Second-Price Auctions
- URL: http://arxiv.org/abs/2207.04690v7
- Date: Wed, 13 Dec 2023 04:02:14 GMT
- Title: Dynamic Budget Throttling in Repeated Second-Price Auctions
- Authors: Zhaohua Chen, Chang Wang, Qian Wang, Yuqi Pan, Zhuming Shi, Zheng Cai,
Yukun Ren, Zhihua Zhu, Xiaotie Deng
- Abstract summary: throttling is a popular choice, managing an advertiser's total expenditure by selecting only a subset of auctions to participate in.
This paper provides a theoretical panorama of a single advertiser's dynamic budget throttling process in repeated second-price auctions.
Our results bridge the gaps in theoretical research of throttling in repeated auctions and reveal the ability of this popular budget-smoothing strategy.
- Score: 11.823210231891517
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In today's online advertising markets, a crucial requirement for an
advertiser is to control her total expenditure within a time horizon under some
budget. Among various budget control methods, throttling has emerged as a
popular choice, managing an advertiser's total expenditure by selecting only a
subset of auctions to participate in. This paper provides a theoretical
panorama of a single advertiser's dynamic budget throttling process in repeated
second-price auctions. We first establish a lower bound on the regret and an
upper bound on the asymptotic competitive ratio for any throttling algorithm,
respectively, when the advertiser's values are stochastic and adversarial.
Regarding the algorithmic side, we propose the OGD-CB algorithm, which
guarantees a near-optimal expected regret with stochastic values. On the other
hand, when values are adversarial, we prove that this algorithm also reaches
the upper bound on the asymptotic competitive ratio. We further compare
throttling with pacing, another widely adopted budget control method, in
repeated second-price auctions. In the stochastic case, we demonstrate that
pacing is generally superior to throttling for the advertiser, supporting the
well-known result that pacing is asymptotically optimal in this scenario.
However, in the adversarial case, we give an exciting result indicating that
throttling is also an asymptotically optimal dynamic bidding strategy. Our
results bridge the gaps in theoretical research of throttling in repeated
auctions and comprehensively reveal the ability of this popular
budget-smoothing strategy.
Related papers
- Procurement Auctions via Approximately Optimal Submodular Optimization [53.93943270902349]
We study procurement auctions, where an auctioneer seeks to acquire services from strategic sellers with private costs.
Our goal is to design computationally efficient auctions that maximize the difference between the quality of the acquired services and the total cost of the sellers.
arXiv Detail & Related papers (2024-11-20T18:06:55Z) - Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds.
The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
arXiv Detail & Related papers (2024-05-31T19:26:05Z) - Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM)
We study a model within this problem domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary.
We propose an algorithm namely robust contextual dueling bandit (algo), which is based on uncertainty-weighted maximum likelihood estimation.
arXiv Detail & Related papers (2024-04-16T17:59:55Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning.
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.
arXiv Detail & Related papers (2024-02-12T01:33:33Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed.
SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
arXiv Detail & Related papers (2023-12-13T11:08:25Z) - Multi-Platform Budget Management in Ad Markets with Non-IC Auctions [6.037383467521294]
In online advertising markets, budget-constrained advertisers acquire ad placements through repeated bidding in auctions on various platforms.
We present a strategy for bidding optimally in a set of auctions that may or may not be incentive-compatible under the presence of budget constraints.
Our strategy maximizes the expected total utility across auctions while satisfying the advertiser's budget constraints in expectation.
arXiv Detail & Related papers (2023-06-12T18:21:10Z) - Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
We study a game between autobidding algorithms that compete in an online advertising platform.
We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
arXiv Detail & Related papers (2023-01-30T21:59:30Z) - Fast Rate Learning in Stochastic First Price Bidding [0.0]
First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising.
We show how to achieve significantly lower regret when the opponents' maximal bid distribution is known.
Our algorithms converge much faster than alternatives proposed in the literature for various bid distributions.
arXiv Detail & Related papers (2021-07-05T07:48:52Z) - Efficient Algorithms for Stochastic Repeated Second-price Auctions [0.0]
We develop efficient sequential bidding strategies for repeated auctions.
We provide the first parametric lower bound for this problem.
We propose more explainable strategies which are reminiscent of the Explore Then Commit bandit algorithm.
arXiv Detail & Related papers (2020-11-10T12:45:02Z) - Optimal Bidding Strategy without Exploration in Real-time Bidding [14.035270361462576]
maximizing utility with a budget constraint is the primary goal for advertisers in real-time bidding (RTB) systems.
Previous works ignore the losing auctions to alleviate the difficulty with censored states.
We propose a novel practical framework using the maximum entropy principle to imitate the behavior of the true distribution observed in real-time traffic.
arXiv Detail & Related papers (2020-03-31T20:43:28Z) - Adversarial Attacks on Linear Contextual Bandits [87.08004581867537]
Malicious agents may have incentives to attack the bandit algorithm to induce it to perform a desired behavior.
We show that a malicious agent can force a linear contextual bandit algorithm to pull any desired arm $T - o(T)$ times over a horizon of $T$ steps.
We also investigate the case when a malicious agent is interested in affecting the behavior of the bandit algorithm in a single context.
arXiv Detail & Related papers (2020-02-10T15:04:09Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.