The price of atomic selfish ring routing

Bo Chen (), Xujin Chen () and Xiaodong Hu ()
Additional contact information
Bo Chen: University of Warwick
Xujin Chen: Chinese Academy of Sciences
Xiaodong Hu: Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2010, vol. 19, issue 3, No 2, 258-278

Abstract: Abstract We study selfish routing in ring networks with respect to minimizing the maximum latency. Our main result is an establishment of constant bounds on the price of stability (PoS) for routing unsplittable flows with linear latency. We show that the PoS is at most 6.83, which reduces to 4.57 when the linear latency functions are homogeneous. We also show the existence of a (54,1)-approximate Nash equilibrium. Additionally we address some algorithmic issues for computing an approximate Nash equilibrium.

Keywords: Selfish routing; Nash equilibrium; Price of stability (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9171-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:19:y:2010:i:3:d:10.1007_s10878-008-9171-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9171-z

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().