1 Search Results for "Lianeas, Thanasis"


Document
Track A: Algorithms, Complexity and Games
Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games

Authors: Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, and Stratis Skoulakis

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


Abstract
In this work, we seek a more refined understanding of the complexity of local optimum computation for Max-Cut and pure Nash equilibrium (PNE) computation for congestion games with weighted players and linear latency functions. We show that computing a PNE of linear weighted congestion games is PLS-complete either for very restricted strategy spaces, namely when player strategies are paths on a series-parallel network with a single origin and destination, or for very restricted latency functions, namely when the latency on each resource is equal to the congestion. Our results reveal a remarkable gap regarding the complexity of PNE in congestion games with weighted and unweighted players, since in case of unweighted players, a PNE can be easily computed by either a simple greedy algorithm (for series-parallel networks) or any better response dynamics (when the latency is equal to the congestion). For the latter of the results above, we need to show first that computing a local optimum of a natural restriction of Max-Cut, which we call Node-Max-Cut, is PLS-complete. In Node-Max-Cut, the input graph is vertex-weighted and the weight of each edge is equal to the product of the weights of its endpoints. Due to the very restricted nature of Node-Max-Cut, the reduction requires a careful combination of new gadgets with ideas and techniques from previous work. We also show how to compute efficiently a (1+ε)-approximate equilibrium for Node-Max-Cut, if the number of different vertex weights is constant.

Cite as

Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, and Stratis Skoulakis. Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fotakis_et_al:LIPIcs.ICALP.2020.50,
  author =	{Fotakis, Dimitris and Kandiros, Vardis and Lianeas, Thanasis and Mouzakis, Nikos and Patsilinakos, Panagiotis and Skoulakis, Stratis},
  title =	{{Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{50:1--50:19},
  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.50},
  URN =		{urn:nbn:de:0030-drops-124573},
  doi =		{10.4230/LIPIcs.ICALP.2020.50},
  annote =	{Keywords: PLS-completeness, Local-Max-Cut, Weighted Congestion Games, Equilibrium Computation}
}
  • Refine by Author
  • 1 Fotakis, Dimitris
  • 1 Kandiros, Vardis
  • 1 Lianeas, Thanasis
  • 1 Mouzakis, Nikos
  • 1 Patsilinakos, Panagiotis
  • Show More...

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

  • Refine by Keyword
  • 1 Equilibrium Computation
  • 1 Local-Max-Cut
  • 1 PLS-completeness
  • 1 Weighted Congestion Games

  • 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