文章基本信息

标题：Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games
本地全文：下载
作者：Dimitris Fotakis ; Vardis Kandiros ; Thanasis Lianeas 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：50:1-50:19
DOI：10.4230/LIPIcs.ICALP.2020.50
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：PLS-completeness; Local-Max-Cut; Weighted Congestion Games; Equilibrium Computation