A relatively new research area in theoretical computer science, at the intersection of game theory and computer science, is brought to light in this paper. The problem of computing pure Nash equilibria (PNE) is discussed, and specific cases of congestion games and network congestion games are addressed. A pure Nash equilibrium is a state in a game where each player, using a pure (nonrandom) strategy, has no selfish interest in changing what she is currently doing, as it would not improve the metric.

A congestion game is one where each player is competing for resources that become more costly based on how many users are using them. A network congestion game is one in which the resources are the edges of a network, and flow is sent from one node to another in the network. It is symmetric if all users send flow from the same source to the same sink.

It is well known that all congestion games (unweighted) have a PNE. The main contribution of this paper is to prove that, while there is a (strongly) polynomial algorithm to find a PNE in a symmetric network congestion game, there are several other cases which are PLS-complete. The authors present an extremely complex reduction to prove the PLS-completeness of the asymmetric network congestion game in the appendix, which is most entertaining to follow.