A gentle introduction to strategic networks formation

When Nash equilibrium is not enough, we have to introduce another kind of stability concept. Playground here (sources included)! 🎉

Probabilistic network formation models introduce special network topologies but can’t explain why does those topologies do actually take form.

The connection model developed by Jackson and Wolinsky in 1996 assigns a utility to every agent (node) in a network. Agents gains benefit (0<𝛅<1) from friends, friends of friends (and so on…) and pay a cost (𝙘>0) to maintain links.

So every agent has the following payoff:

and we can observe how there is a sort of decay in benefit, as we consider friends (and friends of friends…) and that the cost is taken in account only for direct connections.

In this model, payoffs are symmetrical:

Let’s introduce a game on networks: in this game, every player announces at the same time the will to form a link with another player.

A Nash equilibrium is a configuration where nobody wants to change his own set of announcements, given the others’ set of announcements.

If we consider a dyad, it’s obvious that only two states are a Nash equilibrium: nobody wants to form a link or players both want to form a link. In the first case, if one player does not announce the will to form a link, the other player knows the links will not form, so is not going to form a link.

In the other case, players both announce the will to form a link and the link is created.

Those two Nash equilibria can predict any kind of situation than can arise and so it’s not so predictive.

For this reason another concept is introduced, Pairwise Stability, where G is Pairwise stable:

• if nobody wants to sewer a link included in G
• if one player wants to include a link, the other player does not want (otherwise it should be included!)

Back to the dyad example, now both the configurations are Nash stable but only the latter is Pairwise stable.

Pairwise stability can be considered a fairly weak concept, since only considers adding or deleting one link a time.

While Pairwise stability consider individual incentives, efficiency is about overall payoff gain.

A network is Pareto Efficient if does not exists another network g’ such as:

ui(g’)>=ui(g) for each i, with strict inequality for some i

So basically no network makes someone lose while offering a strictly higher payoff for someone other.

A stronger notion of efficiency is (strong) efficiency where the network maximize the overall agent payoff:

With strong efficiency, no matter if someone is getting better and someone is getting worse, efficiency just assure that that the overall payoff is at is best (and this is also what we generally call “utilitarianism”).

A network which evolved toward pairwise stability does not imply strong efficiency nor pareto efficiency and this is a consequence of the fact that individuals do not take care of harming other individuals while trying to improve self payoff.

Since networks will tend to pairwise stability, connection model makes possible to predict which networks will form and to evaluate them.

Let’s consider strong efficiency depending on delta and cost value, we will observe the following:

• 𝙘 < 𝛅-𝛅², cost to form a link is very low so the complete network is efficient
• 𝛅-𝛅²<𝙘<𝛅+(n-2)*𝛅²/2, the cost is medium and the star network is efficient
• 𝛅+(n-2)*𝛅²/2<𝙘, the cost is high so the empty network is efficient

Why stars? Because stars connect individuals at a minimum distances, minimizing indirect link delta loss.

Delta and cost also influence the structure of a pairwise stable network:

• for a low cost 𝙘 < 𝛅-𝛅², complete network is pairwise stable
• for a medium/low cost 𝛅-𝛅²< 𝙘 < 𝛅, star network is pairwise stable (but other networks can be pairwise stable too)
• for a medium/high cost 𝛅 < 𝙘 < 𝛅 + (n-2)𝛅²/2, the cost does not justify bringing only one person in the network with the link so forming links tends to bring in more people to get indirect benefits to compensate cost. Additionally, every agent forms a link only with agents bringing other connection with them. This is actually the case where a star network is efficient but not pairwise stable.
• 𝛅 + (n-2)𝛅²/2< 𝙘, the empty network is pairwise stable

References: “Social and economic networks”, Mattew O. Jackson, Princeton; Wikipedia, https://en.wikipedia.org/wiki/Strategic_Network_Formation