The Expected Number of Pairwise Stable Networks

技术摘要：成对稳定网络的期望数量

问题陈述
本文研究了在个体效用为随机变量的经济网络形成模型中，成对稳定性（pairwise stability）的概率属性。虽然成对稳定性（Jackson and Wolinsky, 1996）是网络形成中的主流解概念，但对于任意效用剖面，其存在性并不能得到保证，且现有文献主要集中于推导存在性的充分条件。本研究将视角转向概率框架，探讨以下问题：一个特定网络是成对稳定的概率是多少？在规模为 $n$ 的群体中，成对稳定网络的期望数量是多少？当 $n \to \infty$ 时，这个数量如何变化？

研究方法
作者建立了一个由 $n$ 个个体组成的群体模型，其中每个个体 $i$ 对每一个可能的网络 $g$ 的效用均独立且均匀地从 $[0, 1]$ 中抽取。这定义了一个具有随机效用 $(U_n, P_n)$ 的网络模型。

1. 稳定性概率： 论文首先推导了特定网络 $g$ 是成对稳定的概率。这涉及分析单方面删除链路和双向增加链路的条件。作者证明，稳定性的概率相对于集合包含关系具有单调性：增加链路会降低稳定性的概率。
2. 稳定网络的期望数量： 为了计算成对稳定网络的期望数量，$E(s_n)$，作者引入了**资历度（seniority degrees）**的概念。对于给定网络，个体的资历度是基于其与“长辈”（索引较高者）的链路以及与“晚辈”（索引较低者）的缺失链路计算得出的。研究表明，成对稳定网络的期望数量等于所有可能网络中资历度倒数的总和。
3. 界限与渐近性质： 考虑到对于较大的 $n$，精确求和在计算上是难以处理的（由于存在 $2^{n(n-1)/2}$ 个可能的网络），作者推导出了易于处理的上下界。
   • 下界利用 Jensen 不等式应用于资历度乘积的对数，将问题简化为伯努利随机变量对数的期望。
   • 上界采用迭代积分法，通过将被积函数限制为独立随机变量的乘积，类比了 Knuth (1976) 关于稳定匹配的研究工作。
4. 方差与收敛性： 第二组结果分析了稳定网络数量的方差。作者通过研究两个网络之间的稳定性依赖关系，将其与它们的汉明距离（Hamming distance）（即它们之间差异的链路数量）联系起来。他们证明，如果汉明距离 $\ge 3$，则稳定性事件是独立的；如果距离为 2，则它们是正相关的；如果距离为 1，则它们是互斥的。

核心贡献与结果

• 稳定性概率的单调性： 论文证明，随着链路的增加，网络是成对稳定的概率会降低。空网络具有最高的稳定性概率，而完全图的稳定性概率最低。
• 闭式表达式： 论文提供了一个精确表达式，即所有网络资历度倒数的总和（定理 4.2）。
• 渐近行为： 作者确定了成对稳定网络的期望数量增长速率与序列如下相当：
  $$c_n = 2^{n(n-1)/2} \left(\frac{2}{n+1}\right)^n$$
  虽然总网络数量按 $2^{n(n-1)/2}$ 增长，但成对稳定网络的比例却以 $(\frac{2}{n+1})^n$ 的速度衰减，趋于零。
• 归一化期望： 通过用 $c_n$ 对稳定网络数量进行归一化，作者表明，归一化后的期望数量在渐近意义上介于 $\sqrt{e}$ 和 $e$ 之间。
• 方差收敛性： 归一化后的成对稳定网络数量的方差在 $n \to \infty$ 时趋于零。这是因为随着 $n$ 的增大，具有汉明距离 $\ge 3$ 的网络对所占的比例趋于 1，使得稳定性事件在渐近意义上是独立的。
• 几乎处处收敛： 通过结合方差趋于零与期望增长的结论，论文得出结论：几乎处处（almost surely），成对稳定网络的绝对数量在 $n \to \infty$ 时趋于无穷大，而其在所有可能网络中所占的比例趋于零。

意义与主张
该论文声称为将成对稳定性视为一种“弱”或“宽容”的解概念提供了概率基础。与随机匹配模型（如 Gale and Shapley, 1962，其中稳定匹配保证存在）不同，网络中的成对稳定性并不保证对于每个剖面都存在。然而，这种概率分析表明，尽管稳定网络的比例在消失，但稳定网络的绝对数量随着群体规模的扩大而爆炸式增长。因此，在大型群体中，存在多个成对稳定网络不仅是可能的，而且是几乎确定的。

作者指出，其方法不同于随机博弈文献（例如 Goldman, 1957; Rinott and Scarsini, 2000），因为成对稳定性是一个不对称的概念（单方面删除 vs 双向增加），从而导致了不同的统计特性。同样，它也不同于随机匹配模型，因为其概率空间更大且链路形成的机制不同。

局限性与未来方向
论文承认，归一化期望数量的精确极限仍是一个开放性问题，尽管它被限制在 $\sqrt{e}$ 和 $e$ 之间。建议的未来研究方向包括在收益中引入相关性（遵循 Rinott and Scarsini, 2000），将该框架应用于特定的网络模型（如共同作者模型或连接模型），以及分析更强的解概念，如任意联盟都可以偏离的强稳定性网络。