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.)