  Linear complementarity programming is a generalization of linear programming
which encompasses the computation of Nash equilibria for bimatrix games. While
the latter problem is PPAD-complete, we show that the tropical analogue of the
complementarity problem associated with Nash equilibria can be solved in
polynomial time. Moreover, we prove that the Lemke--Howson algorithm carries
over the tropical setting and performs a linear number of pivots in the worst
case. A consequence of this result is a new class of (classical) bimatrix games
for which Nash equilibria computation can be done in polynomial time.
