License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-2209
URL: http://drops.dagstuhl.de/opus/volltexte/2005/220/
Go to the corresponding Portal

Leyton-Brown, Kevin ; Bhat, Navin A.R.

Computing Nash Equilibria of Action-Graph Games

pdf-format:
Document 1.pdf (412 KB)

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.

BibTeX - Entry

@InProceedings{leytonbrown_et_al:DSP:2005:220,
  author =	{Kevin Leyton-Brown and Navin A.R. Bhat},
  title =	{Computing Nash Equilibria of Action-Graph 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 =	{1862-4405},
  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, action-graph games, Nash}
}

Keywords: compact representation of games, action-graph games, Nash
Freie Schlagwörter (deutsch): equilibria
Seminar: 05011 - Computing and Markets
Issue Date: 2005
Date of publication: 26.07.2005

DROPS-Home | Fulltext Search | Imprint Published by LZI