License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.50
URN: urn:nbn:de:0030-drops-124573
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12457/
Go to the corresponding LIPIcs Volume Portal


Fotakis, Dimitris ; Kandiros, Vardis ; Lianeas, Thanasis ; Mouzakis, Nikos ; Patsilinakos, Panagiotis ; Skoulakis, Stratis

Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games

pdf-format:
LIPIcs-ICALP-2020-50.pdf (0.8 MB)


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.

BibTeX - Entry

@InProceedings{fotakis_et_al:LIPIcs:2020:12457,
  author =	{Dimitris Fotakis and Vardis Kandiros and Thanasis Lianeas and Nikos Mouzakis and Panagiotis Patsilinakos and Stratis Skoulakis},
  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 =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12457},
  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}
}

Keywords: PLS-completeness, Local-Max-Cut, Weighted Congestion Games, Equilibrium Computation
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020


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