Chen, Bo, Dr., Chen, Xujin, Hu, J. (Jie) and Hu, Xiaodong, 1962- (2010) Stability vs. optimality in selfish ring routing. SIAM Journal on Discrete Mathematics . ISSN 0895-4801

PDF WRAP_Chen_9471193-wbs-060110-submitted_version.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (396Kb)

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
Date:	2010
Status:	Peer Reviewed
Access rights to Published version:	Open Access
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)
References:	[1] H. Ackermann, H. R¨oglin, and B. V¨ocking, On the impact of combinatorial structure on congestion games, Proceedings of the 47th Foundations of Computer Science, 2006, 613–622. [2] E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden, The price of stability for network design with fair cost allocation, Proceedings of the 45th annual Symposium on Foundations of Computer Science, 2004, 295–304. [3] E. Anshelevich and L. Zhang, Path decomposition under a new cost measure with applications to optical network design, ACM Transactions on Algorithms, 4 (2008), Artical No. 15. [4] B. Awerbuch, Y. Azar, and L. Epstein, The price of routing unsplittable flow, Proceedings of the 37th annual ACM Symposium on Theory of Computing, 2005, 57–66. [5] C. Bentza, M-.C. Costab, L. L´etocartc, and F. Roupin, Multicuts and integral multiflows in rings, European Journal of Operational Research, 196 (2009) 1251–1254. [6] A. Blum, A. Kalai, and J. Kleinberg, Addmission control to minimize rejections, Lecture Notes in Computer Science, 2152 (2001) 155–164. [7] C. Busch and M. Magdon-Ismail, Atomic routing games on maximum congestion, Lecture Notes in Computer Science, 4041 (2006) 79–91. [8] C.T. Cheng, Improved approximation algorithms for the demand routing and slotting problem with unit Demands on rings, SIAM Journal on Discrete Mathematics, 17 (2004) 384–402. [9] B. Chen, X. Chen, and X. Hu, The price of atomic selfish ring routing, Journal of Comminatorial Optimization, 2008. doi: 10/1007/s10878-008-9171-z. [10] G. Christodoulou and E. Koutsoupias, The price of anarchy of finite congestion games, Proceedings of the 37th annual ACM Symposium on Theory of Computing, 2005, 67–73. [11] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill, 2001. [12] J.R. Correa, A.S. Schulz, and N.E. Stier-Moses, Fast, fair, and efficient flows in networks, Oprerations Research, 55 (2007) 215–225. [13] E. Even-Dar, A. Kesselman, and Y. Mansour, Convergence time to nash equilibria in load balancing, ACM Transactions on Algorithms, 3 (2007), Artical No. 32. [14] A. Fabrikant, C. Papadimitriou, and K. Talwar, The complexity of pure Nash equilibria, Proceedings of the 36th annual ACM Syposimum on Theory of Computing, 2004, 604–612. [15] D. Fotakis, Congestin game with linearly independent paths: convergence time and price of anarchy, Lecture Notes in Computer Science, 4997 (2008) 33–45. [16] D. Fotakis, S. Kontogiannisa, and P. Spirakis, Selfish unsplittable flows, Theoretical Computer Sci- ences, 348 (2005) 226–239. [17] E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, Lecture Notes in Computer Science, 1563 (1999) 404–413. [18] D. Monderer and L. Shapley, Potential games, Game and Economic Behavior, 14 (1996) 124–143. [19] N. Nisan, T. Roughtgarden, E. Tardos, and V.V. Vazirani (Eds), Algorithmic Game Theory, Cambridge University Press, Cambridge, UK, 2007. [20] H. Lin, T. Roughgarden, E. Tardos, and A. Walkover, Braess’s paradox, Fibonacci Numbers, and exponential inapproximability, Lecture Notes in Computer Science, 3580 2005, 497–512. [21] R.W. Rosenthal, A class of games possessing pure-strategy Nash equilibira, International Jouranl of Game Theory, 2 (1973) 65–67. [22] T. Roughgarden, The price of anarchy is independent of the network topology, Jouranl of Computer and System Sciences, 67 (2003) 342–364. [23] T. Roughgarden and E. Tardos, How bad is selfish routing? Journal of the ACM, 49 (2002) 236–259. [24] A. Schrijver, P. Seymour, and P. Winkler, The ring loading problem SIAM Journal on Discrete Mathematics, 11 (1998) 1–14. [25] B. F Wang, Linear time algorithms for the ring loading problem with demand splitting, Journal of Algorithms, 54 (2005) 45-57.
URI:	http://wrap.warwick.ac.uk/id/eprint/2535

Request changes to a record

Actions (login required)

View Item