On Backward Induction Paths and Pure Strategy Nash Equilibria of Congestion Games

Igal Milchtaich

In this note, a congestion game is a noncooperative normal-form game in which the players share a common set of strategies. The payoff a player receives for playing a particular strategy depends only on the total number of players playing that strategy and decreases with that number in a manner which is specific to the particular player. The corresponding sequential move game is the perfect-information extensive-form game in which players choose their plays sequentially rather than simultaneously, and each player knows the plays of the previous players. We show that the backward induction path of this game is a pure-strategy Nash equilibrium of the simultaneous move game. We also show that, by changing the order of movers in the sequential move game, every pure-strategy Nash equilibrium of the simultaneous move game that is not Pareto dominated by another equilibrium can be obtained.

June, 1996
Published in: 
Published as: "Crowding Games are Sequentially Solvable", International Journal of Game Theory 27 (1998), 501-509