Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.17463 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915517631037440 |
|---|---|
| author | Xiong, Yi Chen, Ningyuan Gao, Xuefeng |
| author_facet | Xiong, Yi Chen, Ningyuan Gao, Xuefeng |
| contents | When two players are engaged in a repeated game with unknown payoff matrices, they may use single-agent multi-armed bandit algorithms to choose the actions independent of each other. We show that when the players use Thompson sampling, the game dynamics converges to the Nash equilibrium under a mild assumption on the payoff matrices. Therefore, algorithmic collusion doesn't arise in this case despite the fact that the players do not intentionally deploy competitive strategies. To prove the convergence result, we find that the framework developed in stochastic approximation doesn't apply, because of the sporadic and infrequent updates of the inferior actions and the lack of Lipschitz continuity. We develop a novel sample-path-wise approach to show the convergence. However, when the payoff matrices do not satisfy the assumption, the game may converge to collusive outcomes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17463 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Is Thompson Sampling Susceptible to Algorithmic Collusion? Xiong, Yi Chen, Ningyuan Gao, Xuefeng Computer Science and Game Theory Machine Learning When two players are engaged in a repeated game with unknown payoff matrices, they may use single-agent multi-armed bandit algorithms to choose the actions independent of each other. We show that when the players use Thompson sampling, the game dynamics converges to the Nash equilibrium under a mild assumption on the payoff matrices. Therefore, algorithmic collusion doesn't arise in this case despite the fact that the players do not intentionally deploy competitive strategies. To prove the convergence result, we find that the framework developed in stochastic approximation doesn't apply, because of the sporadic and infrequent updates of the inferior actions and the lack of Lipschitz continuity. We develop a novel sample-path-wise approach to show the convergence. However, when the payoff matrices do not satisfy the assumption, the game may converge to collusive outcomes. |
| title | Is Thompson Sampling Susceptible to Algorithmic Collusion? |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2405.17463 |