Randomized Truthful Auctions with Learning Agents

• URL: http://arxiv.org/abs/2411.09517v1
• Date: Thu, 14 Nov 2024 15:28:40 GMT
• Title: Randomized Truthful Auctions with Learning Agents
• Authors: Gagan Aggarwal, Anupam Gupta, Andres Perlroth, Grigoris Velegkas,
• Abstract summary: We study a setting where agents use no-regret learning to participate in repeated auctions. We show that when bidders participate in second-price auctions using no-regret bidding algorithms, the runner-up bidder may not converge to bidding truthfully. We define a notion of em auctioneer regret comparing the revenue generated to the revenue of a second price auction with bids.
• Score: 10.39657928150242
• License:
• Abstract: We study a setting where agents use no-regret learning algorithms to participate in repeated auctions. \citet{kolumbus2022auctions} showed, rather surprisingly, that when bidders participate in second-price auctions using no-regret bidding algorithms, no matter how large the number of interactions $T$ is, the runner-up bidder may not converge to bidding truthfully. Our first result shows that this holds for \emph{general deterministic} truthful auctions. We also show that the ratio of the learning rates of the bidders can \emph{qualitatively} affect the convergence of the bidders. Next, we consider the problem of revenue maximization in this environment. In the setting with fully rational bidders, \citet{myerson1981optimal} showed that revenue can be maximized by using a second-price auction with reserves.We show that, in stark contrast, in our setting with learning bidders, \emph{randomized} auctions can have strictly better revenue guarantees than second-price auctions with reserves, when $T$ is large enough. Finally, we study revenue maximization in the non-asymptotic regime. We define a notion of {\em auctioneer regret} comparing the revenue generated to the revenue of a second price auction with truthful bids. When the auctioneer has to use the same auction throughout the interaction, we show an (almost) tight regret bound of $\smash{\widetilde \Theta(T^{3/4})}.$ If the auctioneer can change auctions during the interaction, but in a way that is oblivious to the bids, we show an (almost) tight bound of $\smash{\widetilde \Theta(\sqrt{T})}.$

Related papers

• A pragmatic policy learning approach to account for users' fatigue in repeated auctions [47.75983850930121]
  ML models can predict how previously won auctions the current opportunity value. A policy that uses this prediction tomaximize the expected payoff of the current auction could be dubbedimpatient. We provide two empirical arguments for the importance of this cost ofimpatience.
  arXiv  Detail & Related papers  (2024-07-15T07:53:29Z)
• Learning in Repeated Multi-Unit Pay-As-Bid Auctions [3.6294895527930504]
  We study the problem of bidding strategies in pay-as-bid (PAB) auctions from the perspective of single bidder. We show that a utility trick enables a time algorithm to solve the offline problem where competing bids are known in advance. We also present additional findings on the characterization of PAB equilibria.
  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)
• 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)
• Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions [42.002983450368134]
  We study the question of how to bid in first-price auctions. Unlike in second-price auctions, bidding one's private value truthfully is no longer optimal. We consider two types of hints: one where a single point-prediction is available, and the other where a hint interval is available.
  arXiv  Detail & Related papers  (2022-11-05T19:20:53Z)
• 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)
• Artificial Intelligence and Auction Design [0.0]
  We find that first-price auctions with no additional feedback lead to tacit-collusive outcomes. We show that the difference is driven by the incentive in first-price auctions to outbid opponents by just one bid increment. We also show that providing information about lowest bid to win, as introduced by Google at the time of switch to first-price auctions, increases competitiveness of auctions.
  arXiv  Detail & Related papers  (2022-02-12T00:54:40Z)
• 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)
• 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)
• Optimal No-regret Learning in Repeated First-price Auctions [38.908235632001116]
  We study online learning in repeated first-price auctions. We develop the first learning algorithm that achieves a near-optimal $widetildeO(sqrtT)$ regret bound.
  arXiv  Detail & Related papers  (2020-03-22T03:32: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.