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

作者：Laoutaris Nikolaos; Poplawski Laura; Rajaraman Rajmohan^*; Sundaram Ravi; Teng Shang Hua

来源：Journal of Computer and System Sciences, 2014, 80(7): 1266-1284.

DOI：10.1016/j.jcss.2014.04.013

• Network formation
• Algorithmic game theory
• Nash equilibrium
• Network creation games
• Social networks
• Price of anarchy

Motivated by applications in social and peer-to-peer networks, we introduce the Bounded Budget Connection (BBC) game and study its pure Nash equilibria. We have a collection of n players, each with a budget for purchasing links. Each link has a cost and a length. Each node has a preference weight for each node, and its objective is to purchase outgoing links within its budget to minimize its sum of preference-weighted distances to the nodes. We show that determining if a BBC game has pure Nash equilibria is NP-hard. We study (n, k)-uniform BBC games, where all link costs, lengths, and preferences are equal and every budget equals k. We show that pure Nash equilibria exist for all (n, k)-uniform BBC games and all equilibria are essentially fair. We construct a family of equilibria spanning the spectrum from minimum to maximum social cost. We also analyze best-response walks and alternative node objectives.

• 单位
  东北大学