Network structure and strong equilibrium in route selection games

In a route selection game on a network, every player chooses a route from the origin to the destination, which are common to all players. Costs are assigned to road segments in the form of monotone nondecreasing functions of the number of players who use them. Each player incurs a total cost equal to the sum of the costs of the road segments in his route. It is known that such a game always has a Nash equilibrium in pure strategies. Here we obtain a structural characterization of those networks for which a strong equilibrium is guaranteed to exist regardless of the cost assignment. The route selection games based on networks in this class enjoy more stability as well as other desirable properties of equilibrium regarding uniqueness and efficiency. (C) 2003 Elsevier B.V. All rights reserved.