Equilibrium Numbers in Non-Square Bimatrix Games
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≥5, we construct 3× 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× 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× n games, we construct games where all but a fraction of O(1/n) of the maximum number of vertices are equilibrium strategies.
Related
- Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games
- Stability of ideal Nash equilibrium points in generalized multi-criteria games, interval-valued games, and existence in single-leader--multi-follower problems
- Equilibrium and Infeasibility: A new solution concept for games
- On the counting function of square-full numbers
- Equilibrium Learning in Unbounded Stochastic Games with Gaussian Transitions
BibTeX
@misc{ickstadt2026equilibrium,
title = {{Equilibrium Numbers in Non-Square Bimatrix Games}},
author = {Constantin Ickstadt and Thorsten Theobald and Bernhard von Stengel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.24878},
eprint = {2609.24878},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.24878},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Equilibrium Numbers in Non-Square Bimatrix Games
AU - Constantin Ickstadt
AU - Thorsten Theobald
AU - Bernhard von Stengel
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.24878
UR - https://arxiv.org/abs/2609.24878
AB - 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≥5, we construct 3× 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× 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× n games, we construct games where all but a fraction of O(1/n) of the maximum number of vertices are equilibrium strategies.
ER -