Finding a Nash equilibrium of a random win-lose game in expected polynomial time
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911210815881216 |
|---|---|
| author | Collevecchio, Andrea Lugosi, Gabor Vetta, Adrian Zhang, Rui-Ray |
| author_facet | Collevecchio, Andrea Lugosi, Gabor Vetta, Adrian Zhang, Rui-Ray |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12846 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding a Nash equilibrium of a random win-lose game in expected polynomial time Collevecchio, Andrea Lugosi, Gabor Vetta, Adrian Zhang, Rui-Ray Computer Science and Game Theory Probability 91A05 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$. |
| title | Finding a Nash equilibrium of a random win-lose game in expected polynomial time |
| topic | Computer Science and Game Theory Probability 91A05 |
| url | https://arxiv.org/abs/2510.12846 |