On nash equilibria for a network creation game

ABSTRACT

We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of α per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players.Fabrikant et al. conjectured that there exists a constant A such that, for any α > A, all non-transient Nash equilibria graphs are trees. They showed that if a Nash equilibrium is a tree, the price of anarchy is constant. In this paper we disprove the tree conjecture. More precisely, we show that for any positive integer n0, there exists a graph built by n ≥ n0 players which contains cycles and forms a non-transient Nash equilibrium, for any α with 1 < α ≤ √n/2. Our construction makes use of some interesting results on finite affine planes. On the other hand we show that, for α ≥ 12n[log n], every Nash equilibrium forms a tree.Without relying on the tree conjecture, Fabrikant et al. proved an upper bound on the price of anarchy of O(√α), where α ∈ [2, n²]. We improve this bound. Specifically, we derive a constant upper bound for α ∈ O(√n) and for α ≥ 12n[log n]. For the intermediate values we derive an improved bound of O(1 + (min{α²/n, n²/α})^1/3).Additionally, we develop characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing.

REFERENCES

• 1: 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]
• 2: 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]
• 3: V. Bala and S. Goyal. A non-cooperative theory of network formation. Econometrica, 68(5):1181--1229, 2000.
• 4: A. Blokhuis and A. E. Brouwer. Geodetic graphs of diameter two. Geometricae Dedicata, 25:527--533, 1988.
• 5: Jacomo Corbo , David Parkes, The price of selfish behavior in bilateral network formation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073833]
• 6: 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]
• 7: 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]
• 8: 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
• 9: R. Distel. Graph Theory. Graduate Texts in Mathematics. Springer, 2000.
• 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: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 12: A. Gupta, A. Srinivasan, and E. Tardos. Cost-sharing mechanisms for network design. In Proc. 7th APPROX, pages 139--150, 2004.
• 13: H. Haller and S. Sarangi. Nash networks with heterogeneous agents, 2003.
• 14: M. Jackson. A survey of models of network formation:stability and efficiency. In G. Demange and M. Wooders, editors, Group Formation in Economics: Networks, Clubs and Coalitions. 2003.
• 15: 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]
• 16: R. Johari, S. Mannor, and J. Tsitsiklis. A contract-based model for directed network formation. Games and Economic Behaviour, 2006. To appear.
• 17: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of 16th STACS, pages 404--413, 1999.
• 18: H. Lin. On the price of anarchy of a network creation game. 2004.
• 19: J. F. Nash. Non-cooperative games. Annals of Mathematics, 54:286--295, 1951.
• 20: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 21: 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]
• 22: F. J. Mac Williams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North Holland Publishing, 1978.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory