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

• We use game theory to model the formation of social networks.
• We study how individuals form connections to maximize influence.
• We characterize the existence and structure of stable networks.
• Determining the existence of stable networks in general is intractable.
• When individuals are homogeneous, we present family of stable networks.

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)(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)(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.