We study the class of congestion games for which the set of Nash equilibrium is equivalent to the set of strategy profiles played by greedy myopic players. We show these two coincide iff such games are played over extension-parallel graphs.

The model of congestion games is widely used to analyze games related to traffic and communication. A central property of these games is that they are potential games and hence posses a pure Nash equilibrium. In reality, it is often the case that some players cooperatively decide on their joint...