Abstract
This talk will survey two graphical models which the authors have proposed
for compactly representing singleshot, finiteaction games in which a large
number of agents contend for scarce resources.
The first model considered is LocalEffect Games (LEGs). These games often
(but not always) have purestrategy 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 purestrategy
equilibria exist in the absence of potential functions.
Actiongraph games (AGGs) are a fully expressive game representation which
can compactly express both strict and contextspecific 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.
BibTeX  Entry
@InProceedings{leytonbrown_et_al:DSP:2005:220,
author = {Kevin LeytonBrown and Navin A.R. Bhat},
title = {Computing Nash Equilibria of ActionGraph Games},
booktitle = {Computing and Markets},
year = {2005},
editor = {Daniel Lehmann and Rudolf M{\"u}ller and Tuomas Sandholm},
number = {05011},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/220},
annote = {Keywords: compact representation of games, actiongraph games, Nash}
}
Keywords: 

compact representation of games, actiongraph games, Nash 
Freie Schlagwörter (deutsch): 

equilibria 
Seminar: 

05011  Computing and Markets 
Issue Date: 

2005 
Date of publication: 

26.07.2005 