Search Results

Documents authored by Leyton-Brown, Kevin

Document
DOI: 10.4230/DagSemProc.05011.6
Computing Nash Equilibria of Action-Graph Games

Authors: Kevin Leyton-Brown and Navin A.R. Bhat

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

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.
Cite as

Kevin Leyton-Brown and Navin A.R. Bhat. Computing Nash Equilibria of Action-Graph Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.05011.6},
  URN =		{urn:nbn:de:0030-drops-2209},
  doi =		{10.4230/DagSemProc.05011.6},
  annote =	{Keywords: compact representation of games, action-graph games, Nash equilibria}
}
Document
DOI: 10.4230/DagSemProc.05011.11
Local-Effect Games

Authors: Kevin Leyton-Brown and Moshe Tennenholtz

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

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.
Cite as

Kevin Leyton-Brown and Moshe Tennenholtz. Local-Effect Games. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{leytonbrown_et_al:DagSemProc.05011.11,
  author =	{Leyton-Brown, Kevin and Tennenholtz, Moshe},
  title =	{{Local-Effect Games}},
  booktitle =	{Computing and Markets},
  pages =	{1--6},
  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/entities/document/10.4230/DagSemProc.05011.11},
  URN =		{urn:nbn:de:0030-drops-2190},
  doi =		{10.4230/DagSemProc.05011.11},
  annote =	{Keywords: compact representation of games, congestion games, local-effect}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact