Today I read a paper titled “A bounded-degree network formation game”

The abstract is:

* 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.*