Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/95995
Authors: 
Milchtaich, Igal
Year of Publication: 
2010
Series/Report no.: 
Working Papers, Bar-Ilan University, Department of Economics 2010-09
Abstract: 
Every finite noncooperative game can be presented as a weighted network congestion game, and also as a network congestion game with player-specific costs. In the first presentation, different players may contribute differently to congestion, and in the second, they are differently (negatively) affected by it. This paper shows that the topology of the underlying (undirected two-terminal) network provides information about the existence of pure-strategy Nash equilibrium in the game. For some networks, but not for others, every corresponding game has at least one such equilibrium. For the weighted presentation, a complete characterization of the networks with this property is given. The necessary and sufficient condition is that the network has at most three routes that do traverse any edge in opposite directions, or it consists of several such networks connected in series. The corresponding problem for player-specific costs remains open.
Subjects: 
congestion games
network topology
existence of equilibrium
Document Type: 
Working Paper

Files in This Item:
File
Size
931.77 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.