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

• URL: http://arxiv.org/abs/2301.13306v3
• Date: Wed, 12 Jun 2024 02:18:07 GMT
• Title: Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
• Authors: Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins, Mengxiao Zhang,
• Abstract summary: 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.
• Score: 53.62091043347035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  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 bid cooperatively 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.
  arXiv  Detail & Related papers  (2024-09-12T07:59:10Z)
• 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)
• No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraints [0.9694940903078658]
  We study the problem of designing online autobidding algorithms to optimize value subject to ROI and budget constraints. 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.
  arXiv  Detail & Related papers  (2024-04-15T14:31:53Z)
• 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)
• Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
  We study online learning in contextual pay-per-click auctions where at each of the $T$ rounds, the learner receives some context along with a set of ads. The learner's goal is to minimize her regret, defined as the gap between her total revenue and that of an oracle strategy.
  arXiv  Detail & Related papers  (2023-10-08T07:04:22Z)
• Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
  We consider the problem of learning how to bid in repeated multi-unit pay-as-bid auctions. The problem of learning how to bid in pay-as-bid auctions is challenging according to the nature of the action space. We show that the optimal solution to the offline problem can be obtained using a time dynamic programming scheme.
  arXiv  Detail & Related papers  (2023-07-27T20:49:28Z)
• Learning and Collusion in Multi-unit Auctions [17.727436775513368]
  We consider repeated multi-unit auctions with uniform pricing. We analyze the properties of this auction in both the offline and online settings. We show that the $(K+1)$-st price format is susceptible to collusion among the bidders.
  arXiv  Detail & Related papers  (2023-05-27T08:00:49Z)
• No-regret Learning in Repeated First-Price Auctions with Budget Constraints [5.834615090865286]
  We propose an RL-based bidding algorithm against the optimal non-anticipating strategy under stationary competition. Our algorithm obtains $widetilde O(sqrt T)$-regret if the bids are all revealed at the end of each round.
  arXiv  Detail & Related papers  (2022-05-29T04:32:05Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

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.