2020/12/09 by Xavier Allamigeon, Stéphane Gaubert, Allamigeon, Xavier +3
Decision Sciences · #Game Theory and Applications
paper · doi:10.48550/arxiv.2012.05314
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.