Integer Programming Games: A Gentle Computational Overview
In this tutorial, we present a computational overview on computing Nash equilibria in integer programming games (IPGs), that is, how to compute solutions for a class of noncooperative and nonconvex games where each player solves a mixed-integer optimization problem. IPGs are a broad class of games extending the modeling power of mixed-integer optimization to multiagent settings. This class of games includes, for instance, any finite game and any multiagent extension of traditional combinatorial optimization problems. After providing some background motivation and context of applications, we systematically review and classify the state-of-the-art algorithms to compute Nash equilibria. We propose an essential taxonomy of the algorithmic ingredients needed to compute equilibria, and we describe the theoretical and practical challenges associated with equilibria computation. Finally, we quantitatively and qualitatively compare a sequential Stackelberg game with a simultaneous IPG to highlight the different properties of their solutions.