Efficient graph topologies in network routing games

Amir Epstein, Michal Feldman and Yishay Mansour

Games and Economic Behavior, 2009, vol. 66, issue 1, 115-125

Abstract: A topology is efficient for network games if, for any game over it, every Nash equilibrium is socially optimal. It is well known that many topologies are not efficient for network games. We characterize efficient topologies in network games with a finite set of players, each wishing to transmit an atomic unit of unsplittable flow. We distinguish between two classes of atomic network routing games. In network congestion games a player's cost is the sum of the costs of the edges it traverses, while in bottleneck routing games, it is its maximum edge cost. In both classes, the social cost is the maximum cost among the players' costs. We show that for symmetric network congestion games the efficient topologies are Extension Parallel networks, while for symmetric bottleneck routing games the efficient topologies are Series Parallel networks. In the asymmetric case the efficient topologies include only trees with parallel edges.

Keywords: Network; routing; games; Congestion; games; Price; of; anarchy (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00095-X
Full text for ScienceDirect subscribers only

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:eee:gamebe:v:66:y:2009:i:1:p:115-125

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().