World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SELFISH ROUTING IN THE PRESENCE OF NETWORK UNCERTAINTY

    We study the problem of selfish routing in the presence of incomplete network information. Our model consists of a number of users who wish to route their traffic on a network of m parallel links with the objective of minimizing their latency. However, in doing so, they face the challenge of lack of precise information on the capacity of the network links. This uncertainty is modeled via a set of probability distributions over all the possibilities, one for each user. The resulting model is an amalgamation of the KP-model of [14] and the congestion games with user-specific functions of [22]. We embark on a study of Nash equilibria and the price of anarchy in this new model. In particular, we propose polynomial-time algorithms (w.r.t. our model's parameters) for computing some special cases of pure Nash equilibria and we show that negative results of [22], for the non-existence of pure Nash equilibria in the case of three users, do not apply to our model. Consequently, we propose an interesting open problem, that of the existence of pure Nash equilibria in the general case of our model. Furthermore, we consider appropriate notions for the social cost and the price of anarchy and obtain upper bounds for the latter. With respect to fully mixed Nash equilibria, we show that when they exist, they are unique. Finally, we prove that the fully mixed Nash equilibrium is the worst equilibrium.

    This work is partially supported by the IST Program of the European Union under contract number IST-2005-015964 (AEOLUS). A preliminary version of this paper has appeared in IEEE IPDPS 2006.

    References

    • B. Awerbuch, Y. Azar and A. Epstein, The Price of Routing Unsplittable Flow, Proc. of the 37th ACM Symposium on Theory of Computing (2005) pp. 57–66. Google Scholar
    • G. Christodoulou and E. Koutsoupias, The Price of Anarchy of Finite Congestion Games, Proc. of the 37th ACM Symposium on Theory of Computing (2005) pp. 67–73. Google Scholar
    • A. Czumaj and B. Vöcking, ACM Transactions on Algorithms 3(1), (2007), DOI: 10.1145/1219944.1219949. Google Scholar
    • A. Fabrikant, C. H. Papadimitriou and K. Talwar, The Complexity of Pure Nash Equilibria, Proc. of the 36th ACM Symposium on Theory of Computing (2004) pp. 604–612. Google Scholar
    • R. Feldmannet al., Selfish Routing in Non-Cooperative Networks: A Survey, Proc. of the 28th International Symposium on Mathematical Foundations of Computer Science (2003) pp. 21–45. Google Scholar
    • S. Fischer and B. Vöcking, Theoretical Computer Science 378(2), 165 (2007), DOI: 10.1016/j.tcs.2007.02.019. Crossref, ISIGoogle Scholar
    • D. Fotakis, S. C. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. Theoretical Computer Science, accepted. (Preliminary version appears in ICALP 2002, pages 123-134.) . Google Scholar
    • M. Gairinget al., Theoretical Computer Science 343(2), 133 (2005), DOI: 10.1016/j.tcs.2005.05.011. Crossref, ISIGoogle Scholar
    • M. Gairing, B. Monien and K. Tiemann, Theory of Computing Systems 42(1), 91 (2008), DOI: 10.1007/s00224-007-9015-8. Crossref, ISIGoogle Scholar
    • M. Gairing, B. Monien and K. Tiemann, Routing (Un-)Splittable Flow in Games with Player-specific Linear Latency Functions, Proc. of the 33rd International Colloquium on Automata, Languages and Programming (2006) pp. 501–512. Google Scholar
    • R. L. Graham, SIAM Journal on Applied Mathematics 17, 416 (1969), DOI: 10.1137/0117039. Crossref, ISIGoogle Scholar
    • J. C. Harsanyi, Management Science 14, 159 (1967), DOI: 10.1287/mnsc.14.3.159. CrossrefGoogle Scholar
    • E. Koutsoupias, M. Mavronicolas and P. Spirakis, Theory of Computer Systems 36(6), 683 (2003), DOI: 10.1007/s00224-003-1131-5. Crossref, ISIGoogle Scholar
    • E. Koutsoupias and C. H. Papadimitriou, Worst-Case Equilibria, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (1999) pp. 404–413. Google Scholar
    • J. Lebrunet al., Knowledge-based Opportunistic Forwarding in Vehicular Wireless Ad Hoc Networks, Proceedings of the 61st IEEE International Conference on Vehicular Technology Conference (2005) pp. 2289–2293. Google Scholar
    • J. K. Lee and J. C. Hou, Modeling Steady-state and Transient Behaviors of User Mobility: Formulation, Analysis, and Application, Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (2005) pp. 85–96. Google Scholar
    • T. Lückinget al., Theoretical Computer Science 406(3), 187 (2008). Crossref, ISIGoogle Scholar
    • A. Lindgren, A. Doria and O. Schelen, Probabilistic Routing in Intermittently Connected Networks, Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (2003) pp. 85–96. Google Scholar
    • T. Lückinget al., Which is the Worst-Case Nash Equilibrium?, Proc. of the 28th International Symposium of Mathematical Foundations of Computer Science (2003) pp. 551–561. Google Scholar
    • M. Mavronicolaset al., Congestion Games with Player-Specific Constants, Proc. of the 32nd International Symposium of Mathematical Foundations of Computer Science (2007) pp. 633–644. Google Scholar
    • M. Mavronicolas and P. Spirakis, Algorithmica 48(1), 91 (2007), DOI: 10.1007/s00453-006-0056-1. Crossref, ISIGoogle Scholar
    • I. Milchtaich, Games and Economic Behavior 13(1), 111 (1996), DOI: 10.1006/game.1996.0027. Crossref, ISIGoogle Scholar
    • D. Mondener and L. S. Shapley, Games and Economic Behavior 14(1), 124 (1996). Crossref, ISIGoogle Scholar
    • J. F. Nash, Proc. of the National Academy of Sciences of the United States of America 36, 48 (1950), DOI: 10.1073/pnas.36.1.48. Crossref, ISIGoogle Scholar
    • J. F. Nash, Annals of Mathematics 54(2), 286 (1951), DOI: 10.2307/1969529. Crossref, ISIGoogle Scholar
    • R. W. Rosenthal, International Journal of Game Theory 2, 65 (1973), DOI: 10.1007/BF01737559. Crossref, ISIGoogle Scholar
    • L. Songet al., Predictability of WLAN Mobility and its Effects on Bandwidth Provisioning, Proceedings of the 25th IEEE International Conference on Computer Communications (2006) pp. 1–13. Google Scholar