Identifying classes of games where Nash equilibrium is tractable is an important open problem (e.g. [1]}).
Congestion games [2]} are arguably the most important class of games for computer scientists, capturing useful applications like resource sharing and routing in networks.
They play a fundamental role in Algorithmic Game Theory since the inception of the field two decades ago.
In particular, a celebratedIncluding well-deserved citations for prizes named after Godel, Tucker, von Neumann (twice), and Kalai. research program on Price of Anarchy has focused on characterizing the outcomes of these games at equilibrium.
But an important question remains about this modeling assumption:
