University of Southampton
4pm Tuesday 15th April 2008
Room 2511, JCMB, King's Buildings
Graphical games are a natural and compact representation formalism for a large class of multi-player games. They have been introduced by Kearns, Littman and Singh in UAI'01, and have recently been used in the proof of the seminal PPAD-hardness result for finding a Nash equilibrium in 2-player, n-action games. This proof shows that finding a Nash equilibrium in general bounded-degree graphical games in PPAD-hard as well. In this talk, we discuss polynomial-time algorithms for finding Nash equilibria in graphical games on bounded-degree trees. We show that an algorithm for this problem that was proposed by Littman, Kearns and Singh in NIPS'01 is incorrect and describe how to fix it. Our version of the algorithm runs in polynomial time if the underlying graph is a path, but may require exponential time even on very simple trees. We show that this is, in some sense, inevitable: any algorithm that is based on the general approach of Littman et al. will have to store an exponentially large data structure. Moreover, the problem remains PPAD-complete for graphs with bounded pathwidth. We also discuss the problem of finding Nash equilibria with special properties, such as the ones that maximize the total payoff or guarantee certain payoffs to all players.