Fixed-point bundle method computes Nash equilibria on product simplices
Original title: The fixed-point bundle method over product-of-simplex domains arising from game equilibria
The path-following algorithm reached 10^{-5} precision on all 5600 random games, from 2-player 128-action to 128-player 2-action.
The paper extends the fixed-point bundle framework for variational inequalities from a simplex to a product of simplices so it applies to Nash equilibria of general-sum games. An equivalent simplex formulation and a fiber-bundle isomorphism carry over the simplex method's global linear convergence. Code and data are released on GitHub.
Unconfirmed: Convergence and the 10^{-5} result are reported by the authors on synthetic instances.
- The resulting object has a composite fiber bundle structure.
- Global linear convergence is inherited from the simplex-domain framework.
- Test games range from 2 players with 128 actions to 128 players with 2 actions.
- Code is at github.com/shb20tsinghua/FiberBundle_VI.
From the original article
1 min read at huggingface.co
Developing general-purpose algorithms with global asymptotic convergence guarantees for Nash equilibria of general-sum games remains a longstanding challenge. This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from simplex domains to product-of-simplex domains, enabling its direct application to Nash equilibrium computation.
By Hongbo Sun · huggingface.co
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.