The Nash equilibrium enlightens the structure of rational behavior in non-cooperative multi-agent decision-making. However, besides its existence, the concept is as helpful as one can efficiently compute it. This paper introduces the Cut-and-Play, an efficient algorithm for computing equilibria in simultaneous non-cooperative games where players solve (parametric) nonconvex and possibly unbounded optimization problems. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the original game and refines them with techniques from integer programming. We test our algorithm on two families of challenging nonconvex games involving discrete decisions and bilevel programs, and we empirically demonstrate that it efficiently computes equilibria and outperforms existing game-specific algorithms.

The paper is available at arXiv:2111.05726.

The Idea in 1'

In a nutshell, we compute Nash equilibria for Separable Non-convex games, i.e., simultaneous non-cooperative games where each player solves an optimization problem whose objective function \(f^i(x^i;x^{-i})\) is a "separable polynomial" in the player's variables.

\[ \min_{x^i}\{f^i(x^i;x^{-i}) : x^i \in \mathcal{X}^i \}\]

We prove there exists an equivalent convex representation of the game where each player's feasible is \(\text{cl conv}(\mathcal{X}^i)\), and that there is an exact correspondence between the Nash equilibria of the convexified and the original game. We exploit this fundamental theorem to build a cutting plane algorithm that iteratively refines an outer approximation of \(\text{cl conv}(\mathcal{X}^i)\) for each player \(i\). Our computational tests show our method tends to outperform existing approaches, and provides useful insights to market regulators.