A Stable-Set Bound and Maximal Numbers of Nash Equilibria in Bimatrix Games
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_ | 1866911281302208512 |
|---|---|
| author | Ickstadt, Constantin Theobald, Thorsten von Stengel, Bernhard |
| author_facet | Ickstadt, Constantin Theobald, Thorsten von Stengel, Bernhard |
| contents | Quint and Shubik (1997) conjectured that a non-degenerate n-by-n game has at most 2^n-1 Nash equilibria in mixed strategies. The conjecture is true for n at most 4 but false for n=6 or larger. We answer it positively for the remaining case n=5, which had been open since 1999. The problem can be translated to a combinatorial question about the vertices of a pair of simple n-polytopes with 2n facets. We introduce a novel obstruction based on the index of an equilibrium, which states that equilibrium vertices belong to two equal-sized disjoint stable sets of the graph of the polytope. This bound is verified directly using the known classification of the 159,375 combinatorial types of dual neighborly polytopes in dimension 5 with 10 facets. Non-neighborly polytopes are analyzed with additional combinatorial techniques where the bound is used for their disjoint facets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12385 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Stable-Set Bound and Maximal Numbers of Nash Equilibria in Bimatrix Games Ickstadt, Constantin Theobald, Thorsten von Stengel, Bernhard Computer Science and Game Theory Combinatorics 91A05 G.2 Quint and Shubik (1997) conjectured that a non-degenerate n-by-n game has at most 2^n-1 Nash equilibria in mixed strategies. The conjecture is true for n at most 4 but false for n=6 or larger. We answer it positively for the remaining case n=5, which had been open since 1999. The problem can be translated to a combinatorial question about the vertices of a pair of simple n-polytopes with 2n facets. We introduce a novel obstruction based on the index of an equilibrium, which states that equilibrium vertices belong to two equal-sized disjoint stable sets of the graph of the polytope. This bound is verified directly using the known classification of the 159,375 combinatorial types of dual neighborly polytopes in dimension 5 with 10 facets. Non-neighborly polytopes are analyzed with additional combinatorial techniques where the bound is used for their disjoint facets. |
| title | A Stable-Set Bound and Maximal Numbers of Nash Equilibria in Bimatrix Games |
| topic | Computer Science and Game Theory Combinatorics 91A05 G.2 |
| url | https://arxiv.org/abs/2411.12385 |