Reproduce “Finding a Nash equilibrium of a random win-lose game in expected polynomial time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Andrea Collevecchio, Gabor Lugosi, Adrian Vetta, Rui-Ray Zhang
The authors present an expected-polynomial-time algorithm for finding Nash equilibria in random two-player win-lose games. It represents payoff tables as a directed bipartite graph and searches for stable small cycles that certify equilibria; Lemke–Howson is a fallback. For ℓ=2, one stated density regime has expected running time O(n²). Results cover nearly all densities, leaving gaps near p∼n⁻¹ and p∼n⁻¹ᐟ².
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.