f:id:komatsuna4747:20210127160740j:plain

Sansan DSOC R&D 研究員の小松です。

本題に入る前に、1つ告知です。私が所属する DSOC R&D では、現在サマーインターンを募集中です。私も関わります。一緒にネットワークデータの海に潜りましょう。

さて本稿からは、ネットワーク形成の構造モデルを提案した Mele (2017) の内容に入っていきます。 Mele は内容が多岐に渡るので、数回に分けて内容を確認していきます。

今回は、戦略的ネットワーク形成過程がポテンシャルゲームとして記述できることを示します。これは後で計量モデルに繋げていく上で重要な役割を担います。

結論を先に言うと、ポテンシャルゲームを考えるモチベーションは、均衡条件を満たすネットワークを求める問題を、関数の最大化問題に置き換えて考えるためです。ポテンシャルゲームは、私たちの味方です。

Model setup

それでは、ネットワーク形成過程をゲームとしてモデル化していきましょう。今、ネットワークを構成するノードが $n$ あるとし、ネットワークが隣接行列 $g$ によって表現できるとします。ノード $i$ と $j$ がつながっているとき、 $g_{ij} = 1$ 、それ以外の場合は $g_{ij} = 0$ とします。ネットワークは undirected であるとして、全ての $i \neq j$ に対して $g_{ij} = g_{ji}$ が成立するとします*1。また、ループは存在しない、つまり全ての $i$ に対して $g_{ii} = 0$ が成り立つとします。

このネットワークの各ノードは、以下のような効用関数を持つとします。

$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}$

$\theta := (\alpha, \beta, \gamma)$ です。ネットワークの各プレーヤーは、他のノードとの直接のつながり、つながる相手が他の人とどれぐらいつながっているか、つながる相手との共通の友人がどれぐらいいるか (三角形が形成されているか)、これらから効用を得るとします。つながる相手が人気者であれば、その人とつながって何らかの利益を得たいと思うでしょう。共通の友人が存在する相手ならば、つながろうとする相手の価値が共通の友人を通じてある程度担保されるでしょうから、共通の友人が存在しないケースと比較してつながりの価値が相対的に高くなると考えることができます。こうした直感を、上の効用関数にて定式化しています。

そして、他のノードがどのように戦略的に動くかを考慮しながら自身の効用関数を最大化するように、他のノードとつながりを形成すると考えます。

Equilibrium

モデルが書けたところで、このゲームの均衡を考えましょう。その均衡概念として、前回見た pairwise stability というのを使いましょう。定義を再度確認します。

あるネットワーク $g$ が pairwise stable であるとは、以下の1、2を両方満たすときのことを言います。

For all $ij \in g$ , $u_i(g) \geq u_i(g - ij)$ and $u_j(g) \geq u_j(g - ij)$
For all $ij \notin g$ , if $u_i(g + ij) \gt u_i(g)$ , then $u_j(g) \gt u_j(g + ij)$

つまり、ネットワーク上のどのペアも今あるリンクを切りたくないし、どのペアもこれ以上リンクを形成したくない状態にあるネットワークの状態を pairwise stable であると言うのでした。

また、ノード $i$ と $j$ の間で何らかの transfer を許容した pairwise stability with transfers は以下のように定義されます。

For all $ij \in g$ , $u_i(g) + u_j(g) \geq u_i(g - ij) + u_j(g - ij)$
For all $ij \notin g$ , $u_i(g) + u_j(g) \geq u_i(g + ij) + u_j(g + ij)$

ここでは pairwise stability with transfers をゲームの均衡概念として用いることにします。

あるネットワーク $g$ が pairwise stability with transfers であるかどうかを確認するには、上で書いた定義を満たしているかを確認する必要があります。これが何をしているかを少しフォーマルに確認してみましょう*2。

$MU_{i, j}(g) := \begin{cases} u_i(g) + u_j(g) - (u_i(g - ij) + u_j(g - ij) ) \ \ \ (\text{if } ij \in g) \\ u_i(g) + u_j(g) - (u_i(g + ij) + u_j(g + ij)) \ \ \ (\text{if } ij \notin g) \end{cases}$

という関数を定義します。これは $i$ と $j$ にとっての marginal utility、すなわちリンクを生成する/切るときに追加的に得られる、または失う効用を表します。また、 $\mathcal{G}$ を全ての考えられるネットワークの集合、 $\mathcal{I} = \{0, 1\}$ と定義すると、 $\mathcal{G}$ から $\mathcal{I}^{n(n-1)/2}$ の写像は全単射 (bijection) です。つまり、ネットワークを行列で表現するか、エッジリストで表現するかの違いで、あるネットワークを表現しているという点で本質的な違いはないということです。

以下、 $g \in \mathcal{G}$ とそれと同等のエッジリストである $y \in \mathcal{I}^{n(n-1)/2}$ について、 $MU_{i, j}(g) = MU_{i, j}(y)$ のように書けるとします。ここで更に

$F(y) := [1(MU_{1, 2}(y) \geq 0), 1(MU_{1, 3}(y) \geq 0), \ldots, 1(MU_{n-1, n}(y) \geq 0)]^{\top}$

という関数 $F: \mathcal{I}^{n(n-1)/2} \to \mathcal{I}^{n(n-1)/2}$ を考えると、 $g$ が pairwise stable であるかを確認することは、 $g$ と同等の $y$ が関数 $F$ の不動点であるかを確認していることになります。

あるネットワーク $g$ が pairwise stable with transfers であるかどうかは、上の関数 $F$ の不動点であるかどうかを確認すればよい。言葉で言うのは簡単ですが、実際には非常に大変です。特に今考えている効用関数は、ノード $i$ と $j$ のつながり以外の別のリンクの存在も影響を与えます。またノード $i$ と $j$ のつながりが変化すれば、それ以外のつながりにも影響を与えます。このように、ネットワーク上で各リンクが相互に依存している (interdependent) 状況で、pairwise stable なネットワークを探すということは、途方も無い作業に思えます。

この均衡をより簡便に求める、確認することができないだろうかということで、このネットワーク形成ゲームをポテンシャルゲーム (potential game) として表現できないかと考えます。

Potential game

ポテンシャルゲーム、なんだか仰々しいものが出てきました。ポテンシャルゲームとは何者なのでしょうか。それに親しむために、一旦ネットワークから離れて、ミクロ経済学で学ぶクールノー競争 (Cournot competition) のモデルを考えてみましょう。

ある寡占市場に会社が2社存在するとして、それぞれの利潤関数 (profit function) が

$\Pi_1(q_1, q_2) = \{a - b(q_1 + q_2)\} q_1 - cq_1$ ,　 $\Pi_2(q_1, q_2) = \{a - b(q_1 + q_2)\} q_2 - cq_2$

で与えられるとします。各々の生産量 $q_1, q_2$ が相互に影響を与える状況です。

まずは普通にこのモデルを解いてみましょう。各企業は、相手の生産量を所与として、利潤を最大化するように自分の生産量を決定します。一階の条件は、

$\frac{\partial \Pi_1}{\partial q_1} (q_1, q_2) = 0$ かつ $\frac{\partial \Pi_2}{\partial q_2} (q_1, q_2) = 0$ です。これより、各企業の最適反応関数

$q_1(q_2) = \frac{a-c}{b} - 2q_2$ , $q_2(q_1) = \frac{a-c}{b} - 2q_1$

を得ます。

$f(q_1, q_2) := [ \frac{a-c}{b} - 2q_2, \frac{a-c}{b} - 2q_1]^{\top}$

という関数を定義します。このゲームの均衡における生産量 $q^{*} = (q_1^{*}, q_2^{*})^{\top}$ は、 $f(q^{*}) = q^{*}$ という連立方程式を解くことで得られます。これは $q^{*}$ が関数 $f$ の不動点であることに他なりません。そしてその不動点は、

$q_1^{*} = q_2^{*} = \frac{2(a - c)}{3b}$

と求めることができます。これがこのモデルの通常の解き方でしょう。

ここでどういうわけか、以下のような関数 $P^{*}$ をラマヌジャンが天啓を得たかのように思いついたとしましょう。

$P^{*}(q_1, q_2) := a (q_1 + q_2) - b(q_1^{2} + q_2^{2}) -b q_1 q_2 - c(q_1 + q_2)$

この関数 $P^{*}$ は、すべての $q_1, q_2, x_1, x_2 \in \mathbb{R}_{+}$ に対して、

$\Pi_1 (q_1, q_2) - \Pi_1 (x_1, q_2) = P^{*}(q_1, q_2) - P^{*}(x_1, q_2)$ $\Pi_2 (q_1, q_2) - \Pi_2 (q_1, x_2) = P^{*}(q_1, q_2) - P^{*}(q_1, x_2)$

が成立することが確認できます。このような条件を満たす関数 $P^{*}$ のことを、ポテンシャル関数 (potential function) と呼び、そうしたポテンシャル関数が存在するゲームのことを ポテンシャルゲーム (potential game) と呼びます*3。

ポテンシャルゲームにおいて、ナッシュ均衡を求めることは、ポテンシャル関数の最大値 (正確には極大値) を求めることと同値になります。 $P^{*}$ は明らかに上に凸の関数なので、一階の条件を満たす $(q_1, q_2)$ が $P^{*}$ の最大元になります。実際に一階の条件をとると、

$0 = \frac{\partial P^{*}}{\partial q_1} (q_1, q_2) = a - 2b q_1- b q_2 - c$ かつ $0 = \frac{\partial P^{*}}{\partial q_2} (q_1, q_2) = a - 2b q_2- b q_1 - c$

から

$q_1 = \frac{a-c}{b} - 2q_2$ かつ $q_2 = \frac{a-c}{b} - 2q_1$

を得ます。これは一番最初に一階の条件で求めたときと同じ式ですから、得られる解も当然同じになります。またポテンシャル関数の定義、および $q^{*} = (q_1^{*}, q_2^{*})$ が $P^{*}$ の (唯一の) 最大元であることから、全ての $x_1, x_2 \in \mathbb{R}_{+}$ に対して、

$P^{*}(q^{*}) - P^{*}(x_1, q_2^{*}) = \Pi_1 (q^{*}) - \Pi_1 (x_1, q_2^{*}) > 0$ $P^{*}(q^{*}) - P^{*}(q_1^{*}, x_2) = \Pi_2 (q^{*}) - \Pi_2 (q_1^{*}, x_2) > 0$

が成立することが確認できます。これは企業1、2ともに $q^{*} = (q_1^{*}, q_2^{*})$ においては生産量を変化させるインセンティブがない、つまりナッシュ均衡であることがわかります。

以上から、最適反応関数の不動点として定義されるナッシュ均衡を求めることと、ポテンシャル関数の最大値を与える生産量を求めることが同値であることがわかります。別の言い方をすると、ゲームの全てのプレーヤーのインセンティブを要約した関数が、ポテンシャル関数というわけです。

このポテンシャル関数を用いた議論で重要なことは、「不動点であるところの均衡をそのまま扱うのではなく，最大化問題におきかえて分析する」ということです (尾山, 2016)。このモデルにおいて、不動点は連立方程式を解くだけで得られましたから、それほど苦労はしませんでした。しかし、モデルが複雑になったり、最初に導入したネットワーク形成ゲームを考えたりするときは、不動点を考えることが複雑になることは想像に難くありません。

もしゲームがポテンシャルゲームである、つまりポテンシャル関数が存在することがわかれば、私たちはその関数の挙動にのみ集中すればよいことになります。不動点を考えるよりも関数の最大化問題の方が、扱いがより簡単になるでしょう。

ポテンシャルゲームに関する詳細は、元論文の Monderer and Shapley (1996) を参照下さい。

Existence of a potential function in the network formation game

さてここでの問題は、こうした便利なポテンシャル関数が、最初の方で考えたネットワーク形成ゲームにおいて存在するかということです。その答えが、条件をみたす選好のもとで Yes であると示したのが Mele (2017) です。もう一度、今考える効用関数を書き下しておきましょう。

$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}$

このとき、以下が言えます。

Proposition (Mele, 2017): 全てのネットワーク $g \in \mathcal{G}$ に対して、ネットワーク生成ゲームの全てのプレーヤーの deterministic なインセンティブは以下のポテンシャル関数によって要約される。

$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}$

すなわち、全ての $ij \in g$ に対して

$Q(g, \theta) - Q(g - ij, \theta) = u_i(g, \theta) + u_j(g, \theta) - \{u_i(g - ij, \theta) + u_j(g - ij, \theta)\}$

が成り立ち、全ての $ij \notin g$ に対して

$Q(g, \theta) - Q(g + ij, \theta) = u_i(g, \theta) + u_j(g, \theta) - \{u_i(g + ij, \theta) + u_j(g + ij, \theta)\}$

が成り立つ。

本当はこの Proposition の証明までやろうと思いましたが、本ポストがかなり長くなるのと、はてなブログが数式を用いた証明に向いていないことから断念しました。和のとり方がやや複雑ですが、ぜひ手を動かして示してみてください。

上の Proposition が成立することを所与として話を進めます。先の議論に基づくと、ポテンシャル関数を使うことのメリットは、ナッシュ均衡を求める問題を関数の最大化問題に置き換えて考えられることでした。これはネットワーク形成ゲームにおいても同様です。ネットワーク形成ゲームがポテンシャルゲームとして書けるとき、pairwise stable (with transfers) なネットワークは必ず存在し、その1つはポテンシャル関数の最大元として与えられるようになります。これを確認しましょう。

まず、今考えているポテンシャル関数 $Q$ は必ず最大値を持ちます。これは、関数 $Q$ のドメイン $\mathcal{G}$ が有限であることからわかります*4。 $Q$ の最大元は必ずしもユニークではないことに注意しましょう。

ここで、 $Q$ の最大元の1つを $g^{*}$ とおきます。 $g^{*}$ は $Q$ の最大元の1つですから、すべての $ij \in g^{*}$ に対して

$Q(g^{*}, \theta) - Q(g^{*} - ij, \theta) \geq 0$

が成り立ち、かつすべての $ij \notin g^{*}$ に対して

$Q(g^{*}, \theta) - Q(g^{*} + ij, \theta) \geq 0$

が成り立ちます。ここで、ポテンシャル関数の定義を思い出すと、

$Q(g^{*}, \theta) - Q(g^{*} - ij, \theta) = u_i(g^{*}, \theta) + u_j(g^{*}, \theta) - \{u_i(g^{*} - ij, \theta) + u_j(g^{*} - ij, \theta)\} \geq 0$

$Q(g^{*}, \theta) - Q(g^{*} + ij, \theta) = u_i(g^{*}, \theta) + u_j(g^{*}, \theta) - \{u_i(g^{*} + ij, \theta) + u_j(g^{*} + ij, \theta)\} \geq 0$

と書けます。すなわち、すべての $ij \in g^{*}$ に対して

$u_i(g^{*}, \theta) + u_j(g^{*}, \theta) \geq u_i(g^{*} - ij, \theta) + u_j(g^{*} - ij, \theta)$

が成り立ち、かつすべての $ij \notin g^{*}$ に対して

$u_i(g^{*}, \theta) + u_j(g^{*}, \theta) \geq u_i(g^{*} + ij, \theta) + u_j(g^{*} + ij, \theta)$

が成り立ちます。これは $g^{*}$ が pairwise stable with transfers であることに他なりません。したがって、pairwise stable なネットワークの存在、およびポテンシャル関数 $Q$ の最大元が pairwise stable with transfers であることが示せました*5。

以上のように、ポテンシャル関数を使うと議論を関数の最大化問題に置き換えて考えることができ非常に楽になります。ポテンシャルゲームは私たちの味方と冒頭で言った理由はここにあります。

おわりに

以上数式が多くなってしまいましたが、簡単な例を通じてポテンシャルゲームの有用性、およびネットワーク形成ゲームをポテンシャルゲームとして記述する意義を眺めました。これらは理論的な分析を進める上で便利なツールとなるだけでなく、計量モデルとして記述する上でも重要な役割を担います。

注意点としては、度々指摘していますが、pairwise stable なネットワークは複数存在し得る点です。複数均衡などと言ったりしますが、そうした状況下ではパラメーターの推定に色々と問題が生じてしまいます。その問題についてどう対処するのかを、次のポストで見ていきましょう。 ERGM ファンのみなさま、おまたせしました。次回ようやく、例の尤度関数が登場します。お楽しみに。

References

Mele, A. (2017). A structural model of dense network formation. Econometrica, 85(3), 825-850.
Miyauchi, Y. (2016). Structural estimation of pairwise stable networks with nonnegative externality. Journal of Econometrics, 195(2), 224-235.
Monderer, D., & Shapley, L. S. (1996). Potential games. Games and economic behavior, 14(1), 124-143.
尾山大輔. (2016). 社会ゲームにおけるナッシュ均衡の安定性: ポテンシャル・ゲームと完全予見動学. 計測と制御, 55(4), 362-367.

buildersbox.corp-sansan.com

*1:Mele (2017) では directed network についてモデル化していますが、本稿では後の pairwise stability との整合性が良いことから、undirected network にのみ焦点を当てます。

*2:以下の数式表現は Miyauchi (2016) を参考にしています。

*3:ここで考えるポテンシャルは、物理学などで用いられるそれと概念的には同じものです。

*4:実際は $\mathcal{G}$ はほぼ infinite といっていいぐらいの集合ですが、理論上は有限です。

*5:あるネットワーク $g$ が pairwise stable with transfers であるには、必ずしもそれが $Q$ の最大元である必要はなく、local maximum であれば十分です。