  Kleinberg proposed a family of small-world networks to explain the
navigability of large-scale real-world social networks. However, the underlying
mechanism that drives real networks to be navigable is not yet well understood.
In this paper, we present a game theoretic model for the formation of navigable
small world networks. We model the network formation as a Distance-Reciprocity
Balanced (DRB) game in which people seek for both high reciprocity and
long-distance relationships. We show that the game has only two Nash
equilibria: One is the navigable small-world network, and the other is the
random network in which each node connects with each other node with equal
probability. We further show that the navigable small world is very stable ---
(a) no collusion of any size would benefit from deviating from it; and (b)
after an arbitrary deviations of a large random set of nodes, the network would
return to the navigable small world as soon as every node takes one
best-response step. In contrast, for the random network, a small group
collusion or random perturbations is guaranteed to move the network to the
navigable network as soon as every node takes one best-response step. Moreover,
we show that navigable small world has much better social welfare than the
random network, and provide the price-of-anarchy and price-of-stability results
of the game. Our empirical evaluation demonstrates that the system always
converges to the navigable network even when limited or no information about
other players' strategies is available, and the DRB game simulated on the
real-world network leads to navigability characteristic that is very close to
that of the real network. Our theoretical and empirical analyses provide
important new insight on the connection between distance, reciprocity and
navigability in social networks.
