Volume

Dagstuhl Seminar Proceedings, Volume 7471

Publication Details

  • published at: 2008-06-04
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.07471.1
07471 Abstracts Collection – Equilibrium Computation

Authors: P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Eva Tardos, and Bernhard von Stengel

Abstract
From 18 to 23 November 2007, the Dagstuhl Seminar 07471 ``Equilibrium Computation'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

P. Jean-Jacques Herings, Marcin Jurdzinski, Peter Bro Miltersen, Eva Tardos, and Bernhard von Stengel. 07471 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{herings_et_al:DagSemProc.07471.1,
  author =	{Herings, P. Jean-Jacques and Jurdzinski, Marcin and Bro Miltersen, Peter and Tardos, Eva and von Stengel, Bernhard},
  title =	{{07471 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--15},
  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/entities/document/10.4230/DagSemProc.07471.1},
  URN =		{urn:nbn:de:0030-drops-15286},
  doi =		{10.4230/DagSemProc.07471.1},
  annote =	{Keywords: Equilibrium, algorithm, polynomial time, game theory, economics}
}
Document
DOI: 10.4230/DagSemProc.07471.2
Equilibrium Tracing in Bimatrix Games

Authors: Anne Balthasar

Abstract
We analyze the relations of the van den Elzen-Talman algorithm, the Lemke-Howson algorithm and the global Newton method introduced by Govindan and Wilson. It is known that the global Newton method encompasses the Lemke-Howson algorithm; we prove that it also comprises the van den Elzen-Talman algorithm, and more generally, the linear tracing procedure, as a special case. This will lead us to a discussion of traceability of equilibria of index +1. We answer negatively the open question of whether, generically, the van den Elzen-Talman algorithm is flexible enough to trace all equilibria of index +1.
Cite as

Anne Balthasar. Equilibrium Tracing in Bimatrix Games. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{balthasar:DagSemProc.07471.2,
  author =	{Balthasar, Anne},
  title =	{{Equilibrium Tracing in Bimatrix Games}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--14},
  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/entities/document/10.4230/DagSemProc.07471.2},
  URN =		{urn:nbn:de:0030-drops-15265},
  doi =		{10.4230/DagSemProc.07471.2},
  annote =	{Keywords: Bimatrix games, Equilibrium computation, Homotopy methods, Index}
}
Document
DOI: 10.4230/DagSemProc.07471.3
Homotopy Methods to Compute Equilibria in Game Theory

Authors: P. Jean-Jacques Herings and Ronald Peeters

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

P. Jean-Jacques Herings and Ronald Peeters. Homotopy Methods to Compute Equilibria in Game Theory. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@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/entities/document/10.4230/DagSemProc.07471.3},
  URN =		{urn:nbn:de:0030-drops-15257},
  doi =		{10.4230/DagSemProc.07471.3},
  annote =	{Keywords: Homotopy, Equilibrium computation, Non-cooperative games, Nash Equilibrium}
}
Document
DOI: 10.4230/DagSemProc.07471.4
Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems

Authors: Nir Halman

Abstract
We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem. Using this formulation, and the known algorithm of Sharir and Welzl for LP-type problems, we obtain the first strongly subexponential solution for SSGs (a strongly subexponential algorithm has only been known for binary SSGs). Using known reductions between various games, we achieve the first trongly subexponential solutions for Discounted and Mean Payoff Games. We also give alternative simple proofs for the best known upper bounds for Parity Games and binary SSGs. To the best of our knowledge, the LP-type framework has been used so far only in order to yield linear or close to linear time algorithms for various problems in computational geometry and location theory. Our approach demonstrates the applicability of the LP-type framework in other fields, and for achieving subexponential algorithms. This work has been published in Algorithmica, volume 49 (September 2007), pages 37-50
Cite as

Nir Halman. Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 7471, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{halman:DagSemProc.07471.4,
  author =	{Halman, Nir},
  title =	{{Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--2},
  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/entities/document/10.4230/DagSemProc.07471.4},
  URN =		{urn:nbn:de:0030-drops-15274},
  doi =		{10.4230/DagSemProc.07471.4},
  annote =	{Keywords: Subexponential algorithm, LP-type framework}
}

Filters

  • Authors
  • B
  • Balthasar, Anne
  • Bro Miltersen, Peter
  • H
  • Halman, Nir
  • Herings, P. Jean-Jacques
  • J
  • Jurdzinski, Marcin
  • P
  • Peeters, Ronald
  • T
  • Tardos, Eva
  • V
  • von Stengel, Bernhard

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 About DROPS Imprint Privacy Contact