596. A Stable-Set Bound and Maximal Numbers of Nash Equilibria in Bimatrix Games
Invited abstract in session MC-10: Optimization, Learning, and Games II, stream Optimization, Learning, and Games.
Monday, 14:00-16:00Room: B100/8011
Authors (first author is the speaker)
| 1. | Constantin Ickstadt
|
| Goethe-Universität |
Abstract
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.
Keywords
- Computational game theory
Status: accepted
Back to the list of papers