Network Topology and Equilibrium Existence in Weighted Network Congestion Games

Igal Milchtaich ()
Additional contact information
Igal Milchtaich: Department of Economics, Bar Ilan University

No 2010-09, Working Papers from Bar-Ilan University, Department of Economics

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.

Keywords: Congestion games; network topology; existence of equilibrium (search for similar items in EconPapers)
JEL-codes: C72 (search for similar items in EconPapers)
Date: 2010-05
New Economics Papers: this item is included in nep-gth, nep-net and nep-soc
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www2.biu.ac.il/soc/ec/wp/2010-09.pdf Working paper (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:biu:wpaper:2010-09

Access Statistics for this paper

More papers in Working Papers from Bar-Ilan University, Department of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Department of Economics ().