V Soni, S Singh, and MP Wellman

Sixth International Joint Conference on Autonomous Agents and Multiagent Systems, pages 423–430, May 2007.
Copyright (c) 2007, IFAAMAS.


We formulate the problem of computing equilibria in multiplayer games represented by arbitrary undirected graphs as a constraint satisfaction problem and present two algorithms. The first is PureProp: an algorithm for computing approximate Nash equilibria in complete information one-shot games and approximate Bayes-Nash equilibria in one-shot games of incomplete information. PureProp unifies existing message-passing based algorithms for solving these classes of games. We also address repeated graphical games, and present a second algorithm, PureProp-R, for computing approximate Nash equilibria in these games.