Non-cooperative multicast and facility location games

ABSTRACT

We consider a multicast game with selfish non-cooperative players. There is a special source node and each player is interested in connecting to the source by making a routing decision that minimizes its payment. The mutual influence of the players is determined by a cost sharing mechanism, which in our case evenly splits the cost of an edge among the players using it. We consider two different models: an integral model, where each player connects to the source by choosing a single path, and a fractional model, where a player is allowed to split the flow it receives from the source between several paths. In both models we explore the overhead incurred in network cost due to the selfish behavior of the users, as well as the computational complexity of finding a Nash equilibrium.The existence of a Nash equilibrium for the integral model was previously established by the means of a potential function. We prove that finding a Nash equilibrium that minimizes the potential function is NP-hard. We focus on the price of anarchy of a Nash equilibrium resulting from the best-response dynamics of a game course, where the players join the game sequentially. For a game with n players, we establish an upper bound of O(√n log²n) on the price of anarchy, and a lower bound of Ω(log n/ log log n). For the fractional model, we prove the existence of a Nash equilibrium via a potential function and give a polynomial time algorithm for computing an equilibrium that minimizes the potential function. Finally, we consider a weighted extension of the multicast game, and prove that in the fractional model, the game always has a Nash equilibrium.

REFERENCES

• 1: Micah Adler , Dan Rubenstein, Pricing multicasting in more practical network models, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.981-990, January 06-08, 2002, San Francisco, California
• 2: A. Agarwal and M. Charikar. On the advantage of network coding for improving network throughput. Proc. of IEEE Information Theory Workshop, 2004.
• 3: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 4: J. Feigenbaum , A. Krishnamurthy , R. Sami , S. Shenker, Approximation and collusion in multicast cost sharing (extended abstract), Proceedings of the 3rd ACM conference on Electronic Commerce, p.253-255, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501190]
• 5: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 6: Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335332]
• 7: C.H. Helvig, G. Robins, and A. Zelikovsky. Improved approximation scheme for the group Steiner problem. Networks, 37(1):8--20, 2001.
• 8: Shai Herzog , Scott Shenker , Deborah Estrin, Sharing the “cost” of multicast trees: an axiomatic analysis, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.847-860, Dec. 1997 [doi>10.1109/90.650144]
• 9: R. Holzman and N. Law-Yone. Strong equilibrium in congestion games. Games and Economic Behavior, Vol. 21, pp. 85--101, 1997.
• 10: Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
• 11: Ramesh Johari , John N. Tsitsiklis, Efficiency Loss in a Network Resource Allocation Game, Mathematics of Operations Research, v.29 n.3, p.407-435, August 2004 [doi>10.1287/moor.1040.0091]
• 12: M. Imaze and B. Waxman. Dynamic steiner tree problem. SIAM J. on Discrete Mathematics, Vol. 4(3):369--384, 1991.
• 13: S. Kakutani. A generalization of Brouwer's Fixed Point Theorem. Duke Mathematical Journal, Vol. 8, 457--459, 1941.
• 14: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 15: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Proc. of STACS, LNCS, 404--413, 1999.
• 16: Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
• 17: I. Milchtaich. Congestion games with player specific payoff functions. Games and Economic Behavior, Vol. 13, 111--124, 1996.
• 18: V. Mirrokni and A. Vetta. Convergence Issues in Competitive Games. Proc. of APPROX, LNCS, 183--194, 2004.
• 19: D. Monderer and L.S. Shapley. Potential Games. Games and Economic Behavior, 14:124--143, 1996.
• 20: J. Nash. Non-cooperative games. Annals of Mathematics, 2nd Ser., Vol. 54(2), pp. 286--295, 1951.
• 21: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 22: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 23: R.W. Rosenthal. A class of games possessing pure strategy Nash equilibria. International Journal of Game Theory, Vol. 2, 65--67, 1973.
• 24: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 25: Tim Roughgarden, The price of anarchy is independent of the network topology, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509971]
• 26: L.S. Shapley. A value for n-person games. Contribution to the Theory of Games, pp. 31--40, Princeton University Press, Princeton, 1953.
• 27: Andreas S. Schulz , Nicolás Stier Moses, On the performance of user equilibria in traffic networks, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 28: M. Voorneveld, P. Borm, F. van Megen, S. Tijs and G. Faccini. Congestion games and potentials reconsidered. International Game Theory Review, Vol. 1, 283--299, 1999.
• 29: A. Zelikovsky. A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica, Vol. 18, 99--110, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Performance, Theory

Keywords:
multicast game, nash equilibrium, price of anarchy, price of stability