Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

ABSTRACT

Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We study the structural and complexity-theoretic properties of pure Nash equilibria in BBC games. We show that determining the existence of a pure Nash equilibrium in general BBC games is NP-hard. A major focus is the study of (n,k)-uniform BBC games - those in which all link costs, link lengths and preference weights are equal (to 1) and all budgets are equal (to k). We show that a pure Nash equilibrium or stable graph exists for all (n,k)-uniform BBC games and that all stable graphs are essentially fair (i.e. all nodes have similar costs). We provide an explicit construction of a family of stable graphs that spans the spectrum from minimum total social cost to maximum total social cost. To be precise we show that that the price of stability is Θ(1) and the price of anarchy is Ω(√n/k / log_k n) and O(√n/log_k n).

We analyze best-response walks on the configuration space defined by the uniform game, and show that starting from any initial configuration, strong connectivity is reached within n² rounds. We demonstrate that convergence to a pure Nash equilibrium is not guaranteed by demonstrating the existence of an explicit loop which also proves that even uniform BBC games are not potential games. Lastly, we extend our results to the case where each node seeks to minimize its maximum distance to the other nodes.

REFERENCES

• 1: Susanne Albers , Stefan Eilts , Eyal Even-Dar , Yishay Mansour , Liam Roditty, On nash equilibria for a network creation game, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.89-98, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109568]
• 2: N. Alon and Y. Roichman. Random Cayley graphs and expanders. RSA: Random Structures & Algorithms, 5, 1994.
• 3: Fred Annexstein , Marc Baumslag , Arnold L. Rosenberg, Group action graphs and parallel architectures, SIAM Journal on Computing, v.19 n.3, p.544-569, June 1990 [doi>10.1137/0219037]
• 4: Elliot Anshelevich , Bruce Shepherd , Gordon Wilfong, Strategic Network Formation through Peering and Service Agreements, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.77-86, October 21-24, 2006 [doi>10.1109/FOCS.2006.72]
• 5: Venkatesh Bala and Sanjeev Goyal. A noncooperative model of network formation. Econometrica, 68(5):1181--1229, 2000.
• 6: Shishir Bharathi, David Kempe, and Mahyar Salek. Competitive influence maximization in social networks. In WINE, pages 306--311, 2007.
• 7: Byung-Gon Chun, Rodrigo Fonseca, Ion Stoica, and John Kubiatowicz. Characterizing selfishly constructed overlay routing networks. In Proc. of IEEE INFOCOM'04, Hong Kong, 2004.
• 8: Gene Cooperman , Larry Finkelstein , N. Sarawagi, Applications of Cayley Graphs, Proceedings of the 8th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.367-378, August 20-24, 1990
• 9: 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]
• 10: Erik D. Demaine , MohammadTaghi Hajiaghayi , Hamid Mahini , Morteza Zadimoghaddam, The price of anarchy in network creation games, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281142]
• 11: Eyal Even-Dar and Michael Kearns. A small world threshold for economic network formation. In NIPS, pages 385--392, 2006.
• 12: Eyal Even-Bar , Michael Kearns , Siddharth Suri, A network formation game for bipartite exchange economies, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.697-706, January 07-09, 2007, New Orleans, Louisiana
• 13: 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]
• 14: 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]
• 15: Yair Halevi and Yishay Mansour. A Network Creation Game with Nonuniform Interests. In WINE, pages 278--292, 2007.
• 16: P. E. Haxell , G. T. Wilfong, A fractional model of the border gateway protocol (BGP), Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.193-199, January 20-22, 2008, San Francisco, California
• 17: Matthew Jackson and Asher Wolinsky. A strategic model of social and economic networks. Journal of Economic Theory, 71:44--74, 1996.
• 18: Ramesh Johari, Shie Mannor, and John N. Tsitsiklis. A contract-based model for directed network formation. Games and Economic Behavior, 56(2):201--224, 2006.
• 19: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 20: David Kempe, Jon M. Kleinberg, and Eva Tardos. Influential nodes in a diffusion model for social networks. In ICALP, pages 1127--1138, 2005.
• 21: Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In STACS '99, pages 404--413, March 1999.
• 22: Nikolaos Laoutaris, Georgios Smaragdakis, Azer Bestavros, and John Byers. Implications of selfish neighbor selection in overlay networks. In Proc. of IEEE INFOCOM '07, 2007.
• 23: Nikolaos Laoutaris , Laura J. Poplawski , Rajmohan Rajaraman , Ravi Sundaram , Shang-Hua Teng, Bounded budget connection (BBC) games or how to make friends and influence people, on a budget, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400774]
• 24: Evangelos Markakis , Amin Saberi, On the core of the multicommodity flow game, Proceedings of the 4th ACM conference on Electronic commerce, p.93-97, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779940]
• 25: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146403]
• 26: M.J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
equilibria, game theory, network construction