ゲーム理論:フォーク定理

今日はゲーム理論に関する記事を書きます。表題の通りフォーク定理(folk theorem)に関する記事です。1回の記事だと紙面が足りなくなるので何回かに分ける予定です。

戦略形ゲームにおいてすべてのプレイヤーが戦略を(自分一人だけ)変えるインセンティブを持たない戦略の組であったり、進化ゲームにおける安定的な状態の戦略の組であったりするナッシュ均衡解について、一般にパレート最適は保証されないことが知られています。

「しょうがないね、だってナッシュ均衡なんだもん」

と割り切ってもよいのですが、やはりより好ましい選択肢があるのならそちらを取りたくなるのが人情というもの。 さらに、実社会ではナッシュ均衡解とパレート最適解が一致しないようなゲームに近似できる条件下で、ナッシュ均衡解ではなくパレート最適解の方が実現する場合があることも観察されていました。

フォーク定理はプレイヤーの合理性に制限を加えることなく、この現象を説明することができます。 *1

フォーク定理が要請する条件は以下の2つです。

  • ゲームが無限回繰り返し構造を持つこと
  • 将来利得の割引率が十分に大きいこと、ないしは存在しない(= 常に1)であること

この条件下では、

となります。

プレイヤー同士がお互いトリガー戦略を採用したり、Fudenberg と Maskin の戦略を使用した場合、均衡パス上で実現されるひとつひとつのゲームの結果は、そのゲームのナッシュ均衡解以外の解になることができます。


ここからは、一番簡単な

  • 将来利得の割引率が存在しない(= 常に1)場合の
  • トリガー戦略

が、無限回繰り返しゲームのナッシュ均衡解かつパレート最適解となることを示します。

まずは繰り返されるひとつひとつのゲームについて、
プレイヤー  i の戦略の集合を  S_i とおきます。
戦略自体は小文字で  s_i \in S_i と表すことにします。

各プレイヤーの戦略で構成されるベクトルは

 a = \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_n \end{pmatrix}

と表記します。
略記表現として、プレイヤー  j 以外のプレイヤーの戦略で構成されるベクトルを

 a_{-j} = \begin{pmatrix} s_1 \\ s_2 \\ \vdots \\ s_{j-1} \\ s_{j+1} \\ \vdots  \\ s_n \end{pmatrix}

と表記することとします。

プレイヤー i の利得関数は  P_i(a) となります。プレイヤー j の戦略と、それ以外の戦略ベクトルに着目して  P_i(s_j, a_{-j}) という書き方も許容することします。
利得関数の値域は  P_i と書くことにします。

プレイヤー j が最適応答をした際の j の利得  \max_{s_j} P_j(s_j, a_{-j}) を最小化させる  a_{-j} m_{-j} と書くことにします。
定義より明らかに  \max_{s_j} P_j(s_j, m_{-j}) \leq\max_{s_j} P_j(s_j, a_{-j}) となります。

この最小化されたプレイヤー j の利得を  p_{min, j} = \max_{s_j} P_j(s_j, m_{-j}) と書くこととして、

 p_{min} = \begin{pmatrix} p_{min, 1} \\ p_{min, 2} \\ \vdots \\ p_{min, n} \end{pmatrix}

と書くこととします。

次に、無限回繰り返しゲームの利得の評価について、 t 回目のゲームの利得を  p_{i, t} \in P_i と書くことにします。
プレイヤー i の利得を評価するにあたって素直に利得の総和  \sum p_{i, t} で評価しようとすると値が発散してしまう場合があるので、平均利得  v_i = \lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^{N} p_{i, t} で評価することにします。

各プレイヤーの無限回繰り返しゲームの平均利得のベクトルを、

 v = \begin{pmatrix} v_1 \\ v_2 \\ \vdots  \\ v_n \end{pmatrix}

とすると、このとき  v の集合内でパレート最適であり、 p_{min} をパレート支配するような  v が存在します。これを  v_{trigger} と書くことにします。

トリガー戦略を以下のように定義します。

  1. ゲーム開始時点からは、 v_{trigger} を実現するような戦略を全プレイヤーは選択する。
  2.  v_{trigger} から逸脱する戦略をプレイヤー  j が選択した場合、次回以降  j 以外のプレイヤーは  m_{-j} を選択し続ける。

ちなみに同時に2名以上のプレイヤーが  v_{trigger} から逸脱した場合は、1. を続行します。

誰も逸脱しない場合のプレイヤー  j の無限回繰り返しゲームの平均利得は  v_jとなります。

次に、プレイヤー  j が逸脱する場合、逸脱した回で多くの利得を得られはしますが、ゲームを無限に繰り返す場合は高々有限回数の利得が平均利得に与える影響は0となるため、プレイヤー  j の無限回繰り返しゲームの平均利得は  p_{min, j}となります。

 v p_{min} をパレート支配するので、明らかに   v_j \geq p_{min, j} です。プレイヤー  j v_{trigger} を逸脱するインセンティブを持ちません。

以上より、割引率が存在しない(= 常に1)場合のトリガー戦略が無限回繰り返しゲームのナッシュ均衡解かつパレート最適解となることが示されました。

*1:逆にプレイヤーの合理性に制限を加えるアプローチによってこの現象を説明する方法もあります。