SELFISH ROUTING IN THE PRESENCE OF NETWORK UNCERTAINTY
Abstract
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 ScholarG. 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- 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 ScholarR. Feldmann , 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- Theoretical Computer Science 378(2), 165 (2007), DOI: 10.1016/j.tcs.2007.02.019. Crossref, ISI, Google 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
- Theoretical Computer Science 343(2), 133 (2005), DOI: 10.1016/j.tcs.2005.05.011. Crossref, ISI, Google Scholar
- Theory of Computing Systems 42(1), 91 (2008), DOI: 10.1007/s00224-007-9015-8. Crossref, ISI, Google 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- SIAM Journal on Applied Mathematics 17, 416 (1969), DOI: 10.1137/0117039. Crossref, ISI, Google Scholar
- Management Science 14, 159 (1967), DOI: 10.1287/mnsc.14.3.159. Crossref, Google Scholar
- Theory of Computer Systems 36(6), 683 (2003), DOI: 10.1007/s00224-003-1131-5. Crossref, ISI, Google 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 ScholarJ. Lebrun , 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 ScholarJ. 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- Theoretical Computer Science 406(3), 187 (2008). Crossref, ISI, Google 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 ScholarT. Lücking , Which is the Worst-Case Nash Equilibrium?, Proc. of the 28th International Symposium of Mathematical Foundations of Computer Science (2003) pp. 551–561. Google ScholarM. Mavronicolas , Congestion Games with Player-Specific Constants, Proc. of the 32nd International Symposium of Mathematical Foundations of Computer Science (2007) pp. 633–644. Google Scholar- Algorithmica 48(1), 91 (2007), DOI: 10.1007/s00453-006-0056-1. Crossref, ISI, Google Scholar
- Games and Economic Behavior 13(1), 111 (1996), DOI: 10.1006/game.1996.0027. Crossref, ISI, Google Scholar
- Games and Economic Behavior 14(1), 124 (1996). Crossref, ISI, Google Scholar
- Proc. of the National Academy of Sciences of the United States of America 36, 48 (1950), DOI: 10.1073/pnas.36.1.48. Crossref, ISI, Google Scholar
- Annals of Mathematics 54(2), 286 (1951), DOI: 10.2307/1969529. Crossref, ISI, Google Scholar
- International Journal of Game Theory 2, 65 (1973), DOI: 10.1007/BF01737559. Crossref, ISI, Google Scholar
L. Song , 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


