Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912544585678848 |
|---|---|
| author | Deng, Xiaotie Hu, Xinyan Lin, Tao Zheng, Weiqiang |
| author_facet | Deng, Xiaotie Hu, Xinyan Lin, Tao Zheng, Weiqiang |
| contents | The convergence properties of learning dynamics in repeated auctions is a timely and important question, with numerous applications in, e.g., online advertising markets. This work focuses on repeated first-price auctions where bidders with fixed values learn to bid using mean-based algorithms -- a large class of online learning algorithms that include popular no-regret algorithms such as Multiplicative Weights Update and Follow the Perturbed Leader. We completely characterize the learning dynamics of mean-based algorithms, under two notions of convergence: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium converges to 1; (2) last-iterate: the mixed strategy profile of bidders converges to a Nash equilibrium. Specifically, the results depend on the number of bidders with the highest value:
- If the number is at least three, the dynamics almost surely converges to a Nash equilibrium of the auction, in both time-average and last-iterate.
- If the number is two, the dynamics almost surely converges to a Nash equilibrium in time-average but not necessarily last-iterate.
- If the number is one, the dynamics may not converge to a Nash equilibrium in time-average or last-iterate.
Our discovery opens up new possibilities in the study of the convergence of learning dynamics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_03906 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions Deng, Xiaotie Hu, Xinyan Lin, Tao Zheng, Weiqiang Computer Science and Game Theory Artificial Intelligence Machine Learning Multiagent Systems Theoretical Economics The convergence properties of learning dynamics in repeated auctions is a timely and important question, with numerous applications in, e.g., online advertising markets. This work focuses on repeated first-price auctions where bidders with fixed values learn to bid using mean-based algorithms -- a large class of online learning algorithms that include popular no-regret algorithms such as Multiplicative Weights Update and Follow the Perturbed Leader. We completely characterize the learning dynamics of mean-based algorithms, under two notions of convergence: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium converges to 1; (2) last-iterate: the mixed strategy profile of bidders converges to a Nash equilibrium. Specifically, the results depend on the number of bidders with the highest value: - If the number is at least three, the dynamics almost surely converges to a Nash equilibrium of the auction, in both time-average and last-iterate. - If the number is two, the dynamics almost surely converges to a Nash equilibrium in time-average but not necessarily last-iterate. - If the number is one, the dynamics may not converge to a Nash equilibrium in time-average or last-iterate. Our discovery opens up new possibilities in the study of the convergence of learning dynamics. |
| title | Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions |
| topic | Computer Science and Game Theory Artificial Intelligence Machine Learning Multiagent Systems Theoretical Economics |
| url | https://arxiv.org/abs/2110.03906 |