The concept of Nash equilibrium enlightens the structure of rational behavior in strategic decision-making. However, the concept is as helpful as one can efficiently compute it. Although several algorithms can compute Nash equilibria in games where players optimize convex problems, little is known about the computation of equilibria when arbitrary non-convexities arise. Such non-convexities often portray complex operational requirements and are necessary from a modeling perspective. Aiming to fill this gap, we introduce the Cut-and-Play, an efficient algorithm for computing equilibria in games where players solve (parametric) non-convex optimization problems, i.e., each player's strategy set is non-convex. Our approach exploits a series of convex approximations of the original game and symbiotically incorporates equilibrium programming and integer programming techniques. We showcase the practical efficiency of our framework on Integer Programming Games and a class of simultaneous games among Stackelberg (bilevel) leaders.

The paper is available at arXiv:2111.05726.

The Idea in 1'

In a nutshell, we compute Nash equilibria for Reciprocally-Bilinear Games, i.e., simultaneous non-cooperative games where each player solves an optimization problem whose objective function is linear in the player's variables.

\[ \min_{x^i}\{ (c^i) ^\top x^i + (x^{-i})^\top C^ix^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.