From No-Regret to Strategically Robust Learning in Repeated Auctions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911433408643072 |
|---|---|
| author | Zhao, Junyao |
| author_facet | Zhao, Junyao |
| contents | 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 a strong strategic robustness guarantee in this auction setting. At a technical level, our results are established via a simple relation that bridges Myerson's auction theory and standard no-regret learning theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03853 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | From No-Regret to Strategically Robust Learning in Repeated Auctions Zhao, Junyao Computer Science and Game Theory Machine Learning Theoretical Economics 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 a strong strategic robustness guarantee in this auction setting. At a technical level, our results are established via a simple relation that bridges Myerson's auction theory and standard no-regret learning theory. |
| title | From No-Regret to Strategically Robust Learning in Repeated Auctions |
| topic | Computer Science and Game Theory Machine Learning Theoretical Economics |
| url | https://arxiv.org/abs/2601.03853 |