Abstract
In this work, we introduce and study a new model for selfish routing over non-cooperative networks that combines features from the two such best studied models, namely the KP model and the Wardrop model in an interesting way.
We consider a set of nusers, each using a mixed strategy to ship its unsplittable traffic over a network consisting of m parallel links. In a Nash equilibrium, no user can increase its Individual Cost by unilaterally deviating from its strategy. To evaluate the performance of such Nash equilibria, we introduce Quadratic Social Cost as a certain sum of Individual Costs – namely, the sum of the expectations of the squares of the incurred link latencies. This definition is unlike the KP model, where Maximum Social Cost has been defined as the maximum of Individual Costs.
We analyse the impact of our modeling assumptions on the computation of Quadratic Social Cost, on the structure of worst-case Nash equilibria, and on bounds on the Quadratic Coordination Ratio.
This work has been partially supported by the IST Program of the European Union under contract numbers IST-1999-14186 (ALCOM-FT) and IST-2001-33116 (FLAGS), and by research funds at University of Cyprus.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation Schemes for Scheduling. In: Proc. of SODA 1997, pp. 493–500 (1997)
Anshelevich, E., Dasgupta, A., Tardos, É., Wexler, T.: Near-Optimal Network Design with Selfish Agents. In: Proc. of STOC 2003, pp. 511–520 (2003)
Beckmann, M.J.: On the Theory of Traffic Flow in Networks. Traffic Quart. 21, 109–116 (1967)
Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
Braess, D.: Über ein Paradoxen aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)
Chandra, A.K., Wong, C.K.: Worst-case Analysis of a Placement Algorithm Related to Storage Allocation. SICOMP 4, 249–263 (1975)
Altman, E., Basar, T., Jimenez, T., Shimkin, N.: Competitive Routing in Networks with Polynomial Costs. IEEE Transactions on Automatic Control 47, 92–96 (2002)
Cody, R.A., Coffman Jr., E.G.: Record Allocation for Minimizing Expected Retrieval Costs on Crum-Like Storage Devices. JACM 23, 103–115 (1976)
Czumaj, A., Vöcking, B.: Tight Bounds for Worst-Case Equilibria. In: Proc. of SODA 2002, pp. 413–420 (2002)
Czumaj, A., Krysta, P., Vöcking, B.: Selfish Traffic Allocation for Server Farms. In: Proc. of STOC 2002, pp. 287–296 (2002)
Dafermos, S.C., Sparrow, F.T.: The Traffic Assignment Problem for a General Network. Journal of Research of the National Bureau of Standards, Series B 73B, 91–118 (1969)
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence Time to Nash Equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003)
Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a Network Creation Game. In: Proc. of PODC 2003, pp. 347–351 (2003)
Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Nashification and the Coordination Ratio for a Selfish Routing Game. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 514–526. Springer, Heidelberg (2003)
Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Selfish Routing in Non-Cooperative Networks: A Survey. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 21–45. Springer, Heidelberg (2003)
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 123–134. Springer, Heidelberg (2002)
Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Spirakis, P.: The Structure and Complexity of Extreme Nash Equilibria (2003) (submitted for publication)
Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate Equilibria and Ball Fusion. In: Proc. of SIROCCO 2002, pp. 223–235 (2002)
Koutsoupias, E., Papadimitriou, C.H.: Worst-case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Leung, J.Y.T., Wei, W.D.: Tighter Bounds on a Heuristic for a Partition Problem. Information Processing Letters 56, 51–57 (1995)
Lücking, T., Mavronicolas, M., Monien, B., Rode, M., Spirakis, P., Vrto, I.: Which is the Worst-case Nash equilibrium? In: Rovan, B., Vojtas, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 551–561. Springer, Heidelberg (2003)
Mavronicolas, M., Spirakis, P.: The Price of Selfish Routing. In: Proc. of STOC 2001, pp. 510–519 (2001)
Nash, J.F.: Equilibrium Points in N-Person Games. Proceedings of the National Academy of Sciences 36, 48–49 (1950)
Nash, J.F.: Non-cooperative Games. Annals of Mathematics 54(2), 286–295 (1951)
Osborne, M.J., Rubinstein, A.: A Course in Game Theory. The MIT Press, Cambridge (1994)
Papadimitriou, C.H.: Algorithms, Games and the Internet. In: Proc. of STOC 2001, pp. 749–753 (2001)
Roughgarden, T.: The Price of Anarchy is Independent of the Network Topology. In: Proc. of STOC 2002, pp. 428–437 (2002)
Roughgarden, T.: Selfish Routing, Ph. D. Thesis, Department of Computer Science, Cornell University (May 2002)
Roughgarden, T., Tardos, É.: How Bad is Selfish Routing? JACM 49, 236–259 (2002)
Wardrop, J.G.: Some Theoretical Aspects of Road Traffic Research. In: Proceedings of the of the Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lücking, T., Mavronicolas, M., Monien, B., Rode, M. (2004). A New Model for Selfish Routing. In: Diekert, V., Habib, M. (eds) STACS 2004. STACS 2004. Lecture Notes in Computer Science, vol 2996. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24749-4_48
Download citation
DOI: https://doi.org/10.1007/978-3-540-24749-4_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21236-2
Online ISBN: 978-3-540-24749-4
eBook Packages: Springer Book Archive