Complexity of Equilibria in Weighted Games

Abstract

In many settings we are interested in problems that, despite being hard to solve globally, admit some local optimization heuristic that can offer locally optimal solutions. The archetypal example of this class of problems is the MaxCut problem under the flip neighborhood, where we can incrementally improve the value of the cut by flipping nodes. However, it has been shown that calculating the result of this process a priori is at least as hard as solving any other local optimization problem, i.e. it is PLS-hard.

In this thesis, we consider a variation of the above problem, named NodeMaxCut, inspired by the combinatorial structure of weighted congestion games, where the MaxCut graph is instead node-weighted rather than edge weighted. We show that, surpisingly, this problem is still PLS-hard despite its still simple structure, through an involved reduction from the canonical PLS problem CircuitFlip. Our reduction is based on and extends previous work on similar reductions. Secondly, we consider certain forms of weighted congestion games, namely series-parallel weighted congestion games with linear delay functions, as well as weighted multi-commodity congestion games with identity delay functions. The latter is obtained as an application of the PLS hardness of NodeMaxCut. Our work adds a new PLS-complete problem to the literature.