1 Search Results for "Waldmann, Clara"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.32
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

Authors: George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ̃(√d)-approximate PNE, which provides the first super-constant lower bound. Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. The circuit gadget is of independent interest and it allows us to also prove hardness for a variety of problems related to the complexity of PNE in congestion games. For example, we demonstrate that the question of existence of α-PNE in which a certain set of players plays a specific strategy profile is NP-hard for any α < 3^(d/2), even for unweighted congestion games. Finally, we study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n. We show that n-PNE always exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.
Cite as

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, and Clara Waldmann. Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{christodoulou_et_al:LIPIcs.ICALP.2020.32,
  author =	{Christodoulou, George and Gairing, Martin and Giannakopoulos, Yiannis and Po\c{c}as, Diogo and Waldmann, Clara},
  title =	{{Existence and Complexity of Approximate Equilibria in Weighted Congestion Games}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.32},
  URN =		{urn:nbn:de:0030-drops-124392},
  doi =		{10.4230/LIPIcs.ICALP.2020.32},
  annote =	{Keywords: Atomic congestion games, existence of equilibria, pure Nash equilibria, approximate equilibria, hardness of equilibria}
}
  • Refine by Author
  • 1 Christodoulou, George
  • 1 Gairing, Martin
  • 1 Giannakopoulos, Yiannis
  • 1 Poças, Diogo
  • 1 Waldmann, Clara

  • Refine by Classification
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Exact and approximate computation of equilibria
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Representations of games and their complexity

  • Refine by Keyword
  • 1 Atomic congestion games
  • 1 approximate equilibria
  • 1 existence of equilibria
  • 1 hardness of equilibria
  • 1 pure Nash equilibria

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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