Abstract
A long-standing open problem in algorithmic game theory asks whether or not there is a polynomial time algorithm to compute a Nash equilibrium in a random bimatrix game. We study random win-lose games, where the entries of the n× n payoff matrices are independent and identically distributed (i.i.d.) Bernoulli random variables with parameter p=p(n). We prove that, for nearly all values of the parameter p=p(n), there is an expected polynomial-time algorithm to find a Nash equilibrium in a random win-lose game. More precisely, if p∼ cn^-a for some parameters a,c≥ 0, then there is an expected polynomial-time algorithm whenever a∈ {1/2, 1}. In addition, if a = 1/2 there is an efficient algorithm if either c ≤ e⁻⁵² 2⁻⁸ or c≥ 0.977. If a=1, then there is an expected polynomial-time algorithm if either c≤ 0.3849 or c≥ log⁹ n.