Stability vs. optimality in selfish ring routing

详细信息    查看全文

• 作者：Bo Chen (1)
  Xujin Chen (2)
  Jie Hu (3)
  
• 关键词：Selfish routing ; price of stability ; minimum maximum linear latency ; 68R99 ; 91A06 ; 91A10 ; 68W40
• 刊名：Acta Mathematica Sinica
• 出版年：2014
• 出版时间：May 2014
• 年：2014
• 卷：30
• 期：5
• 页码：767-784
• 全文大小：372 KB
• 参考文献：1. Ackermann, H., R枚glin, H., V枚cking, B.: On the impact of combinatorial structure on congestion games. / J. ACM, 55, Article No. 25 (2008)
  2. Anshelevich, E., Dasgupta, A., Kleinberg, J., et al.: The price of stability for network design with fair cost allocation. / SIAM J. Comput., 38, 1602鈥?623 (2008) CrossRef
  3. Anshelevich, E., Zhang, L.: Path decomposition under a new cost measure with applications to optical network design. / ACM Trans. Algorithms, 4, Article No. 15 (2008)
  4. Awerbuch, B., Azar, Y., Epstein, L.: The price of routing unsplittable flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 57鈥?6
  5. Bentza, C., Costab, M.-C., L茅tocartc, L., et al.: Multicuts and integral multiflows in rings. / European J. Oper. Res., 196, 1251鈥?254 (2009) CrossRef
  6. Blum, A., Kalai, A., Kleinberg, J.: Addmission control to minimize rejections. / Lecture Notes in Comput. Sci., 2152, 155鈥?64 (2001) CrossRef
  7. Busch, C., Magdon-Ismail, M.: Atomic routing games on maximum congestion. / Lecture Notes in Comput. Sci., 4041, 79鈥?1 (2006) CrossRef
  8. Chen, B., Chen, X., Hu, X.: The price of atomic selfish ring routing. / J. Comb. Optim., 19, 258鈥?78 (2010) CrossRef
  9. Chen, X., Doerr, B., Hu, X., et al.: The price of anarchy for selfish ring routing is two. / Lecture Notes in Comput. Sci., 7695, 421鈥?34 (2012) CrossRef
  10. Cheng, C. T.: Improved approximation algorithms for the demand routing and slotting problem with unit demands on rings. / SIAM J. Discrete Math., 17, 384鈥?02 (2004) CrossRef
  11. Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th annual ACM Symposium on Theory of Computing, 2005, pp. 67鈥?3
  12. Correa, J. R., Schulz, A. S., Stier-Moses, N. E.: Fast, fair, and efficient flows in networks. / Oper. Res., 55, 215鈥?25 (2007) CrossRef
  13. Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria in load balancing. / ACM Trans. Algorithms, 3, Article No. 32 (2007)
  14. Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th annual ACM Syposimum on Theory of Computing, 2004, pp. 604鈥?12
  15. Fotakis, D.: Congestion game with linearly independent paths: convergence time and price of anarchy. / Lecture Notes in Comput. Sci., 4997, 33鈥?5 (2008) CrossRef
  16. Fotakis, D., Kontogiannisa, S., Spirakis, P.: Selfish unsplittable flows. / Theoret. Comput. Sci., 348, 226鈥?39 (2005) CrossRef
  17. Gairing, M., L眉cking, T., Mavronicolas, M., et al.: The price of anarchy for restricted parallel links. / Parallel Process. Lett., 16, 117鈥?32 (2006) CrossRef
  18. Koutsoupias, E., Papadimitriou, C. H.: Worst-case equilibria. / Lecture Notes in Comput. Sci., 1563, 404鈥?13 (1999) CrossRef
  19. Lin, H., Roughgarden, T., Tardos, 脡., et al.: Stronger bounds on Braess鈥檚 paradox and the maximum latency of selfish routing. / SIAM J. Discrete Math., 25, 1667鈥?686 (2011) CrossRef
  20. Lin, H., Roughgarden, T., Tardos, 脡., et al.: Braess鈥檚 paradox, Fibonacci Numbers, and exponential inapproximability. / Lecture Notes in Comput. Sci., 3580, 497鈥?12 (2005) CrossRef
  21. Monderer, D., Shapley, L.: Potential games. / Games Econom. Behav., 14, 124鈥?43 (1996) CrossRef
  22. Rosenthal, R. W.: A class of games possessing pure-strategy Nash equilibira. / Internat. J. Game Theory, 2, 65鈥?7 (1973) CrossRef
  23. Roughgarden, T.: The price of anarchy is independent of the network topology. / J. Comput. System Sci., 67, 342鈥?64 (2003) CrossRef
  24. Nisan, N., Roughtgarden, T., Tardos, 脡., et al. (Eds): Algorithmic Game Theory, Cambridge University Press, Cambridge, UK, 2007
  25. Roughgarden, T., Tardos, 脡.: How bad is selfish routing? / J. ACM, 49, 236鈥?59 (2002) CrossRef
  26. Schrijver, A., Seymour, P., Winkler, P.: The ring loading problem. / SIAM J. Discrete Math., 11, 1鈥?4 (1998) CrossRef
  27. Wang, B. F.: Linear time algorithms for the ring loading problem with demand splitting. / J. Algorithms, 54, 45鈥?7 (2005) CrossRef
  28. Weitz, D.: The price of anarchy. Unpublished manuscript, 2001
  
• 作者单位：Bo Chen (1)
  Xujin Chen (2)
  Jie Hu (3)
  
  1. Warwick Business School, University of Warwick, Coventry, CV4 7AL, UK
  2. Institute of Applied Mathematics, AMSS, Chinese Academy of Sciences, Beijing, 100190, P. R. China
  3. School of Mathematics and Statistics, Wuhan University, Wuhan, 430072, P. R. China
  
• ISSN：1439-7617

文摘

We study 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 show that there exists an optimal solution that is a 9-approximate Nash equilibrium, significantly improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436.