Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909209550913536 |
|---|---|
| author | Zhang, Brian Hu Farina, Gabriele Anagnostides, Ioannis Cacciamani, Federico McAleer, Stephen Marcus Haupt, Andreas Alexander Celli, Andrea Gatti, Nicola Conitzer, Vincent Sandholm, Tuomas |
| author_facet | Zhang, Brian Hu Farina, Gabriele Anagnostides, Ioannis Cacciamani, Federico McAleer, Stephen Marcus Haupt, Andreas Alexander Celli, Andrea Gatti, Nicola Conitzer, Vincent Sandholm, Tuomas |
| contents | We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensive-form zero-sum game. This reformulation allows to apply techniques for learning in zero-sum games, yielding the first learning dynamics that converge to optimal equilibria, not only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_05216 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games Zhang, Brian Hu Farina, Gabriele Anagnostides, Ioannis Cacciamani, Federico McAleer, Stephen Marcus Haupt, Andreas Alexander Celli, Andrea Gatti, Nicola Conitzer, Vincent Sandholm, Tuomas Computer Science and Game Theory We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, information design, and solution concepts such as correlated, communication, and certification equilibria. We observe that optimal equilibria are minimax equilibrium strategies of a player in an extensive-form zero-sum game. This reformulation allows to apply techniques for learning in zero-sum games, yielding the first learning dynamics that converge to optimal equilibria, not only in empirical averages, but also in iterates. We demonstrate the practical scalability and flexibility of our approach by attaining state-of-the-art performance in benchmark tabular games, and by computing an optimal mechanism for a sequential auction design problem using deep reinforcement learning. |
| title | Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2306.05216 |