📈 economics

The Expected Number of Pairwise Stable Networks

This paper derives a closed-form solution and asymptotic bounds for the expected number of pairwise stable networks in a model with random utilities, demonstrating that while the absolute number of such networks grows rapidly with population size, their fraction relative to all possible networks converges to zero almost surely.

Original authors: P. Jean-Jacques Herings, Christian Seel, Arkadi Predtetchinski

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: P. Jean-Jacques Herings, Christian Seel, Arkadi Predtetchinski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant room filled with people. Everyone in the room can potentially shake hands with anyone else. A "network" is simply the collection of all the handshakes that actually happen at a specific moment.

Now, imagine that every person in the room has a secret, random scorecard. This scorecard tells them how happy they are with the current pattern of handshakes. Sometimes, a person might think, "I'd be happier if I stopped shaking hands with Bob." Other times, they might think, "I'd be happier if I started shaking hands with Alice, and Alice agrees."

This paper asks a big question: If everyone's happiness is completely random, how many different patterns of handshakes will end up being "stable"?

A pattern is "stable" if no one wants to break a handshake, and no two people want to start a new one. The authors call this Pairwise Stability.

Here is the story of what they found, broken down into simple concepts:

1. The "Empty Room" vs. The "Mosh Pit"

The authors discovered a funny rule about stability: The more handshakes there are, the harder it is to stay stable.

Think of it like a dance floor.

The Empty Network: If no one is shaking hands, it's very easy to be stable. No one can break a link because there are none, and it's hard to convince two people to start one if they are just randomly happy.
The Complete Network: If everyone is shaking hands with everyone else, it's a chaotic mess. It's very likely that at least one person wants to drop a partner, or two people want to swap partners.

The paper proves mathematically that as you add more links (handshakes), the chance of the whole group being stable drops. The "empty room" is the most likely to be stable; the "mosh pit" is the least likely.

2. The "Seniority Score"

To figure out the average number of stable groups, the authors invented a clever scoring system they call "Seniority Degrees."

Imagine the people in the room are lined up by age (or ID number).

If you are shaking hands with someone older than you, you get a point.
If you are not shaking hands with someone younger than you, you get a point.
You also get a free point just for existing.

The "Seniority Score" of a whole network is the product of everyone's points. The math shows that the expected number of stable networks is simply the sum of the "inverse" of these scores for every possible network.

The Catch: For a small group (say, 7 people), there are over 268 million possible handshake patterns. Calculating this score for every single one is like trying to count every grain of sand on a beach by hand. It's impossible for large groups.

3. The "Magic Bounds"

Since they couldn't count every grain of sand, the authors built a fence around the answer. They created a Lower Bound (the minimum number of stable networks we can expect) and an Upper Bound (the maximum).

They found that as the group gets huge, the number of stable networks grows incredibly fast.

The Growth: The number of stable networks explodes to infinity as the population grows.
The Paradox: Even though the number of stable networks is huge, the percentage of all possible networks that are stable is tiny.

The Analogy: Imagine a library with a billion books. The authors found that there are millions of "good" books (stable networks). But because the library has a trillion books total, the "good" books are still a tiny, tiny drop in the ocean.

4. The "Hamming Distance" (The Ripple Effect)

The paper also looked at how two different stable networks relate to each other. They used a concept called Hamming Distance, which is just a fancy way of counting how many handshakes are different between two groups.

Distance of 1: If two networks differ by just one handshake, they cannot both be stable at the same time. It's like two people trying to stand on the same chair; only one can fit.
Distance of 2: If they differ by two handshakes, they are slightly "linked." If one is stable, it makes the other slightly more likely to be stable.
Distance of 3 or more: If they differ by three or more handshakes, they are completely independent. Knowing one is stable tells you nothing about the other.

As the group gets huge, almost all pairs of networks are far apart (distance 3+). This means the "noise" cancels out, and the math becomes very predictable.

The Final Verdict

The paper concludes with two surprising facts about what happens when the population gets very large:

Stability is Abundant: You will almost certainly find many stable networks. It's not a rare event; it's a guarantee that there are thousands or millions of them.
Stability is Rare: Even though there are millions of them, they are still a microscopic fraction of all the possible ways people could connect.

In short: In a world of random happiness, you will almost always find some arrangements where everyone is happy enough to stay put. But finding a "perfect" arrangement is like finding a needle in a haystack, even if the haystack is so big it contains a billion needles. The paper gives us the math to count those needles and prove they are everywhere, yet still rare.

Technical Summary: The Expected Number of Pairwise Stable Networks

Problem Statement
This paper investigates the probabilistic properties of pairwise stability within economic network formation models where individual utilities are random variables. While pairwise stability (Jackson and Wolinsky, 1996) is the dominant solution concept for network formation, its existence is not guaranteed for arbitrary utility profiles, and the literature has largely focused on deriving sufficient conditions for existence. This work shifts the perspective to a probabilistic framework, asking: What is the probability that a specific network is pairwise stable? What is the expected number of pairwise stable networks in a population of size $n$ ? How does this number behave asymptotically as $n \to \infty$ ?

Methodology
The authors model a population of $n$ individuals where the utility of each agent $i$ for every possible network $g$ is drawn independently and uniformly from $[0, 1]$ . This defines a network model with random utilities $(U_n, P_n)$ .

Probability of Stability: The paper first derives the probability that a specific network $g$ is pairwise stable. This involves analyzing the conditions for unilateral link deletion and bilateral link addition. The authors establish that the probability of stability is monotone with respect to set inclusion: adding links decreases the probability of stability.
Expected Number of Stable Networks: To compute the expected number of pairwise stable networks, $E(s_n)$ , the authors introduce the concept of seniority degrees. For a given network, an individual's seniority degree is calculated based on their links with "seniors" (higher index) and missing links with "juniors" (lower index). The expected number of stable networks is shown to be the sum of the inverses of the seniority degrees across all possible networks.
Bounds and Asymptotics: Recognizing that the exact summation is computationally intractable for large $n$ $n$ (due to the $2^{n(n-1)/2}$ $2^{n (n - 1) /2}$ possible networks), the authors derive tractable lower and upper bounds.
- The lower bound utilizes Jensen's inequality applied to the logarithm of the product of seniority degrees, reducing the problem to the expectation of the logarithm of a Bernoulli random variable.
- The upper bound employs an iterated integral approach, bounding the integrand by a product of independent random variables, drawing an analogy to Knuth's (1976) work on stable matchings.
Variance and Convergence: The second group of results analyzes the variance of the number of stable networks. The authors relate the dependence between the stability of two networks to their Hamming distance (the number of links by which they differ). They prove that if the Hamming distance is $\ge 3$ , the events of stability are independent; if the distance is 2, they are positively dependent; and if the distance is 1, they are mutually exclusive.

Key Contributions and Results

Monotonicity of Stability Probability: The paper proves that the probability of a network being pairwise stable decreases as links are added. The empty network has the highest probability of stability, while the complete network has the lowest.
Closed-Form Expression: An exact expression for the expected number of pairwise stable networks is provided as the sum of the reciprocals of the seniority degrees of all networks (Theorem 4.2).
Asymptotic Behavior: The authors establish that the expected number of pairwise stable networks grows at a rate comparable to the sequence:
$c_n = 2^{n(n-1)/2} \left(\frac{2}{n+1}\right)^n$
While the total number of networks grows as $2^{n(n-1)/2}$ , the fraction of networks that are pairwise stable decays as $(\frac{2}{n+1})^n$ , tending to zero.
Normalized Expectation: By normalizing the number of stable networks by $c_n$ , the authors show that the expected normalized number lies asymptotically between $\sqrt{e}$ and $e$ .
Variance Convergence: The variance of the normalized number of pairwise stable networks converges to zero as $n \to \infty$ . This is a consequence of the fact that as $n$ grows, the fraction of network pairs with a Hamming distance $\ge 3$ approaches 1, rendering the stability events asymptotically independent.
Almost Sure Convergence: Combining the convergence of the variance to zero with the growth of the expectation, the paper concludes that almost surely, the absolute number of pairwise stable networks tends to infinity as $n \to \infty$ , while the fraction of such networks among all possible networks tends to zero.

Significance and Claims
The paper claims to provide a probabilistic foundation for the view of pairwise stability as a "weak" or "permissive" solution concept. Unlike random matching models where a stable matching is guaranteed to exist (Gale and Shapley, 1962), pairwise stability in networks does not guarantee existence for every profile. However, this probabilistic analysis demonstrates that while the fraction of stable networks vanishes, the absolute number of stable networks explodes as the population grows. Thus, in large populations, it is not only possible but almost certain that multiple pairwise stable networks exist.

The authors note that their approach differs from random game literature (e.g., Goldman, 1957; Rinott and Scarsini, 2000) because pairwise stability is an asymmetric concept (unilateral deletion vs. bilateral addition), leading to distinct statistical properties. Similarly, it differs from random matching models due to the larger probability space and the specific mechanics of link formation.

Limitations and Future Directions
The paper acknowledges that the exact limit of the normalized expected number of stable networks remains an open question, though it is bounded between $\sqrt{e}$ and $e$ . Future research directions suggested include introducing correlations in payoffs (following Rinott and Scarsini, 2000), applying the framework to specific network models like the co-author or connections models, and analyzing stronger solution concepts such as strongly stable networks where arbitrary coalitions can deviate.

1. The "Empty Room" vs. The "Mosh Pit"

2. The "Seniority Score"

3. The "Magic Bounds"

4. The "Hamming Distance" (The Ripple Effect)

The Final Verdict

More like this