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.07471.3
URN: urn:nbn:de:0030-drops-15257
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1525/
Go to the corresponding Portal

Herings, P. Jean-Jacques ; Peeters, Ronald

Homotopy Methods to Compute Equilibria in Game Theory

pdf-format:
07471.PeetersRonald.Paper.1525.pdf (0.4 MB)

Abstract

This paper presents a survey of the use of homotopy methods in game theory. Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by various selection theories. We present the relevant techniques underlying homotopy algorithms. We give detailed expositions of the Lemke-Howson algorithm and the van den Elzen-Talman algorithm to compute Nash equilibria in 2-person games, and the Herings-van den Elzen, Herings-Peeters, and McKelvey-Palfrey algorithms to compute Nash equilibria in general $n$-person games. We explain how the main ideas can be extended to compute equilibria in extensive form and dynamic games, and how homotopies can be used to compute all Nash equilibria.

BibTeX - Entry

@InProceedings{herings_et_al:DagSemProc.07471.3,
  author =	{Herings, P. Jean-Jacques and Peeters, Ronald},
  title =	{{Homotopy Methods to Compute Equilibria in Game Theory}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--40},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7471},
  editor =	{P. Jean-Jacques Herings and Marcin Jurdzinski and Peter Bro Miltersen and Eva Tardos and Bernhard von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1525},
  URN =		{urn:nbn:de:0030-drops-15257},
  doi =		{10.4230/DagSemProc.07471.3},
  annote =	{Keywords: Homotopy, Equilibrium computation, Non-cooperative games, Nash Equilibrium}
}

Keywords: Homotopy, Equilibrium computation, Non-cooperative games, Nash Equilibrium
Collection: 07471 - Equilibrium Computation
Issue Date: 2008
Date of publication: 04.06.2008

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