A new model for selfish routing
Date
2008Author
Lücking, T.Mavronicolas, Marios
Monien, Burkhard
Rode, M.
Source
Theoretical Computer ScienceVolume
406Issue
3Pages
187-206Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
In this work, we introduce and study a new, potentially rich model for selfish routing over non-cooperative networks, as an interesting hybridization of the two prevailing such models, namely the KPmodel [E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404-413] and the Wmodel [J.G. Wardrop, Some theoretical aspects of road traffic research, Proceedings of the of the Institute of Civil Engineers 1 (Pt. II) (1952) 325-378]. In the hybrid model, each of n users is using a mixed strategy to ship its unsplittable traffic over a network consisting of m parallel links. In a Nash equilibrium, no user can unilaterally improve its Expected Individual Cost. To evaluate Nash equilibria, we introduce Quadratic Social Cost as the sum of the expectations of the latencies, incurred by the squares of the accumulated traffic. This modeling is unlike the KP model, where Social Cost [E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404-413] is the expectation of the maximum latency incurred by the accumulated traffic but it is like the W model since the Quadratic Social Cost can be expressed as a weighted sum of Expected Individual Costs. We use the Quadratic Social Cost to define Quadratic Coordination Ratio. Here are our main findings: •Quadratic Social Cost can be computed in polynomial time. This is unlike the # P-completeness [D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, P. Spirakis, The structure and complexity of Nash equilibria for a selfish routing game, in: P. Widmayer, F. Triguero, R. Morales, M. Hennessy, S. Eidenbenz, R. Conejo (Eds.), Proceedings of the 29th International Colloquium on Automata, Languages and Programming, in: Lecture Notes in Computer Science, vol. 2380, Springer-Verlag, 2002, pp. 123-134] of computing Social Cost for the KP model.•For the case of identical users and identical links, the fully mixed Nash equilibrium [M. Mavronicolas, P. Spirakis, The price of selfish routing, Algorithmica 48 (1) (2007) 91-126], where each user assigns positive probability to every link, maximizes Quadratic Social Cost.•As our main result, we present a comprehensive collection of tight, constant (that is, independent of m and n), strictly less than 2, lower and upper bounds on the Quadratic Coordination Ratio for several, interesting special cases. Some of the bounds stand in contrast to corresponding super-constant bounds on the Coordination Ratio previously shown in [A. Czumaj, B. Vöcking, Tight bounds for worst-case equilibria, ACM Transactions on Algorithms 3 (1) (2007) E. Koutsoupias, M. Mavronicolas, P. Spirakis, Approximate equilibria and ball fusion, Theory of Computing Systems 36 (6) (2003) 683-693 E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: G. Meinel, S. Tison (Eds.), Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, in: Lecture Notes in Computer Science, vol. 1563, Springer-Verlag, 1999, pp. 404-413 M. Mavronicolas, P. Spirakis, The price of selfish routing, Algorithmica 48 (1) (2007) 91-126] for the KP model. © 2008 Elsevier B.V. All rights reserved.
Collections
Cite as
Related items
Showing items related by title, author, creator and subject.
-
Conference Object
Mobile commerce: Vision and challenges (location and its management)
Samaras, George S. (Institute of Electrical and Electronics Engineers Inc., 2002)Mobile computing is distributed computing that involves elements whose location changes in the course of computation. Elements may be software components such as mobile agents or moving objects-data or hardware such as ...
-
Article
Computer-aided diagnosis in hysteroscopic imaging
Neofytou, Marios S.; Tanos, Vasilios; Constantinou, Ioannis P.; Kyriacou, Efthyvoulos C.; Pattichis, Marios S.; Pattichis, Constantinos S. (2015)The paper presents the development of a computeraided diagnostic (CAD) system for the early detection of endometrial cancer. The proposed CAD system supports reproducibility through texture feature standardization, ...
-
Article
Grid Computing : Second European AcrossGrids Conference, AxGrids 2004, Nicosia, Cyprus, January 28-30, 2004. Revised Papers
European Across, Grids Conference; Dikaiakos, Marios D.; European Across, Grids Conference; Dikaiakos, Marios D.; SpringerLink (Online service); European Across, Grids Conference (2004)