Thorsten Theobald,
Technische Universitaet Berlin
Games of fixed rank - a hierarchy of bimatrix games |
Bimatrix games are the very basic model of game theory.
The geometry of Nash equilibria in these games (e.g.,
"how many Nash equilibria can there be?") naturally leads to
combinatorial questions on polytopes concerning the maximal number
of complementary vertex pairs. However, determining the
maximal number of equilibria in a (non-degenerate)
$n \times n$-game is an open problem.
Here, we introduce a new hierarchy of bimatrix games which
is imposed by a natural rank condition. We study the resulting
enumerative questions on the polytopes, as well as the algorithmic
implications.
(Based on joint work with Ravi Kannan.)