License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1311
URN: urn:nbn:de:0030-drops-13110
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1311/
Go to the corresponding LIPIcs Volume Portal

Yannakakis, Mihalis

Equilibria, Fixed Points, and Complexity Classes

pdf-format:
22011.YannakakisMihalis.Paper.1311.pdf (0.2 MB)

Abstract

Many models from a variety of areas involve the computation of an
equilibrium or fixed point of some kind. Examples include Nash
equilibria in games; market equilibria; computing optimal strategies
and the values of competitive games (stochastic and other games);
stable configurations of neural networks; analysing basic stochastic
models for evolution like branching processes and for language like
stochastic context-free grammars; and models that incorporate the
basic primitives of probability and recursion like recursive Markov
chains. It is not known whether these problems can be solved in
polynomial time. There are certain common computational principles
underlying different types of equilibria, which are captured by the
complexity classes PLS, PPAD, and FIXP. Representative complete
problems for these classes are respectively, pure Nash equilibria in
games where they are guaranteed to exist, (mixed) Nash equilibria in
2-player normal form games, and (mixed) Nash equilibria in normal
form games with 3 (or more) players. This paper reviews the
underlying computational principles and the corresponding classes.

BibTeX - Entry

@InProceedings{yannakakis:LIPIcs:2008:1311,
  author =	{Mihalis Yannakakis},
  title =	{{Equilibria, Fixed Points, and Complexity Classes}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{19--38},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1311},
  URN =		{urn:nbn:de:0030-drops-13110},
  doi =		{10.4230/LIPIcs.STACS.2008.1311},
  annote =	{Keywords: Equilibria, Fixed points, Computational Complexity, Game Theory}
}

Keywords: Equilibria, Fixed points, Computational Complexity, Game Theory
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 05.02.2008

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