Nash Propagation for Loopy Graphical Games

We introduce NashProp, an iterative and local message-passing algorithm forcomputing Nash equilibria in multi-player games represented by arbitrary undirected graphs. We provide a formal analysis and experimental evidencedemonstrating that NashProp performs well on large graphical games with many loops, often converging in just a dozen iterations ongraphs with hundreds of nodes. NashProp generalizes the tree algorithm of (Kearns et al. 2001), and can be viewed as similar in spirit to belief propagation in probabilistic inference,and thus complements the recent work of (Vickrey and Koller 2002), who explored a junction tree approach. Thus, as for probabilistic inference,we have at least two promising general-purpose approaches toequilibria computation in graphs.