The Bounds of Algorithmic Collusion; $Q$-learning, Gradient Learning, and the Folk Theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914365892984832 |
|---|---|
| author | Askenazi-Golan, Galit Cecchelli, Domenico Mergoni Plumb, Edward Possnig, Clemens |
| author_facet | Askenazi-Golan, Galit Cecchelli, Domenico Mergoni Plumb, Edward Possnig, Clemens |
| contents | We explore the behaviour emerging from learning agents repeatedly interacting strategically for a wide range of learning dynamics, including $Q$-learning, projected gradient, replicator and log-barrier dynamics. Going beyond the better understood classes of potential games and zero-sum games, we consider the setting of a general repeated game with finite recall under different forms of monitoring. We obtain a Folk Theorem-style result and characterise the set of payoff vectors that can be obtained by these dynamics, discovering a wide range of possibilities for the emergence of algorithmic collusion. Achieving this requires a novel technical approach, which, to the best of our knowledge, yields the first convergence result for multi-agent $Q$-learning algorithms in repeated games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12725 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Bounds of Algorithmic Collusion; $Q$-learning, Gradient Learning, and the Folk Theorem Askenazi-Golan, Galit Cecchelli, Domenico Mergoni Plumb, Edward Possnig, Clemens Computer Science and Game Theory Theoretical Economics Machine Learning We explore the behaviour emerging from learning agents repeatedly interacting strategically for a wide range of learning dynamics, including $Q$-learning, projected gradient, replicator and log-barrier dynamics. Going beyond the better understood classes of potential games and zero-sum games, we consider the setting of a general repeated game with finite recall under different forms of monitoring. We obtain a Folk Theorem-style result and characterise the set of payoff vectors that can be obtained by these dynamics, discovering a wide range of possibilities for the emergence of algorithmic collusion. Achieving this requires a novel technical approach, which, to the best of our knowledge, yields the first convergence result for multi-agent $Q$-learning algorithms in repeated games. |
| title | The Bounds of Algorithmic Collusion; $Q$-learning, Gradient Learning, and the Folk Theorem |
| topic | Computer Science and Game Theory Theoretical Economics Machine Learning |
| url | https://arxiv.org/abs/2411.12725 |