New bounds on the number of equilibria in non-square games
Equilibrium Numbers in Non-Square Bimatrix Games
Computer Science and Game Theory
Summary
Games where two players each choose from a list of strategies can have many different 'balance points' called Nash equilibria, where neither player wants to change their choice. Past studies mostly looked at games where both players have the same number of choices, but this paper explores what happens when one player’s choices stay fixed while the other grows. The authors find new sharp limits on how many equilibria can appear in these cases, using math about shapes called polytopes and graph theory ideas. They also provide examples of games that reach these limits and use computer checks to confirm their counts.
What this means in practice
- •For algorithm designers: Determine limits on number of equilibria in asymmetrical bimatrix games to improve game-solving algorithms.
- •For economic modelers: Use structural bounds on equilibria counts to better analyze strategic interactions where one participant has many choices.
Authors
Constantin Ickstadt, Thorsten Theobald, Bernhard von Stengel
Abstract
Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies.