On the Convergence of Learning Algorithms in Bayesian Auction Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929634330804224 |
|---|---|
| author | Bichler, Martin Lunowa, Stephan B. Oberlechner, Matthias Pieroth, Fabian R. Wohlmuth, Barbara |
| author_facet | Bichler, Martin Lunowa, Stephan B. Oberlechner, Matthias Pieroth, Fabian R. Wohlmuth, Barbara |
| contents | Equilibrium problems in Bayesian auction games can be described as systems of differential equations. Depending on the model assumptions, these equations might be such that we do not have a rigorous mathematical solution theory. The lack of analytical or numerical techniques with guaranteed convergence for the equilibrium problem has plagued the field and limited equilibrium analysis to rather simple auction models such as single-object auctions. Recent advances in equilibrium learning led to algorithms that find equilibrium under a wide variety of model assumptions. We analyze first- and second-price auctions where simple learning algorithms converge to an equilibrium. The equilibrium problem in auctions is equivalent to solving an infinite-dimensional variational inequality (VI). Monotonicity and the Minty condition are the central sufficient conditions for learning algorithms to converge to an equilibrium in such VIs. We show that neither monotonicity nor pseudo- or quasi-monotonicity holds for the respective VIs. The second-price auction's equilibrium is a Minty-type solution, but the first-price auction is not. However, the Bayes--Nash equilibrium is the unique solution to the VI within the class of uniformly increasing bid functions, which ensures that gradient-based algorithms attain the equilibrium in case of convergence, as also observed in numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_15398 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Convergence of Learning Algorithms in Bayesian Auction Games Bichler, Martin Lunowa, Stephan B. Oberlechner, Matthias Pieroth, Fabian R. Wohlmuth, Barbara Computer Science and Game Theory Equilibrium problems in Bayesian auction games can be described as systems of differential equations. Depending on the model assumptions, these equations might be such that we do not have a rigorous mathematical solution theory. The lack of analytical or numerical techniques with guaranteed convergence for the equilibrium problem has plagued the field and limited equilibrium analysis to rather simple auction models such as single-object auctions. Recent advances in equilibrium learning led to algorithms that find equilibrium under a wide variety of model assumptions. We analyze first- and second-price auctions where simple learning algorithms converge to an equilibrium. The equilibrium problem in auctions is equivalent to solving an infinite-dimensional variational inequality (VI). Monotonicity and the Minty condition are the central sufficient conditions for learning algorithms to converge to an equilibrium in such VIs. We show that neither monotonicity nor pseudo- or quasi-monotonicity holds for the respective VIs. The second-price auction's equilibrium is a Minty-type solution, but the first-price auction is not. However, the Bayes--Nash equilibrium is the unique solution to the VI within the class of uniformly increasing bid functions, which ensures that gradient-based algorithms attain the equilibrium in case of convergence, as also observed in numerical experiments. |
| title | On the Convergence of Learning Algorithms in Bayesian Auction Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2311.15398 |