Sansan Tech Blog

Sansanのものづくりを支えるメンバーの技術やデザイン、プロダクトマネジメントの情報を発信

【Dive into the Economics of Networks】vol.4 ネットワーク形成ゲームが Exponential Random Graph Model (ERGM) に収束することを示す

R&D データ分析 経済学 連載 計量経済学

f:id:komatsuna4747:20210127160740j:plain

Sansan DSOC R&D 研究員の小松です。前回の記事では、ネットワーク形成ゲームがポテンシャルゲームとして表せることをみました。本稿では、ポテンシャルゲームとして表せるネットワーク形成過程が Exponential Random Graph Model (ERGM) に収束することを確認します。ERGM とは、観察されたネットワークがどのようなメカニズムで形成されたかを描写するための統計モデルです。ネットワーク分析において非常に重要なモデルの1つといって差し支えないでしょう。その ERGM にミクロ的基礎付けができることを示した Mele (2017) の内容を、引き続き見ていきましょう*1。

Review

前回議論したことを復習していきましょう。まずネットワークのプレーヤー i の効用関数が以下のように与えられるとします。

\begin{align} u_{i}(g, \theta) = \alpha \sum_{j=1}^{n} g_{ij} + \beta \sum_{j=1}^{n} \sum_{k=1}^{n} g_{ij} g_{jk} + \gamma \sum_{j=1}^{n} \sum_{k=1}^{n} g_{ij} g_{jk} g_{ki} \end{align}

\alpha、 \beta、 \gamma はそれぞれ、他のプレーヤーとの直接のつながり、 つながる相手が他の人とどれぐらいつながっているか (人気者であるか)、つながる相手との共通の友人がどれぐらいいるか (三角形が形成されているか)、以上から得られる効用を決定づけるパラメーターです。 そしてネットワーク上の各プレーヤーは、他のノードがどのように戦略的に動くかを考慮しながら自身の効用関数を最大化するように、他のノードとつながりを形成すると考えます。

このとき、以下のような、プレーヤー全てのインセンティブを要約するようなポテンシャル関数が存在します。

\begin{align} Q(g, \theta) = \alpha \sum_{i=1}^{n} \sum_{j=1}^{n} g_{ij} + \frac{1}{2} \beta \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} g_{ij} g_{jk} + \frac{2}{3} \gamma \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} g_{ij} g_{jk} g_{ki} \end{align}

このポテンシャル関数なるものを考えるベネフィットは、ネットワークの均衡条件の導出を関数の最大化問題に置き換えて議論しやすくすることでした。

Multiple Equilibria

pairwise stable なネットワークは、ポテンシャル関数 Q の最大元として与えられるのでした。しかし留意すべきは、その最大元は unique ではないということです。 pairwise stable なネットワークは複数存在しうると考えられ、現実に観察されるネットワークはその1つと考えられます。 この複数均衡の場合、推定したいパラメーターが追加的な仮定を置かないかぎり点推定できないことがわかっています。 その問題がなぜ起こるのか、ネットワークから一旦離れて、企業の参入ゲームを推定を例として見てみます*2。

あるマーケットに2つの企業が存在し、その市場に参入するかどうかを考えています。 その市場に参入することで得られる利潤は競合の有無によって左右されますから、お互いの企業が参入するかを読み合いながら意思決定をします。 D_1, D_2 をそれぞれ企業1、2が市場に参入するかどうかを表す binary variable として、以下のような計量モデルを考えます。

\begin{align} D_1 = 1\{ x_1 \beta + \rho D_2 - u_1 \geq 0 \} \\ D_2 = 1\{ x_2 \beta + \rho D_1 - u_2 \geq 0 \} \\ \end{align}

ここで関心のあるパラメーターは \beta, \rho です。 競合が参入すると利潤は減ると考えるのが自然なので、 \rho \lt 0 と仮定します。 このパラメーターを推定するために、尤度関数を構築して最尤法で推定することを考えます。

(D_1, D_2) と unobservables (u_1, u_2) の間には以下の関係が成り立つことがわかります。


\begin{align}
(D_{1}, D_{2}) = (1, 1) &\Rightarrow u_{1} \leq x_{1} \beta + \rho \land u_{2} \leq x_{2} \beta + \rho \\
(D_{1}, D_{2}) = (1, 0) &\Rightarrow u_{1} \leq x_{1} \beta \land u_{2} > x_{2} \beta + \rho \\
(D_{1}, D_{2}) = (0, 1) &\Rightarrow u_{1} > x_{1} \beta + \rho \land u_{2} \leq x_{2} \beta \\
(D_{1}, D_{2}) = (0, 0) &\Rightarrow u_{1} > x_{1} \beta \land u_{2} > x_{2} \beta
\end{align}

これを u_1 u_2 平面に(D_1, D_2) との関係を図示すると以下のようになります。

f:id:komatsuna4747:20210706112828p:plain

ここ注目すべきは、上の式の2番目と3番目で表される領域が、(\rho が負である限り) 真ん中の茶色の部分で overlap することです。 茶色以外の領域ではナッシュ均衡は一意に決まりますが、その茶色の領域では2つのナッシュ均衡が考えられます。 そしてその2つのナッシュ均衡のうち実際にどちらが選ばれるかは、今与えられた情報だけからはわかりません。 その overlap した箇所があるために

\begin{align} \Pr \{(D_1, D_2) = (1, 1) |x, \rho, \beta \} + \Pr\{(D_1, D_2) = (1, 0) |x, \rho, \beta \} + \\ \Pr\{(D_1, D_2) = (0, 1) |x, \rho, \beta \}+ \Pr\{(D_1, D_2) = (0, 0) |x, \rho, \beta \} > 1 \end{align}

となり、尤度関数が well-defined でなくなってしまいます*3。 以上は2つの企業の参入ゲームを考えましたが、ネットワーク形成ゲームにおいても複数均衡が存在することで、尤度関数が well-defined でなくなってしまう問題が発生してしまいます。 ではこの問題をどう克服するのでしょうか。

1つの方法は、複数均衡のうちどの均衡が選択されるかを決める均衡選択メカニズムを導入することです。 Mele (2017, 2020)、Badev (2021) はそうした例で、ネットワークの各個人または各ペアに、リンクを形成/切断する機会が順次与えられながらネットワーク形成が行われるという meeting protocol を導入しています。 観察されたネットワークが実際にそうした meeting protocol に従っているかはさておき、このように出会いの機会が各個人または各ペアに順次与えられると考えることで、観察されたデータにフィットできる分布を得られることを示しています。

別の方法は、パラメーターの点識別ではなく部分識別を考えるというものです。Sheng (2020) はネットワーク形成ゲームの推定で部分識別を用いた手法を提案しています。

本稿では前者の逐次的な出会いのプロセスを考えることで、ネットワーク形成ゲームが定常分布として Exponential Random Graph Model (ERGM) と呼ばれるモデルに収束することを見ていきます。

Setup

逐次的な meeting protocol を具体的に記述します。

  1. ネットワークは逐次的に形成される。つまり各期間に2人のプレーヤーだけが行動を取る。
  2. 2人のプレーヤーは、\rho_{ij} := \rho(X_{i}, X_{j}, g_{-ij}) > 0 の確率で出会う。ただし g_{-ij} はネットワーク g から dyad ij を除いたネットワークである。
  3. 2人のプレーヤーはリンクを形成または削除するかを選択する前に、タイプ I 極値分布から i.i.d. で draw されたショック (\varepsilon_{ij1}, \varepsilon_{ij0}) を受け取る。

期間 t にリンク g_{ij}^{t} が形成されるのは以下が成り立つときです。 \begin{align} u_{i}(g_{ij}^{t} = 1, g_{-ij}^{t-1}, \theta) + u_{j}(g_{ij}^{t} = 1, g_{-ij}^{t-1}, \theta) + \varepsilon_{ij1} \geq u_{i}(g_{ij}^{t} = 0, g_{-ij}^{t-1}, \theta) + u_{j}(g_{ij}^{t} = 0, g_{-ij}^{t-1}, \theta) + \varepsilon_{ij0} \end{align}

それぞれの仮定のお気持ちを確認していきましょう。

今考えている効用関数は、ノード i と j のつながり以外の別のリンクの存在も影響を与えます。 前回みたように、ネットワーク上で各リンクが相互に依存している (interdependent) 状況で、pairwise stable なネットワークを探すということは非常に大変な作業です。 各期に意思決定を行うプレーヤーを2人に絞ることで、相互依存した意思決定を簡略化するのが1つ目の仮定の役割となります。

2つ目の仮定で重要な点は、任意のプレーヤー i と j が出会う確率が正であるという点です。つまり、どのプレーヤーとも出会う可能性があると仮定しています。 この meeting protocol で得られるネットワークの列 [g^{0}, g^{1}, \ldots] は1期前のネットワークにのみ依存するマルコフチェーンとなりますが、それがエルゴード的となるためにこの仮定をおいています。つまり、どのネットワーク g \in \mathcal{G} から出発しても、ある期間 t にネットワーク g' \in \mathcal{G} に正の確率で移ることができるというものです。 これはネットワーク形成過程がある定常分布に一意に収束することを示す上で重要な役割を果たします。

3つ目の仮定は、意思決定者には観察できるか、分析者には観察できない項を導入し、ネットワーク形成モデルと計量モデルを橋渡しする役割を果たします。 タイプ I 極値分布は discrete choice model でよく出てくる分布ですね。 その disturbance term を考慮に入れながら、プレーヤー i と j がリンクを形成することが得であるかどうかを判断します。その式は書き換えると、

\begin{align} u_{i}(g_{ij}^{t} = 1, g_{-ij}^{t-1}, \theta) + u_{j}(g_{ij}^{t} = 1, g_{-ij}^{t-1}, \theta) - (u_{i}(g_{ij}^{t} = 0, g_{-ij}^{t-1}, \theta) + u_{j}(g_{ij}^{t} = 0, g_{-ij}^{t-1}, \theta)) + \varepsilon_{ij1} \geq \varepsilon_{ij0} \end{align}

となるわけですが、左辺の効用関数の部分はポテンシャル関数を用いて表すことができますから、最終的に

\begin{align} Q(g_{ij}^{t} = 1, g_{-ij}^{t-1}, \theta)+ \varepsilon_{ij1} \geq Q(g_{ij}^{t} = 0, g_{-ij}^{t-1}, \theta) + \varepsilon_{ij0} \end{align}

と書くことができます。

Main Result

いよいよ本題に入ります。以上の仮定のもとで、以下の Proposition が成り立ちます。

Proposition (Mele, 2017): ネットワーク形成ゲームは、以下の定常分布 \pi(g, \theta) に一意に収束する。

\begin{align} \pi(g, \theta) = \frac{\exp(Q(g, \theta))}{ \sum_{\omega \in \mathcal{G}} \exp(Q(\omega, \theta))} \end{align}

モデルの尤度関数は指数分布族、そしてネットワーク分析でよく出てくる Exponential Random Graph Model (ERGM) に属します。 詳細は次回以降に譲りますが、ERGM を考える利点はリンク同士の interdependencies を明示的に取り込むことができる点です。

この Proposition の証明を簡単に見てみましょう。

まず、あるネットワークから別のネットワークに遷移する遷移確率 \mathbb{P} はエルゴード的であるのでした*4。 \mathcal{G} は有限集合ですから、マルコフチェーンのエルゴード定理によって、以下の性質をみたす \mathcal{G} 上の確率分布 \pi が一意に存在します。

\begin{align} \pi \mathbb{P} = \pi \end{align}

これを不変性、または定常性といったりします。 この \pi が、 \pi(g, \theta) = \exp(Q(g, \theta)) / \sum_{\omega \in \mathcal{G}} \exp(Q(\omega, \theta)) であることを示せばよいことになります。 分布 \pi(g, \theta) が不変であるための十分条件は、 \pi(g, \theta) が詳細釣り合い条件 (detailed balance condition)

\begin{align} P_{gg'} \pi(g, \theta) = P_{g'g} \pi(g', \theta) \end{align}

をみたすことです。 ただし P_{gg'} := \Pr(g^{t+1} = g' | g^{t}= g) です。 したがって、 \pi(g, \theta) が上の条件をみたしていることを示せば、証明は終わりです。

ここで任意のプレーヤー i、j をとってきて、彼らのリンク形成に注目することにしましょう。 すなわち、 g = (1, g_{-ij})、 g' = (0, g_{-ij})とします。 さらに、 \Delta Q := Q(1, g_{-ij}, \theta) - Q(0, g_{-ij}, \theta) と定義しておきます。

さて、実際に P_{gg'} \pi(g, \theta) を計算していきます。 まず、 P_{gg'} は、i と j が期間 t に出会い (その確率は仮定より \rho(X_{i}, X_{j}, g_{-ij}) > 0) 、かつ i と j の間でリンクが形成されない (または切断される) 確率であるので、

\begin{align} P_{gg'} = \rho(X_{i}, X_{j}, g_{-ij}) \times \Pr(g_{ij} = 0 | g_{ij}) \end{align}

と書くことができます。また、


\begin{align}
\Pr(g_{ij} = 0 | g_{ij}) 
&= \Pr(Q(g_{ij}= 0, g_{-ij}, \theta)+ \varepsilon_{ij0} \geq Q(g_{ij} = 1, g_{-ij}, \theta) + \varepsilon_{ij1}) \\
&= \Pr(\varepsilon_{ij0} - \varepsilon_{ij1} \geq \Delta Q )
\end{align}

と書けますが、 (\varepsilon_{ij1}, \varepsilon_{ij0})はタイプ I 極値分布から i.i.d. で draw されているので、 \varepsilon_{ij0} - \varepsilon_{ij1} はロジスティック分布に従います*5。 したがって、


\begin{align}
\Pr(\varepsilon_{ij0} - \varepsilon_{ij1} \geq \Delta Q )　
&= 1 - \frac{\exp(\Delta Q)} {1 + \exp(\Delta Q)} \\
&= \frac{1} {1 + \exp(\Delta Q)}
\end{align}

と書けます。

以上の結果を用いて、あとは計算あるのみです。


\begin{align}
P_{gg'} \pi(g, \theta) 
&= \rho(X_{i}, X\_{j}, g_{-ij}) \times \Pr(g_{ij} = 0 | g_{-ij}) \times \frac{\exp(Q(g_{ij} = 1, g_{-ij}, \theta))}{ \sum_{\omega \in \mathcal{G}} \exp(Q(\omega, \theta))} \\
&= \rho(X_{i}, X\_{j}, g_{-ij}) \times  \frac{1} {1 + \exp(\Delta Q)} \times \frac{\exp(Q(g_{ij} = 1, g_{-ij}, \theta) + Q(g_{ij} = 0, g_{-ij}, \theta) - Q(g_{ij} = 0, g_{-ij}, \theta))}{ \sum_{\omega \in \mathcal{G}} \exp(Q(\omega, \theta))} \\
&= \rho(X_{i}, X\_{j}, g_{-ij}) \times  \frac{\exp(\Delta Q)} {1 + \exp(\Delta Q)} \times \frac{\exp(Q(g_{ij} = 0, g_{-ij}, \theta))}{ \sum_{\omega \in \mathcal{G}} \exp(Q(\omega, \theta))} \\
&=  \rho(X_{i}, X\_{j}, g_{-ij}) \times  \Pr(g_{ij} = 1 | g_{-ij})  \times  \pi(g', \theta)  \\
&=  P_{g'g} \pi(g', \theta) 
\end{align}

ゆえに、P_{gg'} \pi(g, \theta) = P_{g'g} \pi(g', \theta) が成り立ちます。 詳細釣り合い条件が成立していることから、今考えているネットワーク形成ゲームが定常分布 \pi(g, \theta) = \exp(Q(g, \theta)) / \sum_{\omega \in \mathcal{G}} \exp(Q(\omega, \theta)) に一意に収束することが示せました。

ここで注意すべきは、一意に得られたものはネットワークの集合 \mathcal{G} で定義された定常分布 \pi(g, \theta) であり、必ずしも pairwise stable なネットワークが unique であることを述べていません。 実際、均衡条件をみたすネットワークが複数存在することがのちのち ERGM の推定に影響を及ぼすケースがあるのですが、それは別の回で見ていきましょう。

Next

本稿では、ERGMのミクロ的基礎付けを与える Mele (2017) の結果について証明を含めてみてきました。 well-defined な尤度関数が得られたのでこれで安心と言いたいところですが、この尤度関数に基づいたパラメーターの推定は一筋縄にはいきません。 その問題および解決策について、次回見ていけたらと思います。

References

  • Badev, A. (2021). Nash equilibria on (un)stable networks. Econometrica, 89(3), 1179-1206.
  • Mele, A. (2017). A structural model of dense network formation. Econometrica, 85(3), 825-850.
  • Mele, A. (2020). Does school desegregation promote diverse interactions? An equilibrium model of segregation within schools. American Economic Journal: Economic Policy, 12(2), 228-57.
  • Mele, A., & Zhu, L. Forthcoming. Approximate variational estimation for a model of network formation. Review of Economics and Statistics, 1-30.
  • Sheng, S. (2020). A structural econometric analysis of network formation games through subnetworks. Econometrica, 88(5), 1829-1858.
  • Tamer, E. (2003). Incomplete simultaneous discrete response model with multiple equilibria. Review of Economic Studies, 70(1), 147-165.


buildersbox.corp-sansan.com

*1:Mele (2017) が対象としているネットワークは directed ですが、本稿では前回に引き続き undirected network を考えます。本質的な議論は大きくは変わりませんが、undirected network のケースに関しては Mele and Zhu (forthcoming) を参照ください。

*2:ネットワーク形成を例としてもよいのですが、N = 3 で考えると図が3次元となり複雑になるのでやめておきます。 Sheng (2020) にそうした3次元の図がありますが、さっぱり理解できなかった。

*3:entry game の推定の詳細は Tamer (2003) を参照のこと。

*4:正確には、遷移確率が既約 (irreducible) かつ非周期的 (aperiodic) であることからエルゴード性が言えます。このあたりの詳細は確率論の教科書を参照ください。

*5:畳み込み積分、置換積分、部分積分を駆使すると、最終的にロジスティック分布の確率密度関数が得られます。

© Sansan, Inc.