Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910410589863936 |
|---|---|
| author | Gemp, Ian Marris, Luke Piliouras, Georgios |
| author_facet | Gemp, Ian Marris, Luke Piliouras, Georgios |
| contents | We propose the first loss function for approximate Nash equilibria of normal-form games that is amenable to unbiased Monte Carlo estimation. This construction allows us to deploy standard non-convex stochastic optimization techniques for approximating Nash equilibria, resulting in novel algorithms with provable guarantees. We complement our theoretical analysis with experiments demonstrating that stochastic gradient descent can outperform previous state-of-the-art approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_06689 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization Gemp, Ian Marris, Luke Piliouras, Georgios Computer Science and Game Theory Multiagent Systems We propose the first loss function for approximate Nash equilibria of normal-form games that is amenable to unbiased Monte Carlo estimation. This construction allows us to deploy standard non-convex stochastic optimization techniques for approximating Nash equilibria, resulting in novel algorithms with provable guarantees. We complement our theoretical analysis with experiments demonstrating that stochastic gradient descent can outperform previous state-of-the-art approaches. |
| title | Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization |
| topic | Computer Science and Game Theory Multiagent Systems |
| url | https://arxiv.org/abs/2310.06689 |