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, and Liam Roditty. On Nash equilibria for a network creation game. In Proc. of SODA '06, pages 89--98, New York, NY, USA, 2006. ACM Press.
2. N. Alon and Y. Roichman. Random Cayley graphs and expanders. RSA: Random Structures & Algorithms, 5, 1994.
3. F. Annexstein, M. Baumslag, and A. L. Rosenberg. Group action graphs and parallel architectures. SIAM Journal on Computing, 19:544--569, 1990.
4. Elliot Anshelevich, Bruce Shepherd, and Gordon Wilfong. Strategic network formation through peering and service agreements. In Proc. of IEEE FOCS '06, pages 77--86, Washington, DC, USA, 2006.
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. G. Cooperman, L. Finkelstein, and N. Sarawagi. Applications of Cayley graphs. In AAECC: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. LNCS, Springer-Verlag, 1990.
9. Jacomo Corbo and David C. Parkes. The price of selfish behavior in bilateral network formation. In Proc. of PODC'05, pages 99--107, 2005.
10. Erik D. Demaine, MohammadTaghi Hajiaghavi, and Hamid Mahini. The Price of Anarchy in Network Creation Games In PODC, pages 292--298, 2007.
11. Eyal Even-Dar and Michael Kearns. A small world threshold for economic network formation. In NIPS, pages 385--392, 2006.
12. Eyal Even-Dar, Michael Kearns, and Siddharth Suri. A Network Formation Game for Bipartite Exchange Economies In SODA, pages 697-706, 2007.
13. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, and Scott Shenker. On a network creation game. In PODC '03, pages 347--351, New York, NY, USA, 2003. ACM Press.
14. J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker. A BGP-based mechanism for lowest-cost routing. In PODC, 2002.
15. Yair Halevi and Yishay Mansour. A Network Creation Game with Nonuniform Interests. In WINE, pages 278--292, 2007.
16. P. E. Haxell and G. T. Wilfong. A fractional model of the border gateway protocol (BGP). In SODA, pages 193--1999, 2008.
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 M. Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003.
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 Games or How to make friends and influence people, on a budget. arXiv:0806.1727 {cs.GT, cs.NI}.
24. Evangelos Markakis and Amin Saberi. On the core of the multicommodity flow game. In Proc. of the 4th ACM conference on Electronic commerce, pages 93--97, New York, NY, USA, 2003. ACM Press.
25. Thomas Moscibroda, Stefan Schmid, and Roger Wattenhofer. On the topologies formed by selfish peers. In PODC '06, 2006.
26. M.J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
27. Christos Papadimitriou. Algorithms, games, and the Internet. In STOC '01, pages 749--753, New York, NY, USA, 2001. ACM Press.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Network flows

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Network flows