In Algorithmic Game Theory (AGT), designing efficient algorithms to compute Nash equilibria poses considerable challenges. We make progress in the field and shed new light on the intersection between Algorithmic Game Theory and Integer Programming. We introduce ZERO Regrets, a general 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 test ZERO Regrets on two paradigmatic classes of games: the Knapsack Game and the Network Formation Game, a well-studied game in AGT. Our algorithm successfully solves relevant instances of both games and shows promising applications for equilibria selection.

The paper is available here: arXiv:2111.06382

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. In order to do so, we use standard objects from Integer Programming, and adapt them to the realm of equilibria.

Rosario and I finding the best PNE in our favorite 100_4.txt Knapsack Game instance

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

Take me back