COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS
-COMPLETE
Abstract
We determine the complexity of computing pure Nash equilibria in restricted network congestion games. Restricted network congestion games are network congestion games, where for each player there exits a set of edges which he is not allowed to use. Rosenthal's potential function guarantees the existence of a Nash Equilibrium. We show that computing a Nash equilibrium in a restricted network congestion game with two players is
-complete, using a tight reduction from MAXCUT. The result holds for directed networks and for undirected networks.
This work has been partially supported by German Research Foundation (DFG) Priority Programme 1307 Algorithm Engineering.


