We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 27 Issue 4
July  2012
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Pin-Yan Lu, Chang-Yuan Yu. Worst-Case Nash Equilibria in Restricted Routing[J]. Journal of Computer Science and Technology, 2012, 27(4): 710-717. DOI: 10.1007/s11390-012-1257-5
Citation: Pin-Yan Lu, Chang-Yuan Yu. Worst-Case Nash Equilibria in Restricted Routing[J]. Journal of Computer Science and Technology, 2012, 27(4): 710-717. DOI: 10.1007/s11390-012-1257-5
shu

Worst-Case Nash Equilibria in Restricted Routing

  • 1. Microsoft Research Asia, Beijing 100080, China;
    2. Baidu. Inc, Beijing 100085, China

More Information
  • Received Date: March 06, 2011
  • Revised Date: January 14, 2012
  • Published Date: July 04, 2012
    Abstract
  • We study the network routing problem with restricted and related links. There are parallel links with possibly different speeds, between a source and a sink. Also there are users, and each user has a traffic of some weight to assign to one of the links from a subset of all the links, named his/her allowable set. The users choosing the same link suffer the same delay, which is equal to the total weight assigned to that link over its speed. A state of the system is called a Nash equilibrium if no user can decrease his/her delay by unilaterally changing his/her link. To measure the performance degradation of the system due to the selfish behavior of all the users, Koutsoupias and Papadimitriou proposed the notion Price of Anarchy (denoted by PoA), which is the ratio of the maximum delay in the worst-case Nash equilibrium and in an optimal solution. The PoA for this restricted related model has been studied, and a linear lower bound was obtained. However in their bad instance, some users can only use extremely slow links. This is a little artificial and unlikely to appear in a real world. So in order to better understand this model, we introduce a parameter for the system, and prove a better Price of Anarchy in terms of the parameter. We also show an important application of our result in coordination mechanism design for task scheduling game. We propose a new coordination mechanism, Group-Makespan, for unrelated selfish task scheduling game with improved price of anarchy.
    • FullText(HTML)
    • References (19)
  • [1]
    Koutsoupias E, Papadimitriou C H. Worst-case equilibria. InProc. the 16th STACS, February 1999, pp.404-413.
    [2]
    Czumaj A, Vöcking B. Tight bounds for worst-case equilibria.In Proc. the 13th SODA, January 2002, pp.413-420.
    [3]
    Awerbuch B, Azar Y, Richter Y et al. Tradeoffs in worst-caseequilibria. Theor. Comput. Sci., 2006, 361(2): 200-209.
    [4]
    Gairing M, Lucking T, Mavronicolas M, Monien B. The priceof anarchy for restricted parallel links. Parallel ProcessingLetters, 2006, 16(1): 117-132.
    [5]
    Christodoulou G, Koutsoupias E, Nanavati A. Coordinationmechanisms. Theor. Comput. Sci., 2009, 410(36): 3327-3336.
    [6]
    Azar Y, Jain K, Mirrokni V. (Almost) optimal coordinationmechanisms for unrelated machine scheduling. In Proc. the19th SODA, January 2008, pp.323-332.
    [7]
    Wardrop J G. Some theoretical aspects of road traffic research.Proc. Inst. Civil Engineers, 1952, Pt. II, 1: 325-378.
    [8]
    Roughgarden T, Tardos 碋. How bad is selfish routing? InProc. the 41st FOCS, November 2000, pp.93-102.
    [9]
    Roughgarden T, Stackelberg scheduling strategies. In Proc.the 33rd STOC, July 2001, pp.104-113.
    [10]
    Roughgarden T. The price of anarchy is independent of thenetwork topology. In Proc. the 34th STOC, May 2002,pp.428-437.
    [11]
    Roughgarden T, Tardos 碋. Bounding the inefficiency of equilibriain nonatomic congestion games. Technical Report TR2002-1866, Cornell University, 2002.
    [12]
    Schulz A S, Moses N S. On the performance of user equilibriain traffic networks. In Proc. the 43th SODA, January 2003,pp.86-87.
    [13]
    ImmorlicaN, Li L, Mirrokni V, Schulz A. Coordinationmechanismsfor selfish scheduling. In Proc. WINE, December2005, pp.55-69.
    [14]
    Finn G, Horowitz E. A linear time approximation algorithmfor multiprocessor scheduling. BIT Numerical Mathematics,1979, 19(3): 312-320.
    [15]
    Vredeveld T. Combinatorial approximation algorithms: Guaranteedversus experimental performance [Ph.D. Thesis]. Departmentof Mathematics and Computer Science, EindhovenUniversity of Technology, 2002.
    [16]
    Aspnes J, Azar Y, Fiat A, Plotkin S, Waarts O. On-line routingof virtual circuits with applications to load balancing andmachine scheduling. J. ACM, 1997, 44(3): 486-504.
    [17]
    Azar Y, Naor J, Rom R. The competitiveness of on-line assignments.Journal of Algorithms, 1995, 18(2): 221-237.
    [18]
    Gairing M, Lucking T, Mavronicolas M, Monien B. ComputingNash equilibria for scheduling on restricted parallel links.In Proc. the 36th STOC, June 2004, pp.613-622.
    [19]
    Fotakis D, Kontogiannis S, Koutsoupias E, Mavronicolas M,Spirakis P. The structure and complexity of Nash equilibriafor a selfish routing game. In Proc. the 29th ICALP, July2002, pp.123-134.
    • Relative Articles

  • Related Articles

    [1]Bo Yi, Xing-Wei Wang, Min Huang, Qiang He. A QoS Based Reliable Routing Mechanism for Service Customization[J]. Journal of Computer Science and Technology, 2022, 37(6): 1492-1508. DOI: 10.1007/s11390-021-0686-4
    [2]Jiang Rong, Tao Qin, Bo An. Competitive Cloud Pricing for Long-Term Revenue Maximization[J]. Journal of Computer Science and Technology, 2019, 34(3): 645-656. DOI: 10.1007/s11390-019-1933-9
    [3]Jason Cong, Henry Duwe, Rakesh Kumar, Sen Li. Better-Than-Worst-Case Design：Progress and Opportunities[J]. Journal of Computer Science and Technology, 2014, 29(4): 656-663. DOI: 10.1007/s11390-014-1457-2
    [4]Yong Wu, Arun Kumar. A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing[J]. Journal of Computer Science and Technology, 2012, 27(4): 744-753. DOI: 10.1007/s11390-012-1260-x
    [5]Yi Wu. Pricing Loss Leaders Can be Hard[J]. Journal of Computer Science and Technology, 2012, 27(4): 718-726. DOI: 10.1007/s11390-012-1258-4
    [6]Ming-Jun Xiao, Liu-Sheng Huang, Qun-Feng Dong, An Liu, Zhen-Guo Yang. Leapfrog: Optimal Opportunistic Routing in Probabilistically Contacted Delay Tolerant Networks[J]. Journal of Computer Science and Technology, 2009, 24(5): 975-986.
    [7]Jie Wu, Shu-Hui Yang. Small World Model-Based Polylogarithmic Routing Using Mobile Nodes[J]. Journal of Computer Science and Technology, 2008, 23(3): 327-342.
    [8]Yi-Ci Cai, Bin Liu, Yan Xiong, Qiang Zhou, Xian-Long Hong. Priority-Based Routing Resource Assignment Considering Crosstalk[J]. Journal of Computer Science and Technology, 2006, 21(6): 913-921.
    [9]Hui Tian, Hong Shen, Teruo Matsuzawa. Random Walk Routing in WSNs with Regular Topologies[J]. Journal of Computer Science and Technology, 2006, 21(4): 496-502.
    [10]Hai-Long Yao, Yi-Ci Cai, Qiang Zhou, Xian-Long Hong. Crosstalk-Aware Routing Resource Assignment[J]. Journal of Computer Science and Technology, 2005, 20(2).
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (36) PDF downloads (1258) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return