From No-Regret to Strategically Robust Learning in Repeated Auctions

• URL: http://arxiv.org/abs/2601.03853v1
• Date: Wed, 07 Jan 2026 12:09:13 GMT
• Title: From No-Regret to Strategically Robust Learning in Repeated Auctions
• Authors: Junyao Zhao,
• Abstract summary: We show that any no-regret learning algorithm, when fed gradient feedback with respect to the quantile representation, is strategically robust.<n>In particular, the multiplicative weights update (MWU) algorithm simultaneously achieves the optimal regret guarantee and the best-known strategic robustness guarantee.
• Score: 0.5076419064097732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In Bayesian single-item auctions, a monotone bidding strategy--one that prescribes a higher bid for a higher value type--can be equivalently represented as a partition of the quantile space into consecutive intervals corresponding to increasing bids. Kumar et al. (2024) prove that agile online gradient descent (OGD), when used to update a monotone bidding strategy through its quantile representation, is strategically robust in repeated first-price auctions: when all bidders employ agile OGD in this way, the auctioneer's average revenue per round is at most the revenue of Myerson's optimal auction, regardless of how she adjusts the reserve price over time. In this work, we show that this strategic robustness guarantee is not unique to agile OGD or to the first-price auction: any no-regret learning algorithm, when fed gradient feedback with respect to the quantile representation, is strategically robust, even if the auction format changes every round, provided the format satisfies allocation monotonicity and voluntary participation. In particular, the multiplicative weights update (MWU) algorithm simultaneously achieves the optimal regret guarantee and the best-known strategic robustness guarantee. At a technical level, our results are established via a simple relation that bridges Myerson's auction theory and standard no-regret learning theory. This showcases the potential of translating standard regret guarantees into strategic robustness guarantees for specific games, without explicitly minimizing any form of swap regret.

Related papers

• Is Online Linear Optimization Sufficient for Strategic Robustness? [54.49053278073321]
  No-swap-regret algorithms achieve both desirable properties, but are suboptimal in terms of statistical and computational efficiency.<n>Online gradient ascent is the only algorithm that achieves $O(sqrtTK)$ regret and strategic robustness.<n>We construct simple black-box reductions that convert any OLO algorithm into a strategically robust no-regret bidding algorithm.
  arXiv  Detail & Related papers  (2026-02-12T18:41:55Z)
• Learning to Bid in Non-Stationary Repeated First-Price Auctions [27.743710782882136]
  First-price auctions have gained significant traction in digital advertising markets.<n> determining an optimal bidding strategy in first-price auctions is more complex.<n>We provide a minimax-optimal characterization of the dynamic regret for the class of sequences of opponents' highest bids.
  arXiv  Detail & Related papers  (2025-01-23T03:53:27Z)
• Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions [6.309531239485479]
  We study the bidding problem in repeated uniform price multi-unit auctions from the perspective of a value-maximizing buyer.<n>We introduce the notion of safe bidding strategies as those that satisfy the RoI constraints irrespective of competing bids.<n>We show that these strategies satisfy a mild no-overbidding condition, depend only on the valuation curve of the bidder, and the bidder can focus on a finite subset without loss of generality.
  arXiv  Detail & Related papers  (2024-06-06T01:29:47Z)
• Statistically Truthful Auctions via Acceptance Rule [23.38395470540186]
  Strategy-proofness is crucial as it ensures that buyers are incentivized to bid their true valuations.<n>We propose a formulation of statistical strategy-proofness for auction mechanisms.<n>Our method represents a practical middle-ground between enforcing truthfulness -- zero-regret -- at the cost of significant revenue loss.
  arXiv  Detail & Related papers  (2024-05-20T13:39:58Z)
• Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits with Strategic Agents [52.75161794035767]
  We introduce a class of bandit algorithms that meet the two objectives of performance incentivization and robustness simultaneously.<n>We show that settings where the principal has no information about the arms' performance characteristics can be handled by combining ideas from second price auctions with our algorithms.
  arXiv  Detail & Related papers  (2023-12-13T06:54: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.<n>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)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• Dynamic Budget Throttling in Repeated Second-Price Auctions [11.823210231891517]
  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.
  arXiv  Detail & Related papers  (2022-07-11T08:12:02Z)
• 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)
• Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
  Lipschitz bandits is a prominent version of multi-armed bandits that studies large, structured action spaces.<n>A central theme here is the adaptive discretization of the action space, which gradually zooms in'' on the more promising regions.<n>We provide the first algorithm for adaptive discretization in the adversarial version, and derive instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-06-22T16:06:25Z)
• 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.