Computing Nash Equilibria of Action-Graph Games

Abstract

This talk will survey two graphical models which the authors have proposed 
for compactly representing single-shot, finite-action games in which a large 
number of agents contend for scarce resources.  

The first model considered is Local-Effect Games (LEGs). These games often 
(but not always) have pure-strategy Nash equilibria. Finding a potential 
function is a good technique for finding such equilibria. We give a complete 
characterization of which LEGs have potential functions and provide the 
functions in each case; we also show a general case where pure-strategy 
equilibria exist in the absence of potential functions. 

Action-graph games (AGGs) are a fully expressive game representation which 
can compactly express both strict and context-specific independence between 
players' utility functions, and which generalize LEGs. We present algorithms 
for computing both symmetric and arbitrary equilibria of AGGs, based on a 
continuation method proposed by Govindan and Wilson. We analyze the worst-
case cost of computing the Jacobian of the payoff function, the exponential-
time bottleneck step of this algorithm, and in all cases achieve exponential 
speedup. When the indegree of G is bounded by a constant and the game is 
symmetric, the Jacobian can be computed in polynomial time.