Chen, Bo, Chen, Xujin, Hu, J. and Hu, Xiaodong (2010) Stability vs. optimality in selfish ring routing. SIAM Journal on Discrete Mathematics .

PDF WRAP_Chen_9471193-wbs-060110-submitted_version.pdf - Requires a PDF viewer. Download (396Kb)

Request Changes to record.

Abstract

We study the asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We obtain the first constant upper bound on the price of anarchy and significantly improve the existing upper bounds on the price of stability. Moreover, we show that any optimal solution is a good approximate Nash equilibrium. Finally, we present better performance analysis and fast implementation of pseudo-polynomial algorithms for computing approximate Nash equilibria.

Item Type:	Submitted Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Social Sciences > Warwick Business School
Library of Congress Subject Headings (LCSH):	Routing (Computer network management), Network analysis (Planning), Nash manifolds, Equilibrium (Economics), Game theory
Journal or Publication Title:	SIAM Journal on Discrete Mathematics
Publisher:	Society for Industrial and Applied Mathematics
ISSN:	0895-4801
Official Date:	2010
Dates:	Date Event 2010 UNSPECIFIED
Status:	Peer Reviewed
Access rights to Published version:	Open Access (Creative Commons)
Funder:	Guo jia zi ran ke xue ji jin wei yuan hui (China) [National Natural Science Foundation of China] (NSFC), Zhongguo ke xue yuan [Chinese Academy of Sciences] (CAS)
Grant number:	10531070 (NSFC), 10771209 (NSFC), 10721101 (NSFC), kjcx-yw-s7 (CAS)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads