Multilinear formulations for computing Nash equilibrium of multi-player matrix games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911812510810112 |
|---|---|
| author | Fischer, Miriam Gupte, Akshay |
| author_facet | Fischer, Miriam Gupte, Akshay |
| contents | We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_03406 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Multilinear formulations for computing Nash equilibrium of multi-player matrix games Fischer, Miriam Gupte, Akshay Optimization and Control Computer Science and Game Theory 90C26, 91A06, 91A10 We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms. |
| title | Multilinear formulations for computing Nash equilibrium of multi-player matrix games |
| topic | Optimization and Control Computer Science and Game Theory 90C26, 91A06, 91A10 |
| url | https://arxiv.org/abs/2208.03406 |