Abstract:This paper studies probabilistic properties of pairwise stability for a network model where individual utilities are random variables. We study the probability that a given network is pairwise stable and the expected number of pairwise stable networks. We provide a closed-form solution for the latter number.
As the evaluation of the exact expression is computationally challenging for large populations, we provide tractable lower and upper bounds for this expression which allow us to pin down the asymptotic behavior of the expected number of pairwise stable networks up to a multiplicative constant. This asymptotic behavior is described by the number of networks $ 2^{n(n-1)/2} $ times $ (2/n+1)^{n} $, a sequence that tends to infinity fast. We normalize the number of pairwise stable networks by this sequence and show that the variance of the normalized number of pairwise stable networks converges to zero as $ n $ tends to infinity.
We conclude that almost surely the number of pairwise stable networks tends to infinity, while the fraction of pairwise stable networks tends to $ 0 $ as $ n $ goes to infinity.
From: Arkadi Predtetchinski [view email]
[v1]
Mon, 22 Jun 2026 14:58:28 UTC (29 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。