No-regret Learning in Repeated First-Price Auctions with Budget Constraints

• URL: http://arxiv.org/abs/2205.14572v1
• Date: Sun, 29 May 2022 04:32:05 GMT
• Title: No-regret Learning in Repeated First-Price Auctions with Budget Constraints
• Authors: Rui Ai, Chang Wang, Chenchen Li, Jinshan Zhang, Wenhan Huang, Xiaotie Deng
• Abstract summary: 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.
• Score: 5.834615090865286
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently the online advertising market has exhibited a gradual shift from second-price auctions to first-price auctions. Although there has been a line of works concerning online bidding strategies in first-price auctions, it still remains open how to handle budget constraints in the problem. In the present paper, we initiate the study for a buyer with budgets to learn online bidding strategies in repeated first-price auctions. 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. With the restriction that the buyer only sees the winning bid after each round, our modified algorithm obtains $\widetilde O(T^{\frac{7}{12}})$-regret by techniques developed from survival analysis. Our analysis extends to the more general scenario where the buyer has any bounded instantaneous utility function with regrets of the same order.

Related papers

• 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)
• 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 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)
• 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)
• A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design [158.0041488194202]
  We study reserve price optimization in multi-phase second price auctions. From the seller's perspective, we need to efficiently explore the environment in the presence of potentially nontruthful bidders. Third, the seller's per-step revenue is unknown, nonlinear, and cannot even be directly observed from the environment.
  arXiv  Detail & Related papers  (2022-10-19T03:49:05Z)
• 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)
• ProportionNet: Balancing Fairness and Revenue for Auction Design with Deep Learning [55.76903822619047]
  We study the design of revenue-maximizing auctions with strong incentive guarantees. We extend techniques for approximating auctions using deep learning to address concerns of fairness while maintaining high revenue and strong incentive guarantees.
  arXiv  Detail & Related papers  (2020-10-13T13:54:21Z)
• Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions [40.30925727499806]
  We develop the first minimax optimal online bidding algorithm that achieves an $widetildeO(sqrtT)$ regret. We test our algorithm on three real-world first-price auction datasets obtained from Verizon Media.
  arXiv  Detail & Related papers  (2020-07-09T05:40:39Z)
• Certifying Strategyproof Auction Networks [53.37051312298459]
  We focus on the RegretNet architecture, which can represent auctions with arbitrary numbers of items and participants. We propose ways to explicitly verify strategyproofness under a particular valuation profile using techniques from the neural network verification literature.
  arXiv  Detail & Related papers  (2020-06-15T20:22:48Z)

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.