Network congestion games with player-specific delay functions do not possess
pure Nash equilibria in general. We therefore address the computational
complexity of the corresponding decision problem and prove that it is $NP$-complete
to decide whether a pure Nash equilibrium exists. This result is
true for games with directed edges as well as for networks with undirected
edges, and still holds for games with two players only. In contrast to games
with networks of arbitrary size, we present a polynomial-time algorithm
deciding whether there exists a Nash equilibrium in games with networks of
constant size.
¶ Additionally, we introduce a family of player-specific network congestion games
that are guaranteed to possess equilibria. In these games players have identical
delay functions. However, each player may use only a certain subset of the edges.
For this class of games we prove that finding a pure Nash equilibrium is $PLS$-complete.
Again, this result is true for networks with directed edges as
well as for networks with undirected edges, and still holds for games with three
players only. In games with networks of constant size, however, we prove that
pure Nash equilibria can be computed in polynomial time.