Integer Programming Games: A Gentle Computational Overview

arXiv2306.02817MaRDI QIDQ6439233

Author name not available (Why is that?)

Publication date: 5 June 2023

Abstract: In this tutorial, we present a computational overview on computing Nash equilibria in Integer Programming Games ($IPG$s), $i.e.$, how to compute solutions for a class of non-cooperative and nonconvex games where each player solves a mixed-integer optimization problem. $IPG$s are a broad class of games extending the modeling power of mixed-integer optimization to multi-agent settings. This class of games includes, for instance, any finite game and any multi-agent 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.

Has companion code repository: https://github.com/ds4dm/zero

This page was built for publication: Integer Programming Games: A Gentle Computational Overview

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439233)