Title: Algorithms for Rank-1 Bimatrix Games
| Speaker: | Bernhard von Stengel |
| Affiliation: | London School of Economics |
| Room: | MC 5501 |
Abstract:
The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. For a game of rank k, the set of its Nash equilibria is the intersection of a one-dimensional set of equilibria of parameterized games of rank k-1 with a hyperplane. For a game of rank 1, this is a monotonic path of solutions to a parameterized zero-sum game and hence LP. One intersection of this path with the hyperplane can be found in polynomial time by binary search. This gives a polynomial-time algorithm to find an equilibrium of a game of rank 1. On the other hand, there are rank-1 games with exponentially many equilibria, which answers an open problem by Kannan and Theobald (2010). Hence, the exponential multiplicity of equilibria does not prevent one equilibrium in polynomial time. In this spirit, we conjecture that the UNIQUENESS of an equilibrium of a rank-1 game is co-NP-hard. For games of higher rank, the parameterized equilibria of lower rank correspond to the computation of the global Newton method by Govindan and Wilson (2003), which for two-player games is a special case of Lemke's algorithm.
Joint work with Bharat Adsul, Jugal Garg, Ruta Mehta, and Milind Sohoni.