Near-Optimal Network Design with Selfish Agents

by Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler

Theory of Computing, Volume 4(4), pp. 77-109, 2008

Bibliography with links to cited articles

[1] Ajit Agrawal, Philip Klein, and R. Ravi: When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440-456, 1995. [SICOMP:10.1137/S0097539792236237].
[2] Aditya Akella, Srinivasan Seshan, Richard Karp, Scott Shenker, and Christos Papadimitriou: Selfish behavior and stability of the Internet: A game-theoretic analysis of TCP. SIGCOMM Comput. Commun. Rev., 32(4):117-130, 2002. [ACM:964725.633037].
[3] Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, and Liam Roditty: On Nash equilibria for a network creation game. In Proc. 17th ACM-SIAM Symp. on Discrete Algorithms (SODA'06), pp. 89-98, New York, NY, USA, 2006. ACM. [SODA:1109557.1109568].
[4] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden: The price of stability for network design with fair cost allocation. In Proc. 45th FOCS, pp. 295-304, Washington, DC, USA, 2004. IEEE Computer Society. [FOCS:10.1109/FOCS.2004.68].
[5] Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler: Near-optimal network design with selfish agents. In Proc. 35th STOC, pp. 511-520, New York, NY, USA, 2003. ACM. [STOC:780542.780617].
[6] Baruch Awerbuch, Yossi Azar, and Amir Epstein: The price of routing unsplittable flow. In Proc. 37th STOC, pp. 57-66, New York, NY, USA, 2005. ACM. [STOC:1060590.1060599].
[7] Venkatesh Bala and Sanjeev Goyal: A noncooperative model of network formation. Econometrica, 68(5):1181-1230, September 2000. [ .html ]
[8] Moses Charikar, Chandra Chekuri, To yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li: Approximation algorithms for directed Steiner problems. In Proc. 9th ACM-SIAM Symp. on Discrete Algorithms (SODA'98), pp. 192-200, Philadelphia, PA, USA, 1998. Society for Industrial and Applied Mathematics. [SODA:314613.314700].
[9] Chandra Chekuri, Julia Chuzhoy, Liane Lewin-Eytan, Joseph (Seffi) Naor, and Ariel Orda: Non-cooperative multicast and facility location games. In Proc. 7th ACM Conference on Electronic Commerce (EC'06), pp. 72-81, New York, NY, USA, 2006. ACM. [ACM:1134707.1134716].
[10] Ho-Lin Chen and Tim Roughgarden: Network design with weighted players. In Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA'06), pp. 29-38, New York, NY, USA, 2006. ACM. [ACM:1148109.1148114].
[11] George Christodoulou and Elias Koutsoupias: The price of anarchy of finite congestion games. In Proc. 37th STOC, pp. 67-73, New York, NY, USA, 2005. ACM. [STOC:1060590.1060600].
[12] Artur Czumaj and Berthold Vöcking: Tight bounds for worst-case equilibria. ACM Trans. Algorithms, 3(1):4, 2007. [ACM:1186810.1186814, ACM:545436].
[13] Debojyoti Dutta, Ashish Goel, and John Heidemann: Oblivious AQM and Nash equilibria. SIGCOMM Comput. Commun. Rev., 32(3):20-20, 2002. [ACM:571697.571709].
[14] Amir Epstein, Michal Feldman, and Yishay Mansour: Strong equilibrium in cost sharing connection games. In Proc. 8th ACM Conference on Electronic Commerce (EC'07), pp. 84-92, New York, NY, USA, 2007. ACM. [ACM:1250910.1250924].
[15] Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, and Scott Shenker: On a network creation game. In Proc. 22nd Symp. on Principles of Distributed Computing (PODC'03), pp. 347-351, New York, NY, USA, 2003. ACM. [ACM:872035.872088].
[16] Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634-652, 1998. [JACM:285055.285059].
[17] Joan Feigenbaum, Christos H. Papadimitriou, and Scott Shenker: Sharing the cost of multicast transmissions. J. Comput. System Sci., 63(1):21-41, 2001. [JCSS:10.1006/jcss.2001.1754].
[18] Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, and Ronen Shabo: On the price of stability for designing undirected networks with fair cost allocations. In Proc. 33rd International Colloq. on Automata, Languages, and Programming (ICALP'06), volume 4051 of Lecture Notes in Computer Science, pp. 608-618. Springer, 2006. [ICALP:w045t0318v5116xl]. [ http ]
[19] Michel X. Goemans and David P. Williamson: A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296-317, 1995. [SICOMP:10.1137/S0097539793242618].
[20] H. Heller and S. Sarangi: Nash networks with heterogeneous agents. Working Paper E-2001-1, Virginia Tech, 2001. [ .pdf ]
[21] Martin Hoefer: Non-cooperative facility location and covering games. In Proc. 17th Int. Symp. on Algorithms and Computation (ISAAC'06), pp. 369-378, 2006. [ISAAC:rwk3528257852rh1].
[22] Martin Hoefer: Non-cooperative tree creation. In Proc. 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS'06), pp. 517-527, 2006. [MFCS:uu60q8258u47802v].
[23] Martin Hoefer and Piotr Krysta: Geometric network design with selfish agents. In Proc. 11th Int. Conf. on Computing and Combinatorics (COCOON'05), pp. 167-178, 2005. [Springer:2fbchhr9y2x08k8l].
[24] Kamal Jain and Vijay Vazirani: Applications of approximation algorithms to cooperative games. In Proc. 33rd STOC, pp. 364-372, New York, NY, USA, 2001. ACM. [STOC:380752.380825].
[25] E. Koutsoupias and C. Papadimitriou: Worst-case equilibria. In Proc. 16th Symp. on Theoretical Aspects of Computer Science (STACS'99), pp. 404-413, Trier, Germany, March 1999. [STACS:y37e5ne8bbafjb5r].
[26] Christos Papadimitriou: Algorithms, games, and the internet. In Proc. 33rd STOC, pp. 749-753, New York, NY, USA, 2001. ACM. [STOC:380752.380883].
[27] Gabriel Robins and Alexander Zelikovsky: Improved Steiner tree approximation in graphs. In Proc. 11th ACM-SIAM Symp. on Discrete Algorithms (SODA'00), pp. 770-779, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics. [SODA:338219.338638].
[28] R.W. Rosenthal: A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory, 2:65-67, 1973.
[29] Tim Roughgarden: Stackelberg scheduling strategies. In Proc. 33rd STOC, pp. 104-113, New York, NY, USA, 2001. ACM. [STOC:380752.380783].
[30] Tim Roughgarden: The price of anarchy is independent of the network topology. In Proc. 34th STOC, pp. 428-437, New York, NY, USA, 2002. ACM. [STOC:509907.509971].
[31] Tim Roughgarden and Éva Tardos: How bad is selfish routing? J. ACM, 49(2):236-259, 2002. [JACM:506147.506153].
[32] Andreas S. Schulz and Nicolás Stier Moses: On the performance of user equilibria in traffic networks. In Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA'03), pp. 86-87, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics. [SODA:644108.644121].
[33] Scott Shenker: Making greed work in networks: a game-theoretic analysis of gateway service disciplines. SIGMETRICS Perform. Eval. Rev., 18(1):241-242, 1990. [ACM:98460.98764].
[34] Adrian Vetta: Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In Proc. 43rd FOCS, p. 416, Washington, DC, USA, 2002. IEEE Computer Society. [FOCS:10.1109/SFCS.2002.1181966].

This file has been generated by bibtex2html 1.85.