Games of fixed rank: A hierarchy of bimatrix games
| dc.creator | Kannan, Ravi | |
| dc.creator | Theobald, Thorsten | |
| dc.date | 2005-11-04 | |
| dc.date.accessioned | 2026-07-07T06:49:33Z | |
| dc.date.available | 2026-07-07T06:49:33Z | |
| dc.description | We propose a new hierarchical approach to understand the complexity of the open problem of computing a Nash equilibrium in a bimatrix game. Specifically, we investigate a hierarchy of bimatrix games $(A,B)$ which results from restricting the rank of the matrix $A+B$ to be of fixed rank at most $k$. For every fixed $k$, this class strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We show that even for $k=1$ the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we can provide polynomial time algorithms for finding an $ε$-approximation. | |
| dc.description | 13 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0511021 | |
| dc.identifier | http://arxiv.org/abs/cs/0511021 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/104390 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Combinatorics | |
| dc.title | Games of fixed rank: A hierarchy of bimatrix games | |
| dc.type | text |