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.

Intro
Rank-k games
Suggested example of a rank-1 game
NE of games with parameter X
Global Newton Method [Govindan/Wilson 2003]
Rank reduction by intersection with hyperplane
works for rank 1: monotone path, unique rank-O NE
LP for zero-sum game
LP for parameterized zero-sum game
Parameterized matrix (column bonuses)
Equivalent: Parameterized objective function
"Wrap-around" hyperplane defines the path
Algorithm 1: Binary search
Algorithm 2: Enumeration
Parameterized LP [Murty 1980]
Inspired by Murty
Output efficiency
PPAD- versus NP-hardness