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$ がペアワイズ安定である確率を導出する。これには、一方的なリンクの削除（unilateral link deletion）と、双方によるリンクの追加（bilateral link addition）に関する条件の分析が含まれる。著者らは、安定性の確率は集合の包含関係に関して単調であること（リンクを追加すると安定性は低下する）を確立している。
2. 安定なネットワークの期待値: ペアワイズ安定なネットワークの期待値 $E(s_n)$ を計算するために、著者らは**シニアリティ次数（seniority degrees）**という概念を導入する。与えられたネットワークにおいて、個人のシニアリティ次数は、彼らの「シニア」（より高いインデックスを持つ者）とのリンク、および「ジュニア」（より低いインデックスを持つ者）との欠落しているリンクに基づいて算出される。ペアワイズ安定なネットワークの期待値は、すべての可能なネットワークにおけるシニアリティ次数の逆数の和として示される。
3. 境界値と漸近挙動: $n$ が大きい場合（$2^{n(n-1)/2}$ 個の可能なネットワークが存在するため）、正確な総和の計算が困難であることを認識し、著者らは扱いやすい上限および下限を導出する。
   • 下限は、シニアリティ次数の積の対数にイェンセンの不等式を適用することを利用しており、問題をベルヌーイ確率変数の対数の期待値へと還元している。
   • 上限は、反復積分法を用いて、積分被積分関数を独立な確率変数の積で抑えるものであり、Knuth (1976) による安定マッチングの研究との類似性を引きている。
4. 分散と収束: 第二のグループの結果は、安定なネットワークの数の分散を分析する。著者らは、2つのネットワーク間の安定性の依存関係を、それらのハミング距離（差分となるリンクの数）に関連付けている。彼らは、ハミング距離が $\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$ においてゼロに収束する。これは、集団が大きくなるにつれ、ハミング距離が $\ge 3$ であるネットワークのペアの割合が 1 に近づき、安定事象が漸近的に独立になるという事実によるものである。
• ほとんど確実に（Almost Surely）の収束: 分散の収束と期待値の成長率を組み合わせることで、本論文は、ほとんど確実に、絶対的な数のペアワイズ安定なネットワークは $n \to \infty$ において無限大に発散する一方で、全可能なネットワークに対するその割合はゼロに収束すると結論づけている。

意義と主張
本論文は、ペアワイズ安定性を「弱い」あるいは「許容的な」解概念とする見解に対して、確率論的な基礎を与えるものである。ランダム・マッチング・モデル（Gale and Shapley, 1962）では安定なマッチングの存在が保証されるが、ネットワークにおけるペアワイズ安定性は、あらゆるプロファイルに対して存在を保証するものではない。しかし、この確率論的分析は、安定なネットワークの割合は消失するものの、その絶対数は集団が増大するにつれて爆発的に増加することを明らかにしている。したがって、大規模な集団においては、複数のペアワイズ安定なネットワークが存在することは可能であるだけでなく、ほぼ確実である。

著者らは、ペアワイズ安定性が非対称な概念（一方的な削除 vs 双方による追加）であるため、本研究のアプローチがランダム・ゲームの文献（例：Goldman, 1957; Rinott and Scarsini, 2000）とは異なることを指摘している。同様に、ネットワークの形成メカニズムや確率空間の大きさの違いから、ランダム・マッチング・モデルとも異なる。

限界と今後の方向性
本論文は、正規化された期待値の正確な極限が依然として未解決の問題であることを認めているが、それは $\sqrt{e}$ と $e$ の間に抑えられている。示唆されている今後の研究方向としては、報酬における相関の導入（Rinott and Scarsini, 2000に従う）、共著者モデルやコネクション・モデルといった特定のネットワークモデルへの適用、そして任意の連合による逸脱を考慮した、より強い解概念（強安定ネットワークなど）の分析が含まれる。