License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05011.6
URN: urn:nbn:de:0030-drops-2209
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/220/
Go to the corresponding Portal

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

Computing Nash Equilibria of Action-Graph Games

pdf-format:
05011.LeytonBrownKevin.Paper1.220.pdf (0.4 MB)

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:DagSemProc.05011.6,
  author =	{Leyton-Brown, Kevin and Bhat, Navin A.R.},
  title =	{{Computing Nash Equilibria of Action-Graph Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/220},
  URN =		{urn:nbn:de:0030-drops-2209},
  doi =		{10.4230/DagSemProc.05011.6},
  annote =	{Keywords: compact representation of games, action-graph games, Nash equilibria}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI