Network games

ABSTRACT

Network games approach some of the traditional algorithmic questions in networks from the perspective of game theory, which gives rise of a wide range of interesting issues. In this talk we will give an overview of recent progress in many of these areas, and show strong ties to certain algorithmic techniques.

REFERENCES

• 1: Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780617]
• 2: E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. Price of Stability for Network Design with Fair Allocation of Costs. Unpublished manuscript, 2004.
• 3: Aaron Archer , Éva Tardos, Frugal path mechanisms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.991-999, January 06-08, 2002, San Francisco, California
• 4: Artur Czumaj , Piotr Krysta , Berthold Vöcking, Selfish traffic allocation for server farms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509952]
• 5: José R. Correa , Andreas S. Schulz , Nicolás E. Stier-Moses, Selfish Routing in Capacitated Networks, Mathematics of Operations Research, v.29 n.4, p.961-976, November 2004 [doi>10.1287/moor.1040.0098]
• 6: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 7: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 8: N. Devanur, N. Garg, R. Khandekar, V. Pandit, A. Saberi, and V. Vazirani. Price of anarchy, locality gap, and a network service provider game. Unpublished manuscript, 2004.
• 9: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 10: Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872088]
• 11: 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]
• 12: Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
• 13: Joan Feigenbaum , Christos Papadimitriou , Rahul Sami , Scott Shenker, A BGP-based mechanism for lowest-cost routing, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571856]
• 14: E. Friedman. Genericity and Congestion Control in Selfish Routing. Unpublished manuscript, 2003.
• 15: E. Friedman, A. Greenwald and S. Shenker. Learning in Network Context: Experimental Results from Simulations. Games and Economic Behavior, 35:80--123, 2001.
• 16: E. Friedman, M. Shor, S. Shenker, and B. Sopher. Experiment on Learning with Limited Information: Non-convergence, Experimentational Cascades, and the Advantage of Being Slow. To appear in Games and Economic Behavior.
• 17: J. Hershberger , S. Suri, Vickrey Prices and Shortest Paths: What is an Edge Worth?, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.252, October 14-17, 2001
• 18: 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]
• 19: 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]
• 20: 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]
• 21: R. Johari and J. Tsitsiklis. Routing and Peering in a Competitive Internet. Unpublished manuscript, 2004.
• 22: Rahul Garg , Sanjiv Kapoor, Auction algorithms for market equilibrium, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007430]
• 23: F. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunications, volume 8 (1997) pages 33--37.
• 24: K. Kent and D. Skorin-Kapov. Population monoton cost allocation on mst's. In Operations Research Proceedings KOI, pages 43--48, 1996.
• 25: E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In STACS, 404--413, 1999.
• 26: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 27: 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]
• 28: L. Qui, Y. R. Yang, Y. Zhang, S. Shenker. On Selfish Routing in Interner-Like Environments. In SIGCOMM, 2003.
• 29: Tim Roughgarden, The price of anarchy is independent of the network topology, Journal of Computer and System Sciences, v.67 n.2, p.341-364, September 2003 [doi>10.1016/S0022-0000(03)00044-8]
• 30: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 31: 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]
• 32: Subhash Suri , Csaba D. Tóth , Yunhong Zhou, Selfish load balancing and atomic congestion games, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007941]
• 33: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002