{"ID":2855555,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12846","arxiv_id":"2510.12846","title":"Finding a Nash equilibrium of a random win-lose game in expected polynomial time","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\\times 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\\sim cn^{-a}$ for some parameters $a,c\\ge 0$, then there is an expected polynomial-time algorithm whenever $a\\not\\in \\{1/2, 1\\}$. In addition, if $a = 1/2$ there is an efficient algorithm if either $c \\le e^{-52} 2^{-8} $ or $c\\ge 0.977$. If $a=1$, then there is an expected polynomial-time algorithm if either $c\\le 0.3849$ or $c\\ge \\log^9 n$.","short_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\\times n$ payoff matrices are independent and identically distributed (i.i.d.) Bernoulli ra...","url_abs":"https://arxiv.org/abs/2510.12846","url_pdf":"https://arxiv.org/pdf/2510.12846v1","authors":"[\"Andrea Collevecchio\",\"Gabor Lugosi\",\"Adrian Vetta\",\"Rui-Ray Zhang\"]","published":"2025-10-14T05:24:15Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"math.PR\"]","methods":"[]","has_code":false}