×

Worst-case Nash equilibria in restricted routing. (English) Zbl 1280.68056

Summary: 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.

MSC:

68M10 Network design and communication in computer systems
91A43 Games involving graphs
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Koutsoupias E, Papadimitriou C H. Worst-case equilibria. In Proc. the 16th STACS, February 1999, pp.404–413. · Zbl 1099.91501
[2] Czumaj A, Vöcking B. Tight bounds for worst-case equilibria. In Proc. the 13th SODA, January 2002, pp.413–420. · Zbl 1092.91508
[3] Awerbuch B, Azar Y, Richter Y et al. Tradeoffs in worst-case equilibria. Theor. Comput. Sci., 2006, 361(2): 200–209. · Zbl 1097.68012 · doi:10.1016/j.tcs.2006.05.010
[4] Gairing M, Lucking T, Mavronicolas M, Monien B. The price of anarchy for restricted parallel links. Parallel Processing Letters, 2006, 16(1): 117–132. · Zbl 05153294 · doi:10.1142/S0129626406002514
[5] Christodoulou G, Koutsoupias E, Nanavati A. Coordination mechanisms. Theor. Comput. Sci., 2009, 410(36): 3327–3336. · Zbl 1177.91016 · doi:10.1016/j.tcs.2009.01.005
[6] Azar Y, Jain K, Mirrokni V. (Almost) optimal coordination mechanisms for unrelated machine scheduling. In Proc. the 19th SODA, January 2008, pp.323–332. · Zbl 1192.90060
[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? In Proc. the 41st FOCS, November 2000, pp.93–102. · Zbl 1323.90011
[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 the network topology. In Proc. the 34th STOC, May 2002, pp.428–437. · Zbl 1192.68054
[11] Roughgarden T, Tardos É. Bounding the inefficiency of equilibria in nonatomic congestion games. Technical Report TR 2002–1866, Cornell University, 2002. · Zbl 1068.91002
[12] Schulz A S, Moses N S. On the performance of user equilibria in traffic networks. In Proc. the 43th SODA, January 2003, pp.86–87. · Zbl 1094.90512
[13] ImmorlicaN, Li L, Mirrokni V, Schulz A. Coordinationmechanisms for selfish scheduling. In Proc. WINE, December 2005, pp.55–69.
[14] Finn G, Horowitz E. A linear time approximation algorithm for multiprocessor scheduling. BIT Numerical Mathematics, 1979, 19(3): 312–320. · Zbl 0413.68038 · doi:10.1007/BF01930985
[15] Vredeveld T. Combinatorial approximation algorithms: Guaranteed versus experimental performance [Ph.D. Thesis]. Department of Mathematics and Computer Science, Eindhoven University of Technology, 2002. · Zbl 1140.90310
[16] Aspnes J, Azar Y, Fiat A, Plotkin S, Waarts O. On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM, 1997, 44(3): 486–504. · Zbl 0890.68014 · doi:10.1145/258128.258201
[17] Azar Y, Naor J, Rom R. The competitiveness of on-line assignments. Journal of Algorithms, 1995, 18(2): 221–237. · Zbl 0818.68026 · doi:10.1006/jagm.1995.1008
[18] Gairing M, Lucking T, Mavronicolas M, Monien B. Computing Nash equilibria for scheduling on restricted parallel links. In Proc. the 36th STOC, June 2004, pp.613–622. · Zbl 1192.90072
[19] Fotakis D, Kontogiannis S, Koutsoupias E, Mavronicolas M, Spirakis P. The structure and complexity of Nash equilibria for a selfish routing game. In Proc. the 29th ICALP, July 2002, pp.123–134. · Zbl 1056.68028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.