The fixed-point bundle method over product-of-simplex domains arising from game equilibria

The fixed-point bundle method over product-of-simplex domains arising from game equilibria. By Hongbo Sun. Published on the twenty-third of October. Its code repository is public but slight: seven source files.

Computing Nash equilibria of general-sum games with an algorithm that is both general-purpose and globally convergent remains a longstanding challenge. This work approaches it from an existing tool: the fixed-point bundle framework for finite-dimensional variational inequalities, which had been built for domains shaped like a single simplex. A game does not hand you a single simplex. It hands you a product of them, and that domain is where this paper takes the framework, so that it applies directly to Nash equilibrium computation.

The central result is an inheritance. The path-following algorithm for variational inequalities on product-of-simplex domains carries over the global linear convergence guarantees already established for the simplex-domain framework.

Getting there runs through geometry. On the product domain, the fixed-point bundle turns out to have a composite fiber bundle structure. The key innovation is to construct an equivalent variational inequality on a simplex, and then to show that the two fixed-point bundle frameworks are equivalent through a fiber bundle isomorphism. Once the two are tied together that way, the convergence guarantee proved on one side can be claimed on the other.

The guarantee is borrowed, so it holds on the terms of the simplex-domain framework it comes from. The abstract states no further conditions, and it does not restrict the games beyond being general-sum.

The numerical test is broad in shape. Across five thousand six hundred randomly generated game instances, the algorithm reached a precision of ten to the minus five on all of them. At one end sat games of two players and one hundred and twenty-eight actions. At the other, one hundred and twenty-eight players and two actions. One algorithm met the same precision whether the game had a few large choice sets or many tiny ones, and the released code and data let anyone push that range further.