cs.GTFeb 12, 2026

Is Online Linear Optimization Sufficient for Strategic Robustness?

Authors: Yang Cai, Haipeng Luo, Chen-Yu Wei, Weiqiang Zheng

Organizations: Yale University. · University of Southern California. · University of Virginia.

Abstract

We consider bidding in repeated Bayesian first-price auctions. Bidding algorithms that achieve optimal regret have been extensively studied, but their strategic robustness to the seller's manipulation remains relatively underexplored. Bidding algorithms based on no-swap-regret algorithms achieve both desirable properties, but are suboptimal in terms of statistical and computational efficiency. In contrast, online gradient ascent is the only algorithm that achieves O(TK)O(\sqrt{TK}) regret and strategic robustness [KSS24], where TT denotes the number of auctions and KK the number of bids. In this paper, we explore whether simple online linear optimization (OLO) algorithms suffice for bidding algorithms with both desirable properties. Our main result shows that sublinear linearized regret is sufficient for strategic robustness. Specifically, we construct simple black-box reductions that convert any OLO algorithm into a strategically robust no-regret bidding algorithm, in both known and unknown value distribution settings. For the known value distribution case, our reduction yields a bidding algorithm that achieves O(Tlog⁡K)O(\sqrt{T \log K}) regret and strategic robustness (with exponential improvement on the KK-dependence compared to [KSS24]). Moreover, we can further exploit the single-strategy benchmark and construct a bidding algorithm with O(T(log⁡K+log⁡T))O(\sqrt{T(\log K+\log T)}) regret and O(1)O(1) strategic robustness. For the unknown value distribution case, our reduction gives a bidding algorithm with high-probability O(T(log⁡K+log⁡(T/δ))O(\sqrt{T (\log K+\log(T/δ)}) regret and strategic robustness, while removing the bounded density assumption made in [KSS24].

Figures & tables

Explore similar work

Oct 27, 2026

Impossibility of No-Regret in Multi-Agent Bidding

We consider TT repeated second-price auctions across nn pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.
Jun 27, 2026

A3M: Adaptive, Adversarial and Multi-Objective Learning for Strategic Bidding in Repeated Auctions

Learning to bid in repeated multi-unit auctions with bandit feedback poses a fundamental challenge. Existing methods often rely on rigid explore-then-exploit schedules, assume stationary adversaries, and optimize solely for bidder utility, thereby limiting adaptability and strategic robustness. To address these limitations, we introduce the A3M framework, which integrates adaptive deep reinforcement learning (DRL), explicit adversarial reasoning, and principled multi-objective reward design for online auction strategy optimization. A3M employs an actor-critic DRL backbone to dynamically balance exploration and exploitation, an opponent model for fictitious play against non-stationary adversaries, and a composite reward function to jointly maximize utility, auctioneer revenue, and fairness. We provide the first comprehensive empirical evaluation of this integrated approach against established baselines in both discriminatory and uniform price auctions. Results show that A3M reduces final regret by 30--40% in standard settings, maintains robust performance against adversarial strategy shifts, scales favorably with the number of units KK, and enables tunable multi-objective trade-offs. An extensive ablation study confirms the necessity of each core component. Our work establishes A3M as a powerful and flexible framework for learning in complex auction environments.
May 21, 2026

Do Not Trust The Auctioneer: Learning to Bid in Feedback-Manipulated Auctions

Shilling is the use of artificial bids to make competition appear stronger and push prices upward. We study repeated first-price auctions in which shilling affects feedback but not allocation: the learner wins or loses against the real competing bid, but after a loss observes the maximum of the real bid and an independent shill bid. Thus the manipulation changes what the learner observes and hence how it learns to bid, without changing the outcome of the current auction. We analyze regret with respect to the best bid benchmark, assuming that the shill-bid distribution is known. Even then, shilling can mask the real bid, while useful side information appears only through intermittent low-shill events. Our algorithm combines a robust interval-elimination branch, which ignores the shilled report and achieves the dynamic-pricing rate O~(T2/3)\tilde{\mathcal{O}}(T^{2/3}), with an optimistic branch that debiases losing-side reports and exploits the resulting suffix information when it is reliable and achieves the first-price auctions rate O~(T)\tilde{\mathcal{O}}(\sqrt{T}). A validation and racing procedure lets the algorithm use these optimistic updates without knowing the right scale or feedback geometry in advance. We complement the upper bounds with a matching lower bound, up to logarithmic factors, in the single-active-region case. Overall, the results show that even feedback-only shilling can sharply alter the statistical difficulty of repeated bidding.