New Algorithm Finds Nash Equilibrium in 5,600 Games to 1e-5 Precision

Computing Nash equilibria in general-sum games has long been one of the awkward problems at the intersection of game theory and machine learning. Universal algorithms with a global convergence guarantee are almost nonexistent. In arXiv:2609.16158, Hongbo Sun proposes a method that closes a significant part of this gap: the algorithm solves arbitrary m-player, n-action games to any prescribed precision and inherits global linear convergence. Across 5600 randomly generated instances, the gap dropped below 1e-5 in every case.

From a single simplex to a product of simplices

The work builds on the fiber bundle path-following framework described in the author's previous paper, arXiv:2606.00778. That framework solved finite-dimensional variational inequalities on a simplex, the set of probability distributions over a set of options. That is not enough for games. In a game with several participants, each player has their own distribution over actions, and the feasible region becomes a product of simplices.

The straightforward route would be to prove all the convergence properties again for the new domain. Sun took a different one. He constructs an equivalent variational inequality on a single simplex and establishes a fiber bundle isomorphism between the two frameworks. He then adds a slice-extension argument that transfers all the guarantees from the original work. No new convergence theory is needed, because the old one applies through the geometric equivalence.

The resulting object is a composite bundle. According to the author, it allows jumps along fibers that bypass singular points. Those are exactly the points around which the usual guarantees of path-following methods stop working.

What the method actually guarantees

Global linear convergence comes in two forms here, and the difference matters:

• for nonsingular equilibria, the solution is found exactly;
• for singular equilibria, any prescribed precision is reached.

This split honestly reflects the nature of the problem. Degenerate cases do occur in general games, and many numerical methods lose stability or cycle when they hit them. Here, the jumps across fibers are supposed to keep the trajectory away from singular points.

The 5600-game test

The experimental section compares extreme configurations. The dimensions span a range from a two-player game with 128 actions each to a 128-player game with two actions each. These regimes are structured differently:

• 2 players × 128 actions: a small number of participants and a wide strategy space;
• 128 players × 2 actions: a huge number of participants making binary choices, where the total number of action combinations grows exponentially;
• intermediate configurations between these two extremes;
• 5600 random instances in total, with a success criterion of a gap below 1e-5.

The algorithm reached this threshold in every case. The reported results imply that the series had no failures, cycling, or unsuccessful runs. For random games that is a strong signal, although random instances are no substitute for structured problems such as poker abstractions or market mechanisms.

Why AI engineers should care

Nash equilibrium underlies multi-agent learning, self-play, adversarial setups such as GANs, auction mechanisms, and the analysis of interacting autonomous agents. When there are many agents and their goals diverge, the question "where will the system settle?" becomes an equilibrium problem. In practice today, people more often use learning dynamics, which do not always converge. A method with a global guarantee offers an alternative: a solver that can serve as a reference when checking heuristics.

The practical side is simple. The code and data are published in the FiberBundle_VI repository on GitHub, so the results can be reproduced and run on your own games. The first things teams working on multi-agent systems should check are how the method behaves on structured games and how well its running time scales as the number of players grows. For game theory researchers, the work is interesting in its own right: the fiber bundle isomorphism trick shows how to transfer guarantees between domains without rewriting the proofs.

The paper has so far collected a modest two upvotes on Hugging Face Daily Papers, but the topic is the kind that rarely makes headlines and regularly decides whether a multi-agent system will behave predictably.