7 Search Results for "von Stengel, Bernhard"

Document
DOI: 10.4230/LIPIcs.SEA.2023.12
Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games

Authors: Miriam Fischer and Akshay Gupte

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player noncooperative games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended for large games. Hence, the multilinear feasibility program is an alternative method to find a Nash equilibrium in multi-player games, and outperforms many common algorithms. The mixed-integer formulations are generalisations of known mixed-integer programs for two-player games, however unlike two-player games, these mixed-integer programs do not give better performance than existing algorithms.
Cite as

Miriam Fischer and Akshay Gupte. Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 12:1-12:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.SEA.2023.12,
  author =	{Fischer, Miriam and Gupte, Akshay},
  title =	{{Multilinear Formulations for Computing a Nash Equilibrium of Multi-Player Games}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.12},
  URN =		{urn:nbn:de:0030-drops-183620},
  doi =		{10.4230/LIPIcs.SEA.2023.12},
  annote =	{Keywords: Noncooperative n-person games, Nash equilibrium, Multilinear functions, Nonconvex problems, Mixed-integer optimization}
}
Document
DOI: 10.4230/DagRep.3.4.69
Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161)

Authors: Sergiu Hart, Éva Tardos, and Bernhard von Stengel

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13161 "Interface of Computation, Game Theory, and Economics". The workshop was strongly interdisciplinary, on the leading edge of current topics generally connected to algorithmic game theory: Mechanism design and auctions, interactions in networks, social models, and dynamics and equilibrium in games and markets. We summarize these topics, give the talk abstracts, and comment on experiences related to the organization of the workshop.
Cite as

Sergiu Hart, Éva Tardos, and Bernhard von Stengel. Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161). In Dagstuhl Reports, Volume 3, Issue 4, pp. 69-90, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{hart_et_al:DagRep.3.4.69,
  author =	{Hart, Sergiu and Tardos, \'{E}va and von Stengel, Bernhard},
  title =	{{Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161)}},
  pages =	{69--90},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Hart, Sergiu and Tardos, \'{E}va and von Stengel, Bernhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.4.69},
  URN =		{urn:nbn:de:0030-drops-41341},
  doi =		{10.4230/DagRep.3.4.69},
  annote =	{Keywords: Algorithmic Game Theory, Economics, Internet, Nash Equilibrium, Mechanism Design, Auctions}
}
Document
DOI: 10.4230/DagSemProc.10171.1
10171 Abstracts Collection – Equilibrium Computation

Authors: Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani

Published in: Dagstuhl Seminar Proceedings, Volume 10171, Equilibrium Computation (2010)

Abstract
From April 25 to April 30, 2010, the Dagstuhl Seminar 10171 ``Equilibrium Computation'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. 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

Edith Elkind, Nimrod Megiddo, Peter Bro Miltersen, Bernhard von Stengel, and Vijay V. Vazirani. 10171 Abstracts Collection – Equilibrium Computation. In Equilibrium Computation. Dagstuhl Seminar Proceedings, Volume 10171, pp. 1-18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{elkind_et_al:DagSemProc.10171.1,
  author =	{Elkind, Edith and Megiddo, Nimrod and Miltersen, Peter Bro and von Stengel, Bernhard and Vazirani, Vijay V.},
  title =	{{10171 Abstracts Collection – Equilibrium Computation}},
  booktitle =	{Equilibrium Computation},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10171},
  editor =	{Edith Elkind and Nimrod Megiddo and Peter Bro Miltersen and Vijay V. Vazirani and Bernahrd von Stengel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10171.1},
  URN =		{urn:nbn:de:0030-drops-26738},
  doi =		{10.4230/DagSemProc.10171.1},
  annote =	{Keywords: Equilibrium computation, algorithmic game theory}
}
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

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

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

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

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

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

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

Published in: Dagstuhl Seminar Proceedings, Volume 7471, Equilibrium Computation (2008)

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}
}
  • Refine by Author
  • 3 von Stengel, Bernhard
  • 2 Herings, P. Jean-Jacques
  • 1 Balthasar, Anne
  • 1 Bro Miltersen, Peter
  • 1 Elkind, Edith
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Exact and approximate computation of equilibria
  • 1 Theory of computation → Nonconvex optimization

  • Refine by Keyword
  • 3 Equilibrium computation
  • 2 Nash Equilibrium
  • 1 Algorithmic Game Theory
  • 1 Auctions
  • 1 Bimatrix games
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 4 2008
  • 1 2010
  • 1 2013
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact