  Motivated by applications in peer-to-peer and overlay networks we define and
study the \emph{Bounded Degree Network Formation} (BDNF) game. In an
$(n,k)$-BDNF game, we are given $n$ nodes, a bound $k$ on the out-degree of
each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the
traffic rate from node $v$ to node $u$. Each node $v$ uses up to $k$ directed
links to connect to other nodes with an objective to minimize its average
distance, using weights $w_{vu}$, to all other destinations. We study the
existence of pure Nash equilibria for $(n,k)$-BDNF games. We show that if the
weights are arbitrary, then a pure Nash wiring may not exist. Furthermore, it
is NP-hard to determine whether a pure Nash wiring exists for a given
$(n,k)$-BDNF instance. A major focus of this paper is on uniform $(n,k)$-BDNF
games, in which all weights are 1. We describe how to construct a pure Nash
equilibrium wiring given any $n$ and $k$, and establish that in all pure Nash
wirings the cost of individual nodes cannot differ by more than a factor of
nearly 2, whereas the diameter cannot exceed $O(\sqrt{n \log_k n})$. We also
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 $\Theta(n^2)$ rounds. Convergence to a pure Nash
equilibrium, however, is not guaranteed. We present simulation results that
suggest that loop-free best-response walks always exist, but may not be
polynomially bounded. We also study a special family of \emph{regular} wirings,
the class of Abelian Cayley graphs, in which all nodes imitate the same wiring
pattern, and show that if $n$ is sufficiently large no such regular wiring can
be a pure Nash equilibrium.
