The ZERO Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming

Designing efficient algorithms to compute Nash equilibria poses considerable challenges in Algorithmic Game Theory (AGT). We shed new light on the intersection between Algorithmic Game Theory and Integer Programming. We introduce ZERO Regrets, a general and efficient cutting plane algorithm to compute, enumerate, and select Pure Nash Equilibria (PNEs) in Integer Programming Games, a class of simultaneous and non-cooperative games. We present a theoretical foundation for our algorithmic reasoning and provide a polyhedral characterization of the convex hull of the Pure Nash Equilibria. We introduce the concept of equilibrium inequality, and devise an equilibrium separation oracle to separate non-equilibrium strategies from PNEs. We evaluate our algorithmic framework on a wide range of problems from the literature and provide a solid benchmark against the existing algorithmic approaches.