Is Online Linear Optimization Sufficient for Strategic Robustness?

arXiv:2602.12253 · cs.GT, cs.LG · Submitted 2026-02-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Is Online Linear Optimization Sufficient for Strategic Robustness?".

Jane: Here's the gist of the paper. Is online linear optimization sufficient for strategic robustness?

Tom: This paper explores whether simple online linear optimization (OLO) algorithms are enough to guarantee strategic robustness in repeated Bayesian first-price auctions, showing that sublinear linearized regret is sufficient for this property in both known and unknown value distribution settings.

Jane: Problem Context The paper considers bidding in repeated Bayesian first-price auctions where the buyer has an absolutely continuous value distribution F over

0, 1: and chooses a bid from a discrete, equally spaced grid.

Tom: A key property sought is strategic robustness, meaning the seller cannot extract average revenue higher than the optimal single-shot mechanism.

Paper summary: Tom: So, to follow up on that, the paper argues that sublinear linearized regret implies strategic robustness through simple black-box reductions for any online linear optimization algorithm. They show this holds even when you don't know the exact value distribution beforehand.

Jane: That means if you find an online linear optimization algorithm that minimizes sublinear linearized regret against a specific baseline, it automatically becomes a strategically robust no-regret bidding algorithm regardless of the underlying value distribution assumptions.

Lu: They build these reductions to show that any online linear optimization algorithm can be converted into one with both desirable properties, which is what they call a no-regret bidding algorithm that is also strategically robust.

Meng: I wonder how clean those black-box reductions are in practice? When you're shipping models, you want mechanisms that are transparent and easy to verify under real traffic conditions.

Lalam: The paper shows that applying this reduction using the Multiplicative Weights Update algorithm gives an improvement over other methods, yielding a regret bound of O(sqrt(T log K)) and strategic robustness for both known and unknown settings.

Conclusion: Tom: So, wrapping up the paper "Is Online Linear Optimization Sufficient for Strategic Robustness?", the main point is that sublinear linearized regret is enough to guarantee strategic robustness in first-price auctions, whether you know the value distribution or not.

Jane: It suggests that we don't need much more complex machinery than what simple online linear optimization offers if we want a bidding algorithm that resists manipulation.

Lu: The implication here is that for certain classes of problems, this simpler approach provides a powerful path to achieving both no-regret and strategic robustness properties efficiently.

Meng: It also points out the limitation they found, which is that sublinear regret alone isn't enough; you can have negative regret without having strategic robustness.

Lalam: So, in short, this paper confirms that OLO is sufficient for strategically robust no-regret bidding and provides stronger guarantees by leveraging linearized regret over standard regret measures.

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

Yale University · University of Southern California · University of Virginia

cs.GT, cs.LG

Submitted: 2026-02-12

Updated: 2026-11-10

Comments: Accepted to ACM EC 2026. This version includes a new $O(1)$ strategic robustness result

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 92/100

The gist: Is online linear optimization sufficient for strategic robustness? This paper explores whether simple online linear optimization (OLO) algorithms are enough to guarantee strategic robustness in…

Key concepts

Strategic Robustness
This means the seller cannot extract average revenue higher than what they could achieve with the best single-shot mechanism. It ensures the auction design is fair and prevents bidders from exploiting the auction structure to gain unfair advantages over time.
Sublinear Linearized Regret
This is a weaker measure of performance than standard regret, focusing on minimizing error in a linearized sense. The paper proves that minimizing this specific type of regret is sufficient to guarantee strategic robustness, offering a stronger condition for the algorithm's success.
Online Linear Optimization (OLO)
This refers to simple algorithms used in online learning where decisions are made sequentially based on current information and an optimization objective. The paper tests if these basic OLO methods can be adapted to guarantee strategic robustness in auction settings.

Terminology

Summary

Is online linear optimization sufficient for strategic robustness? p. 0 This paper explores whether simple online linear optimization (OLO) algorithms are enough to guarantee strategic robustness in repeated Bayesian first-price auctions, showing that sublinear linearized regret is sufficient for this property in both known and unknown value distribution settings. p. 0

Problem Context

The paper considers bidding in repeated Bayesian first-price auctions where the buyer has an absolutely continuous value distribution F over [0, 1] and chooses a bid from a discrete, equally spaced grid. A key property sought is strategic robustness, meaning the seller cannot extract average revenue higher than the optimal single-shot mechanism. p. 2 The goal is to achieve sublinear regret and strategic robustness simultaneously. p. 2

Key Findings on Sufficiency

The main result demonstrates that sublinear linearized regret implies strategic robustness, providing a black-box reduction that converts any OLO algorithm into a strategically robust no-regret bidding algorithm. Specifically, if an algorithm minimizes linearized regret against the all-zero strategy, it is also strategically robust. p. 9 This holds in both the known and unknown value distribution settings. p. 0

Performance Improvements

The authors show that applying this reduction with the Multiplicative Weights Update (MWU) algorithm yields a bidding algorithm with an improved bound of O(√T log K) regret and strategic robustness, which is better than the O(√TK) bound achieved by online gradient ascent [KSS24]. This improvement is significant when the number of bids K is determined by discretizing a continuous bid space. p. 4

Handling Unknown Distributions

For the unknown value distribution setting, the paper addresses limitations in previous work by proposing a Dominated Continuous Empirical Distribution Fbt. This technique allows for a reduction that achieves high-probability bounds of O(pT(log K + log(T /δ))) for both regret and strategic robustness, successfully removing the need for the bounded density assumption made in prior literature. p. 0

Limitations of Weaker Regret

The paper proves that sublinear regret alone is insufficient for strategic robustness by constructing an example where an algorithm has negative regret but fails to be strategically robust. This demonstrates that minimizing the weaker notion of regret is not enough to guarantee strategic robustness. p. 9

Conclusion

The study confirms that OLO is sufficient for strategically robust no-regret bidding in first-price auctions, and it provides stronger guarantees than previously known methods by leveraging linearized regret. The results also show the unexpected power of linearized regret over standard regret measures. p. 6

A Useful Lemmas

Lemma 6 (1D Wasserstein identity) states that Z 1 0 F−(u) − G−(u) · du = Z ∞ −∞ F(v) − G(v)dv. Lemma 7 (Dvoretzky–Kiefer–Wolfowitz inequality [DKW56]) states that with probability at least 1 − δ that sup v∈R F(v) − Fn(v) ≤ r log(2/δ) / 2n. p. 5

B Sublinear Regret does not Imply Strategic Robustness

The authors present an example where a sequence of bidding strategies has negative regret but is not strategically robust, showing that this is possible.

C Proof of Lemma 2

The proof for Lemma 2 relies on the one-to-one linear transformation between P and Q and the utility definition.

D Proof of Corollary 1

The proof for Corollary 1 combines the gradient properties with Theorem 2 to show that sublinear linearized regret implies strategic robustness.

E Proof of Lemma 4

The proof for Lemma 4 uses the identity derived from [KSS24] and bounds the difference in utility and revenue by 4F − F′∞.

Appendix B Sublinear Regret does not Imply Strategic Robustness

The authors present an instance and proof of Theorem 3 demonstrating that negative regret does not imply strategic robustness.

Appendix D Proof of Corollary 1

The proof for Corollary 1 is completed by invoking Theorem 2.

Appendix E Proof of Lemma 4

The proof for Lemma 4 uses the standard application of the 1-dimensional Wasserstein identity.

In this paper, we show that sublinear linearized regret suffices for strategic robustness in first-price auctions, by simple black-box reductions that convert any OLO algorithm into a strategically robust no-regret bidding algorithm in both the known and unknown value settings. The results also show the unexpected power of linearized regret over regret. p. 6

Acknowledgement

YC is supported by the NSF award CCF-2342642, WZ is supported by the NSF award CCF-2342642 and a research fellowship from the Center for Algorithms, Data, and Market Design at Yale (CADMY), HL is supported by NSF award IIS-1943607.

References

[ABBBD+24] Gagan Aggarwal, Ashwinkumar Badanidiyuru, Santiago R Balseiro, Kshipra Bhawalkar, Yuan Deng, Zhe Feng, Gagan Goel, Christopher Liaw, Haihao Lu, Mohammad Mahdian, et al. “Auto-bidding and auctions in online advertising: A survey”. p. 2 In: ACM SIGecom Exchanges 22.1 (2024), pp. 159–183.

[ACMMS+25] Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. p. 3 “Swap Regret and Correlated Equilibria Beyond Normal-Form Games”. p. 5 In: Proceedings of the 26th ACM Conference on Economics and Computation. p. 2 2025, pp. 130–157.

[ACS24] Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. p. 6 “Pareto-optimal algorithms for learning in games”. p. 6 In: Proceedings of the 25th ACM Conference on Economics and Computation. p. 2 p. 2 p. 2 2024, pp. 490–510.

[AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale. p. 2 “The multiplicative weights update method: a meta-algorithm and applications”. p. 2 In: Theory of computing 8. p. 21 (2012), pp. 121–164.

[AJT25] Anastasios N Angelopoulos, Michael I Jordan, and Ryan J Tibshirani. p. 6 “Gradient equilibrium in online learning: Theory and applications”. p. 8 In: arXiv preprint arXiv:2501. p. 008330 (2025).

[BCD20] Johannes Brustle, Yang Cai, and Constantinos Daskalakis. p. 0 “Multi-item mechanisms without item-independence: Learnability via robustness”. p. 6 In: Proceedings of the 21st ACM Conference on Economics and Computation. p. 2 2020, pp. 715–761.

[BFG23] Ashwinkumar Badanidiyuru, Zhe Feng, and Guru Guruganesh. p. 2 “Learning to Bid in Contextual First Price Auctions”. p. 2 In: Proceedings of the ACM Web Conference 2023. 2023, pp. 3489–3497.

[BGMMS23] Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian, Vahab Mirrokni, and Jon Schneider. p. 2 “Contextual Bandits with Cross-Learning”. p. 2 In: Mathematics of Operations Research 48. p. 23 (2023), pp. 1607–1629.

[BMSW18] Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. p. 2 “Selling to a no-regret buyer”. p. 2 In: Proceedings of the 2018 ACM Conference on Economics and Computation. p. 2 2018, pp. 523–538.

[CCCFL24] Nicolo Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. p. 2 “The role of transparency in repeated first-price auctions with unknown valuations”. p. 2 In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. p. 2 2024, pp. 225–236.

[CWWZ23] Linda Cai, S Matthew Weinberg, Evan Wildenhain, and Shirley Zhang. p. 6 “Selling to multiple no-regret buyers”. p. 6 In: International Conference on Web and Internet Economics. p. 2 Springer. 2023, pp. 113–129.

[DKW56] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. “Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator”. p. 4 In: The Annals of Mathematical Statistics (1956), pp. 642–669.

[DSS19] Yuan Deng, Jon Schneider, and Balasubramanian Sivan. p. 5 “Strategizing against no-regret learners”. p. 5 In: Advances in neural information processing systems 32 (2019). p. 6

[FS97] Yoav Freund and Robert E Schapire. p. 2 “A decision-theoretic generalization of on-line learning and an application to boosting”. p. 2 In: Journal of computer and system sciences 55. p. 21 (1997), pp. 119–139.

[GHZ19] Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. p. 5 “Settling the sample complexity of singleparameter revenue maximization”. p. 7 In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. p. 2 2019, pp. 662–673.

[GKSTV+24] Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talgam-Cohen, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Joshua Ruizhi Wang, and S. Matthew Weinberg. p. 2 “Contracting with a Learning Agent”. p. 6 In: The Thirty-eighth Annual Conference on Neural Information Processing Systems. p. 6 2024.

[Haz+16] Elad Hazan et al. p. 2 “Introduction to online convex optimization”. p. 7 In: Foundations and Trends® in Optimization 2. p. 03-4 (2016), pp. 157–325.

[HWZ25] Yanjun Han, Tsachy Weissman, and Zhengyuan Zhou. p. 2 “Optimal no-regret learning in repeated first-price auctions”. p. 0 In: Operations Research 73. p. 21 (2025), pp. 209–238.

[HZFOW20] Yanjun Han, Zhengyuan Zhou, Aaron Flores, Erik Ordentlich, and Tsachy Weissman. p. 2 “Learning to bid optimally and efficiently in adversarial first-price auctions”. p. 2 In: arXiv preprint arXiv:2007. p. 004568 (2020).

[JP24] Atulya Jain and Vianney Perchet. p. 6 “Calibrated forecasting and persuasion”. In: arXiv preprint arXiv:2406. p. 015680 (2024).

[KSS24] Rachitesh Kumar, Jon Schneider, and Balasubramanian Sivan. p. 3 “Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions”. p. 2 In: Proceedings of the 25th ACM Conference on Economics and Computation. 2024, pp. 893–893.

[LC25] Tao Lin and Yiling Chen. p. 6 “Generalized Principal-Agent Problem with a Learning Agent”. p. 6 In: The Thirteenth International Conference on Learning Representations. p. 1 2025.

[LDO26] Tuo Liu, Edgar Dobriban, and Francesco Orabona. p. 6 Online Conformal Prediction via Universal Portfolio Algorithms. 2026. arXiv: 2602. p. 003168 [stat.ML].

[LW94] Nick Littlestone and Manfred K Warmuth. p. 2 “The weighted majority algorithm”. p. 0 In: Information and computation 108. p. 32 (1994), pp. 212–261.

[MMSS22] Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. p. 3 “Strategizing against learners in bayesian games”. p. 5 In: Conference on Learning Theory. p. 2 PMLR. 2022, pp. 5221–5252.

[Mye81] Roger B Myerson. p. 7 “Optimal auction design”. p. 2 In: Mathematics of Operations Research 6. p. 21 (1981), pp. 58–73.

[Ora19] Francesco Orabona. p. 2 “A modern introduction to online learning”. p. 2 In: arXiv preprint arXiv:1912. p. 013213 (2019).

[RKR25] Ramya Ramalingam, Shayan Kiyani, and Aaron Roth. p. 6 “The Relationship Between NoRegret Learning and Online Conformal Prediction”. p. 6 In: Forty-second International Conference on Machine Learning. p. 2 2025.

[RS16] Tim Roughgarden and Okke Schrijvers. p. 5 “Ironing in the dark”. In: Proceedings of the 2016 ACM Conference on Economics and Computation. p. 2 2016, pp. 1–18.

[RZ24] Aviad Rubinstein and Junyao Zhao. p. 6 “Strategizing against no-regret learners in first-price auctions”. p. 5 In: Proceedings of the 25th ACM Conference on Economics and Computation. 2024, pp. 894–921.

[Won21] Matt Wong. p. 2 Moving adsense to a first-price auction. p. 2 https: / / blog. google / products/adsense/our-move-to-a-first-price-auction/. p. 2 Accessed: 2026-01-22. p. 0 2021.

[WYDK23] Qian Wang, Zongjun Yang, Xiaotie Deng, and Yuqing Kong. p. 2 “Learning to bid in repeated first-price auctions with budgets”. p. 2 In: International Conference on Machine Learning. p. 1 PMLR. 2023, pp. 36494–36513.

[YZ24] Kunhe Yang and Hanrui Zhang. p. 6 “Computational aspects of bayesian persuasion under approximate best response”. p. 3 In: Advances in Neural Information Processing Systems 37 (2024), pp. p. 6 134430–134458.

[Zha26] Junyao Zhao. p. 6 “From No-Regret to Strategically Robust Learning in Repeated Auctions”. p. 2 In: arXiv preprint arXiv:2601. p. 003853 (2026). p. 0

[ZHZFW22] Wei Zhang, Yanjun Han, Zhengyuan Zhou, Aaron Flores, and Tsachy Weissman. p. 2 “Leveraging the hints: Adaptive bidding in repeated first-price auctions”. p. 0 In: Advances in Neural Information Processing Systems 35 (2022), pp. p. 6 21329–21341.

[Zin03] Martin Zinkevich. p. 3 “Online convex programming and generalized infinitesimal gradient ascent”. p. 0 In: Proceedings of the 20th international conference on machine learning (ICML). p. 1 2003.

Lemma 6 (1D Wasserstein identity) states that Let F, G: R → [0, 1] be two CDFs and F −, G− be their generalized inverses. Then Z 1 0 F−(u) − G−(u) · du = Z ∞ −∞ F(v) − G(v)dv.

Lemma 7 (Dvoretzky–Kiefer–Wolfowitz inequality [DKW56]) states that Let F be a CDF and Fn be the empirical CDF with n samples. p. 5 It holds with probability at least 1 − δ that sup v∈R F(v) − Fn(v) ≤ r log(2/δ) / 2n. p. 0

The authors use the following example presented in [KSS24] to show that sublinear regret does not imply strategic robustness.

Example 1

This example uses a smoothly truncated equi-revenue distribution and shows that a sequence of bidding strategies with negative regret is not strategically robust.

Proof of Theorem 3

The proof for Theorem 3 uses the instance in Example 1 to show that an algorithm can have negative regret but fail to be strategically robust.

The proof for Lemma 2 follows directly from Theorem 1 and the one-to-one linear transformation between P and Q.

The proof for Corollary 1 is completed by invoking Theorem 2.

The proof for Lemma 4 uses the standard application of the 1-dimensional Wasserstein identity.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Optimization of Bidding Algorithms for Strategic Robustness: The improved system can utilize any online linear optimization (OLO) algorithm to generate a bidding algorithm that is both no-regret and strategically robust, effectively broadening the class of robust bidding algorithms beyond those achievable by no-swap-regret algorithms.

  2. Enhanced Regret and Robustness Guarantees in Known Value Settings: The system can achieve O(sqrt(T log K)) regret and strategic robustness when using simple black-box reductions that convert any OLO algorithm into a strategically robust no-regret bidding algorithm, which is an exponential improvement over the O(sqrt(TK)) bound of online gradient ascent.

  3. Robustness in Unknown Value Distribution Settings: The system can handle scenarios where the value distribution is unknown by employing a meta-algorithm (Algorithm 2) that estimates the distribution from samples and runs an OLO algorithm, achieving high-probability bounds of O(pT log(T/delta)) for both regret and strategic robustness, overcoming limitations of previous methods.

  4. Improved Computational Efficiency in Discretized Bidding Spaces: When the bidding space is discretized, the system can maintain a O(sqrt(T log T)) regret guarantee by choosing K=T in the reduction, which is superior to the suboptimal O(T(2/3)) regret achieved by online gradient ascent under optimal tuning of K.

Sources

Related papers