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.