2026-08-05T04:46:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12457 2024-03-06T10:50:11Z ddc:004 open_access

Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games Fotakis, Dimitris Kandiros, Vardis Lianeas, Thanasis Mouzakis, Nikos Patsilinakos, Panagiotis Skoulakis, Stratis PLS-completeness Local-Max-Cut Weighted Congestion Games Equilibrium Computation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dimitris Fotakis and Vardis Kandiros and Thanasis Lianeas and Nikos Mouzakis and Panagiotis Patsilinakos and Stratis Skoulakis 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.50 urn:nbn:de:0030-drops-124573 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.50 eng https://creativecommons.org/licenses/by/3.0/legalcode