  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. However, in a natural variant,
fractional BBC games - where it is permitted to buy fractions of links - a pure
Nash equilibrium always exists. 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. We also
study a special family of regular graphs in which all nodes imitate the "same"
buying pattern, and show that if n is sufficiently large no such regular graph
can be a pure Nash equilibrium. We analyze best-response walks on the
configuration defined by the uniform game. Lastly, we extend our results to the
case where each node seeks to minimize its maximum distance to the other nodes.
