Designing efficient algorithms to compute Nash equilibria poses considerable challenges in Algorithmic Game Theory and Optimization. In this work, we employ integer programming techniques to compute Nash equilibria in Integer Programming Games, a class of simultaneous and non-cooperative games where each player solves a parametrized integer program. We introduce ZERO Regrets, a general and efficient cutting plane algorithm to compute, enumerate, and select Nash equilibria. Our framework leverages the concept of equilibrium inequality, an inequality valid for any Nash equilibrium, and the associated equilibrium separation oracle. We evaluate our algorithmic framework on a wide range of practical and methodological problems from the literature, providing a solid benchmark against the existing approaches.

The paper is available at arXiv:2111.06382

The Idea in 1'

In this joint work with my friend (and colleague) Rosario, we propose a theoretical and computational framework to efficiently select and enumerate pure Nash equilibria in Integer Programming Games, namely games where each player solves

\[ \max_{x^i} \{ u^i(x^i, x^{-i}): x^i \in \mathcal{X}^i \}, \; \mathcal{X}^i := \{ A^i x^i \le b^i, x^i \in \mathbb{Z}^{m} \}.\]

In order to do so, we use standard objects from Integer Programming, and adapt them to the realm of equilibria. We lift the problem to a higher-dimensional space of all players' variables (i.e., a space that contains \(\prod_i \mathcal{X}^i\)), and provide a single cutting plane family that is sufficient to describe the convex-hull of the Nash equilibria.

With respect to the Cut-And-Play, here we focus specifically on pure Nash Equilibria and the issue of their selection.