English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we seek a more refined understanding of the complexity of localoptimum computation for Max-Cut and pure Nash equilibrium (PNE) computation forcongestion games with weighted players and linear latency functions. We showthat computing a PNE of linear weighted congestion games is PLS-complete eitherfor very restricted strategy spaces, namely when player strategies are paths ona series-parallel network with a single origin and destination, or for veryrestricted latency functions, namely when the latency on each resource is equalto the congestion. Our results reveal a remarkable gap regarding the complexityof PNE in congestion games with weighted and unweighted players, since in caseof unweighted players, a PNE can be easily computed by either a simple greedyalgorithm (for series-parallel networks) or any better response dynamics (whenthe 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 restrictionof Max-Cut, which we call \emph{Node-Max-Cut}, is PLS-complete. InNode-Max-Cut, the input graph is vertex-weighted and the weight of each edge isequal to the product of the weights of its endpoints. Due to the veryrestricted nature of Node-Max-Cut, the reduction requires a careful combinationof new gadgets with ideas and techniques from previous work. We also show howto compute efficiently a $(1+\eps)$-approximate equilibrium for Node-Max-Cut,if the number of different vertex weights is constant.

Node Max-Cut and Computing Equilibria in Linear Weighted Congestion Games