  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
$\epsilon$-approximation.
