ECAI 2004 Conference Paper

[full paper]

Constrained Pure Nash Equilibria in Graphical Games

Gianluigi Greco, Francesco Scarcello

The rational behavior of non-cooperative players is often formalized by means of the game theoretic notion of Nash equilibrium. However, there are several practical applications (such as multi agent planning, mechanism design, and routing protocols design) where the computation of any Nash equilibrium could not be satisfactory, since we are often interested only in equilibria that satisfy some additional requirements. Even though such Nash equilibria, called constrained Nash equilibria, received a great deal of interest, a comprehensive formalization and a deep investigation of the complexities issues related to their computation are still missing. In this paper, we present a formal framework for specifying and working with these constraints, by focusing on graphical games, where a player p may be directly interested only on part of the other players, called neighbors of p. We study the computational complexity of the main problems arising in this framework for pure strategies. Furthermore, we identify some restrictions on players' interaction that make some of these problems easy, by exploiting the graphical representation of the structure of the game, and a generalization of graph acyclicity called treewidth. In these tractable cases, we also provide highly-parallelizable algorithms for the computation of such constrained Nash equilibria.

Keywords: Game Theory, Decision Theory

Citation: Gianluigi Greco, Francesco Scarcello: Constrained Pure Nash Equilibria in Graphical Games. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.181-185.