Algorithms for Rank-1 Bimatrix Games

Explore algorithms for rank-1 bimatrix games in this lecture from the Hausdorff Trimester Program on Combinatorial Optimization. Delve into the concept of game rank, defined as the matrix rank of the sum of two payoff matrices, and discover how rank-1 games can be solved efficiently. Learn about polynomial-time algorithms for finding Nash equilibria and the application of path-following techniques. Examine the potential for exponential numbers of equilibria in rank-1 games and consider the conjecture regarding the co-NP-completeness of uniqueness in Nash equilibrium. Investigate topics such as rank reduction, global Newton method, parameterized zero-sum games, and the "wrap-around" hyperplane concept. Gain insights into binary search and enumeration algorithms, as well as parameterized linear programming inspired by Murty's work. Conclude by discussing the implications of PPAD- versus NP-hardness in the context of rank-1 bimatrix games.