×

Selfish routing with incomplete information. (English) Zbl 1151.91331

Summary: In his seminal work, J. C. Harsanyi [Manage. Sci., Theory 14, 159–182 (1967; Zbl 0207.51102), 320–334 (1968; Zbl 0177.48402) and 486–502 (1968; Zbl 0177.48501)] introduced an elegant approach to study non-cooperative games with incomplete information. In our work, we use this approach to define a new selfish routing game with incomplete information that we call Bayesian routing game. Here, each of \(n\) selfish users wishes to assign its traffic to one of \(m\) parallel links. However, users do not know each other’s traffic. Following Harsanyi’s approach, we introduce, for each user, a set of possible types. In our model, each type of a user corresponds to some traffic and the players’ uncertainty about each other’s traffic is described by a probability distribution over all possible type profiles.
We present a comprehensive collection of results about our Bayesian routing game. Our main findings are as follows:
Using a potential function, we prove that every Bayesian routing game has a pure Bayesian Nash equilibrium. More precisely, we show this existence for a more general class of games that we call weighted Bayesian congestion games. For Bayesian routing games with identical links and independent type distribution, we give a polynomial time algorithm to compute a pure Bayesian Nash equilibrium.
We study structural properties of fully mixed Bayesian Nash equilibria for the case of identical links and show that they maximize Individual Cost. In general, there is more than one fully mixed Bayesian Nash equilibrium. We characterize fully mixed Bayesian Nash equilibria for the case of independent type distribution.
We conclude with bounds on Coordination Ratio for the case of identical links and for three different Social Cost measures: Expected Maximum Latency, Sum of Individual Costs and Maximum Individual Cost. For the latter two, we are able to give (asymptotically) tight bounds using the properties of fully mixed Bayesian Nash equilibria we proved.

MSC:

91A10 Noncooperative games
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 57–66 (2005) · Zbl 1192.90099
[2] Beier, R., Czumaj, A., Krysta, P., Vöcking, B.: Computing equilibria for congestion games with (im)perfect information. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 746–755 (2004) · Zbl 1318.91010
[3] Berenbrink, P., Goldberg, L.A., Goldberg, P.W., Martin, R.: Utilitarian resource assignment. J. Discret. Algorithms 4(4), 567–587 (2006) · Zbl 1124.91042 · doi:10.1016/j.jda.2005.06.009
[4] Berger, J.O.: Statistical Decision Theory and Bayesian Analysis, 2nd edn. Springer, New York (1980) · Zbl 0444.62009
[5] Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 67–73 (2005) · Zbl 1192.91039
[6] Czumaj, A., Vöcking, B.: Tight bounds for worst-case equilibria. ACM Trans. Algorithms 3(1), Article 4 (2007). Special Issue of SODA’02 · Zbl 1322.91017
[7] Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 604–612 (2004) · Zbl 1192.91042
[8] Facchini, G., van Megan, F., Borm, P., Tijs, S.: Congestion models and weighted Bayesian potential games. Theory Decis. 42, 193–206 (1997) · Zbl 0888.90165 · doi:10.1023/A:1004991825894
[9] 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.) Proceedings of the 30th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 2719, pp. 514–526. Springer, New York (2003) · Zbl 1060.68531
[10] Feldmann, R., Gairing, M., Lücking, T., Monien, B., Rode, M.: Selfish routing in non-cooperative networks: a survey. In: Rovan, B., Vojtás, P. (eds.) Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 2747, pp. 21–45. Springer, New York (2003) · Zbl 1124.68305
[11] Fischer, S., Vöcking, B.: On the structure and complexity of worst-case equilibria. In: Deng, X., Ye, Y. (eds.) Proceedings of the 1st International Workshop on Internet and Network Economics. Lecture Notes in Computer Science, vol. 3828, pp. 151–160. Springer, New York (2005)
[12] 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., Ruiz, F.T., Bueno, R.M., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) Proceedings of the 29th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 2380, pp. 123–134. Springer, New York (2002) · Zbl 1056.68028
[13] Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows. In: Diaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) Proceedings of the 31st International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 3142, pp. 593–605. Springer, New York (2004) · Zbl 1099.90512
[14] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: Nash equilibria in discrete routing games with convex latency functions. In: Diaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) Proceedings of the 31st International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 3142, pp. 645–657. Springer, New York (2004) · Zbl 1100.91003
[15] Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., Spirakis, P.: Structure and complexity of extreme Nash equilibria. Theor. Comput. Sci. 343, 133–157 (2005) · Zbl 1121.91020 · doi:10.1016/j.tcs.2005.05.011
[16] Gairing, M., Lücking, T., Monien, B., Tiemann, K.: Nash equilibria, the price of anarchy and the fully mixed Nash equilibrium conjecture. In: Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 3580, pp. 51–65. Springer, New York (2005) · Zbl 1084.91006
[17] Georgiou, C., Pavlides, T., Philippou, A.: Network uncertainty in selfish routing. In: Proc. of the 20th IEEE International Parallel & Distributed Processing Symposium, p. 105 (2006)
[18] Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416–429 (1969) · Zbl 0188.23101 · doi:10.1137/0117039
[19] Harsanyi, J.C.: Games with incomplete information played by Bayesian players, I, II, III. Manag. Sci. 14, 159–182, 320–332, 468–502 (1967) · Zbl 0207.51102
[20] Harsanyi, J.C.: Games with randomly disturbed payoffs. Int. J. Game Theory 21, 1–23 (1973) · Zbl 0255.90084 · doi:10.1007/BF01737554
[21] Koutsoupias, E., Mavronicolas, M., Spirakis, P.: Approximate equilibria and ball fusion. Theory Comput. Syst. 36(6), 683–693 (2003) · Zbl 1101.68336 · doi:10.1007/s00224-003-1131-5
[22] Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1563, pp. 404–413. Springer, New York (1999) · Zbl 1099.91501
[23] Lücking, T., Mavronicolas, M., Monien, B., Rode, M.: A new model for selfish routing. In: Diekert, V., Habib, M. (eds.) Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 2996, pp. 547–558. Springer, New York (2004) · Zbl 1122.91303
[24] Lücking, T., Mavronicolas, M., Monien, B., Rode, M., Spirakis, P., Vrto, I.: Which is the worst-case Nash equilibrium?. In: Rovan, B., Vojtás, P. (eds.) Proceedings of the 28th International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 2747, pp. 551–561. Springer, New York (2003) · Zbl 1124.68330
[25] Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, Oxford (1995)
[26] Mavronicolas, M., Spirakis, P.: The price of selfish routing. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 510–519 (2001) · Zbl 1323.91006
[27] Milchtaich, I.: Congestion games with player-specific payoff functions. Games Econ. Behav. 13(1), 111–124 (1996) · Zbl 0848.90131 · doi:10.1006/game.1996.0027
[28] Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124–143 (1996) · Zbl 0862.90137 · doi:10.1006/game.1996.0044
[29] Myerson, R.B.: Game Theory: Analysis of Conflict. Harvard University Press (1997) · Zbl 0729.90092
[30] Papadimitriou, C.H.: Algorithms, games, and the Internet. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 749–753 (2001) · Zbl 1323.68022
[31] Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[32] Voorneveld, M., Borm, P., van Megan, F., Tijs, S., Facchini, G.: Congestion games and potentials reconsidered. Int. Game Theory Rev. 1, 283–299 (1999) · Zbl 1045.91501 · doi:10.1142/S0219198999000219
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.