×

When ignorance helps: Graphical multicast cost sharing games. (English) Zbl 1173.91322

Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 108-119 (2008).
Summary: In non-cooperative games played on highly decentralized networks the assumption that each player knows the strategy adopted by any other player may be too optimistic or even unfeasible. In such situations, the set of players of which each player knows the chosen strategy can be modeled by means of a social knowledge graph in which nodes represent players and there is an edge from \(i\) to \(j\) if \(i\) knows \(j\). Following the framework introduced in [V. Bilò, A. Fanelli, M. Flammini and L. Moscardelli, “Graphical congestion games with linear latencies”, in: Proc. of the 20th annual symposium on parallelism in algorithms and architectures, 194–196 (2008)], we study the impact of social knowledge graphs on the fundamental multicast cost sharing game in which all the players want to receive the same communication from a given source. Such a game in the classical complete information case is known to be highly inefficient, since its price of anarchy can be as high as the total number of players \(\rho \). We first show that, under our incomplete information setting, pure Nash equilibria always exist only if the social knowledge graph is directed acyclic (DAG). We then prove that the price of stability of any DAG is at least \(\frac 1 2\log\rho\) and provide a DAG lowering the classical price of anarchy to a value between \(\frac 1 2\log\rho\) and \(\log ^{2} \rho \). If specific instances of the game are concerned, that is if the social knowledge graph can be selected as a function of the instance, we show that the price of stability is at least \(\frac{4\rho}{\rho+3}\), and that the same bound holds also for the price of anarchy of any social knowledge graph (not only DAGs). Moreover, we provide a nearly matching upper bound by proving that, for any fixed instance, there always exists a DAG yielding a price of anarchy less than 4. Our results open a new window on how the performances of non-cooperative systems may benefit from the lack of total knowledge among players and can be considered, in some sense, as another evidence of the famous Braess paradox.
For the entire collection see [Zbl 1154.68021].

MSC:

91A43 Games involving graphs
91A10 Noncooperative games
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anshelevich, E.; Dasgupta, A.; Kleinberg, J.; Tardos, E.; Wexler, T.; Roughgarden, T., The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 295-304 (2004), Los Alamitos: IEEE Computer Society, Los Alamitos · doi:10.1109/FOCS.2004.68
[2] Anshelevich, E.; Dasgupta, A.; Tardos, E.; Wexler, T., Near-Optimal Network Design with Selfish Agents, Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), 511-520 (2003), New York: ACM, New York · Zbl 1192.68019
[3] Bilò, V.; Fanelli, A.; Flammini, M.; Moscardelli, L., Graphical Congestion Games with Linear Latencies, Proceedings of the 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2008), New York: ACM, New York
[4] Braess, D., Uber ein Paradoxon der Verkehrsplanung, Unternehmensforschung, 12, 258-268 (1968) · Zbl 0167.48305 · doi:10.1007/BF01918335
[5] Chekuri, C.; Chuzhoy, J.; Lewin-Eytan, L.; Naor, J.; Orda, A., Non-Cooperative Multicast and Facility Location Games, Proceedings of the 7th ACM Conference on Electronic Commerce (EC), 72-81 (2006), New York: ACM, New York · doi:10.1145/1134707.1134716
[6] Charikar, M., Mattieu, C., Karloff, H., Naor, J., Saks, M.: Best Response Dynamics in Multicast Cost Sharing. Personal communication
[7] Czumaj, A., Selfish Routing on the Internet (2004), Boca Raton: CRC Press, Boca Raton
[8] Fanelli, A.; Flammini, M.; Melideo, G.; Moscardelli, L.; Královič, R.; Urzyczyn, P., Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves, Mathematical Foundations of Computer Science 2006, 363-374 (2006), Heidelberg: Springer, Heidelberg · Zbl 1132.68305 · doi:10.1007/11821069_32
[9] Karakostas, G.; Kim, T.; Viglas, A.; Xia, H.; Prencipe, G.; Zaks, S., Selfish Routing with Oblivious Users, Proceedings of the 14th Colloquium on Structural Information and Communication Complexity (SIROCCO), 318-327 (2007), Heidelberg: Springer, Heidelberg · Zbl 1201.68018 · doi:10.1007/978-3-540-72951-8_25
[10] Kearns, M. J.; Littman, M. L.; Singh, S. P., Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (UAI), 253-260 (2001), San Francisco: Morgan Kaufmann, San Francisco
[11] Koutsoupias, E.; Papadimitriou, C.; Meinel, C.; Tison, S., Worst-Case Equilibria, Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS), 404-413 (1999), Heidelberg: Springer, Heidelberg · Zbl 1099.91501
[12] Rosenthal, R. W., A Class of Games Possessing Pure-Strategy Nash Equilibria, International Journal of Game Theory, 2, 65-67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[13] Roughgarden, T.: Selfish Routing and the Price of Anarchy (Survey). OPTIMA 74 (2007)
[14] Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, V. V., Algorithmic Game Theory (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1130.91005
[15] Shapley, L. S., The value of n-person games, Contributions to the theory of games, 31-40 (1953), Princeton: Princeton University Press, Princeton
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.