The concept of small-world networks has been developed to help explain how real whole-world social networks manage to be “navigable.” By navigable I mean the ease with which any two people can be connected with seemingly few intermediate hops. One challenge with small-world networks is explaining what drives their formation. Game theoretic models are useful simulation tools that show how equilibria can develop across a multitude of actors, each trying to optimize some cost function. The authors use a game theoretic model to create a navigable small-world network, showing that the navigable network is a natural equilibrium state for their selected agent strategy.

Agents independently control their own connection preference parameter, which defines the relative probability that an agent will choose to connect to other agents far away versus agents in close geographic proximity. The payoff function developed by the authors is the product of the average distance of nodes to their long-range contacts (creating a preference for connecting with agents geographically remote) and the probability of forming reciprocal relationships with these long-range contacts. It is this latter probability factor that drives the model toward uniformity.

The authors show that under this payoff function the game has only two equilibria. The first is the navigable small-world network, which is resistant to both permutations and agent collusion. The second equilibrium is the random network that is shown to be unstable, where any permutations will steer it toward the navigable small-world network.

The paper presents an altogether intuitive result given the choice of payoff function, which the authors illustrate in detail through various tests and simulations.