ナッシュ均衡点の導出 Part1

大学数学

はじめに

ある程度のゲーム理論に関する用語は説明なしに使っていきます。何を言っているのかが全くわからないという方はある程度ゲーム理論の勉強をしてからのほうがいいと思います。

いちおう以下はこのブログで解説しているゲーム理論の記事です。よければ読んでください。

【経済学部必見】ゲーム理論入門 ~ナッシュ均衡点とは?~
はじめに ゲーム理論はとてもおもしろい分野で興味を持っている人も結構いると思います。しかし、検索してもちゃんと説明してくれている日本語の記事は少ないですね~。私も教科書や論文ほどがっつりは説明はしませんが、できるだけ深く、わかりやすく解説...

この記事ではナッシュ均衡点を求める方法の中でも最も有名なLemke-Howson algorithmを紹介します。かなり深い話になるので少しむずかしいかもしれませんが、完全に理解したときはもうゲーム理論上級者です!

前提

この記事では2人戦略系ゲームのみを考えます。プレイヤーは1と2とします。
\begin{align}
x &\cdots プレイヤー1の混合戦略 \\
y &\cdots プレイヤー2の混合戦略 \\
M &\cdots プレイヤー1が選びうる純戦略の集合 \\
N &\cdots プレイヤー2が選びうる純戦略の集合 \\
A &\cdots プレイヤー1の利得関数 \\
B &\cdots プレイヤー2の利得関数 \\
\end{align}

ナッシュ均衡点の性質

ナッシュ均衡点が満たすべき性質ってどんなものがあるのでしょうか?「囚人のジレンマ」はちょっと簡単すぎるので、「じゃんけんグリコ」を例に考えてみましょう。

2人でじゃんけんを行い、勝てば進むことができて先にゴールに辿り着いた方が勝ちというゲームです。じゃんけんに勝った際に、勝った手によって進める歩数は変わります。グーで勝った場合は「グリコ」と声に出しながら3歩、チョキで勝った場合は「チョコレート」と言いながら5歩、パーで勝った場合は「パイナップル」と言いながら6歩歩きます。(私の地元ではチョコレートは6文字なので6歩進んでいましたが、それは問題が面白くなくなるので5歩にしました。)損得表は以下の通りのなります。

Aさん、Bさんはそれぞれじゃんけんで何を出すのが正解なのでしょうか??

このナッシュ均衡点はAさんとBさんがグー、チョキ、パーをそれぞれ(5/21, 10/21, 2/7)の確率で出す戦略となります。この例をもとにナッシュ均衡点の必要十分条件を考えてみましょう。

Aさんが戦略を変更したときを考えてみましょう。Aさんはグー、チョキ、パーを選択する確率分布を\((a, b, c)\)に変更したと仮定しましょう。このときAさんがグー、チョキ、パーを選んだ際の歩数の期待値はそれぞれ
\begin{align}
\frac{10}{21}\times 3 = \frac{10}{7} \\
\frac{2}{7}\times 5 = \frac{10}{7} \\
\frac{5}{21}\times 6 = \frac{10}{7}
\end{align}
となります。つまりAさんがグー、チョキ、パーのどれを選択しようと得られる期待値は変わりません。実はナッシュ均衡点ってそういう点なのです!相手がナッシュ均衡点の戦略を選択したとき、自分はどの手を選択しても期待値は変わらないのです。相手がナッシュ均衡点に従う限り、自分はどんな戦略を取ろうがナッシュ均衡点で得られる以上の利得は得られない、しかし戦略を変更しても利得は下がることもないんですね。

期待値が変わらないんならAさんはどんな戦略をとってもいいんじゃないのか?それも間違っています。もしAさんがナッシュ均衡点以外の戦略を取るならば、Bさんはきっと戦略を変更すればより多くの利得が得られるでしょう。だからAさんはどんな戦略をとっても期待値が変わらないのならば、相手にもナッシュ均衡点を選択させるためにナッシュ均衡点に従うのが正しい選択となるのです!(少しややこしいですが頑張って理解してください笑)

では次に以下のようなシチュエーションを考えてみましょう。

勝手にじゃんけんに追加ルールを加えました。ヒットというのは最弱の手でどの手に対しても負けます(笑)このゲームにおいて(5/21, 10/21, 2/7, 0)はナッシュ均衡点の戦略になるのでしょうか??答えはYESです。相手が(5/21, 10/21, 2/7, 0)の戦略を取る限り、自分は(5/21, 10/21, 2/7, 0)以外の戦略をとってもナッシュ均衡点で得られる期待値以上の期待値は得ることはできません。

しかし、上ではナッシュ均衡点の戦略に対してはどの手を出しても期待値は変わらないんじゃないかと仮説を立てました。ここではグー、チョキ、パーを選択した際の期待値は10/7であるのに対し、ヒットを選択した際の期待値は0であるため、期待値は異なります。これでも良いのでしょうか?

実は付与されている確率が0の場合は期待値は異なっても良いのです!この場合だと、ナッシュ均衡点の戦略ではヒットが選ばれる期待値は0であるため、ヒットを選んだ際の期待値が他と異なろうが構わないというわけです。

さらにもう一つ考えてみます。

ストというのは最強の手で、どの手に対しても負けません!ではこのとき(5/21, 10/21, 2/7, 0)はナッシュ均衡点の戦略になるのでしょうか??

もちろんなりません。なぜならこの戦略は最強の手、ストを出す確率を0%にしているわけですから。もしAさんがストを出したときの歩数の期待値は\[6\times \frac{5}{21} + 5\times \frac{10}{21} + 3\times \frac{2}{7} = \frac{14}{3}\]で、グー、チョキ、パーを出したときに得られる期待値10/7を上回ります。つまり、100%ストを出す戦略の方が期待値は高くなるのです。

これから分かることはナッシュ均衡点における戦略は正の確率が付与されている手を出したときに得られる期待値は、全ての手を選択したときに得られる期待値の中で最大となるということです。

 

以上、ナッシュ均衡点がもつ性質を紹介しました。これをまとめるとナッシュ均衡点の必要十分条件は次のようになります。

全ての\(i \in M, j \in N\)で
\begin{align}
x_i > 0 &\Rightarrow (Ay)_i = u = \max\{(Ay)_k | k \in M\} かつ \\
y_j > 0 &\Rightarrow (Bx)_j = v = \max\{(Bx)_k | k \in N\}
\end{align}

もともとのナッシュ均衡点の定義からナッシュ均衡点を求めるためには、無限個ある混合戦略を考える必要があるためとてもむずかしい作業でした。
しかし、この性質を用いると有限個の純戦略の組み合わせからこの条件を満たす戦略を見つければよいのでかなり楽になりました。ではやっとナッシュ均衡点を求める方法を紹介していきましょう!

ナッシュ均衡点の導出方法1:サポートを用いた方法

まずはサポートの定義からですね。サポートの定義は以下のようになります。

混合戦略におけるサポートとは、正の確率をもつ純戦略の集合である。混合戦略におけるサポートの数はsupport(x)と表される。

つまり確率が0じゃない純戦略の集合ですね。混合戦略\(x = (5/21, 10/21, 2/7, 0)\)のサポートは(5/21, 10/21, 2/7)で、\(support(x) = 3\)となります。先ほどのナッシュ均衡点の必要十分条件とサポートを組み合わせて、以下のようなナッシュ均衡点を求めるアルゴリズムを作ることができます。

行っていることはさっきのナッシュ均衡点の必要十分条件を満たす純戦略の組を1つずつ全てをチェックしているだけです。しかしこれ、かなり時間がかかるのです。

例えば利得表が\(n\times n\)だったとしましょう。このとき、\(n\)個の戦略うち、正の確率を付与させる戦略の組み合わせは\(2^n\)通りであり、\(n\)が大きくなると組み合わせの個数は膨大な数となります。そのため、このアルゴリズムは余り賢い方法とは言えません。

ナッシュ均衡点の導出方法2:ラベルを用いた方法

まずは集合\(\overline{P}, \overline{Q}\)を定義します。

\begin{eqnarray*}
\overline{P} &=& \{(x, v) \in \mathbb{R}^d \times \mathbb{R} | x \geq \vec{0}, \vec{1}^{\mathrm{T}}x = 1, B^{\mathrm{T}}x \leq \vec{1}v \}, \\
\overline{Q} &=& \{(y, u) \in \mathbb{R}^d \times \mathbb{R} | y \geq \vec{0}, \vec{1}^{\mathrm{T}}y = 1, Ay \leq \vec{1}u \}
\end{eqnarray*}

この\(\overline{P},\overline{Q}\)を最適応答多面体と呼びます。\(v\)はプレイヤー1の任意の戦略\(x\)に対するプレイヤー2の利得の最大値です。\(u\)も同様なプレイヤー1の利得の最大値です。(ややこしかったらあまり考えなくても大丈夫です!)

簡単に言うと、これは各プレイヤーが取り得るの利得の期待値の集合なのです。

そしてこれを用いるとラベルを以下のように定義することができます。

\(\overline{Q}\)において、\(k \in M\cup N\)を満たす\(k\)が\(k \in M\)ならば\(\sum _{j \in N}a_{kj}y_j = u\)で\(k \in N\)ならば\(x_k = 0\)のとき、\(\overline{Q}\)の点\((y, u)\)はラベル\(k\)を持つという。\(\overline{P}\)においても同様。

意味を解釈してみましょう。

これは定義は簡単なのですが、なぜこれを定義するのかってところが難しいかもしれませんね。なぜこのラベルを定義するのか。実は\(\forall k \in M \cup N\)を満たすラベル\(k\)が\((x, v)\)または\((y, u)\)のいずれかのラベルに含まれているとき\((x, y)\)はナッシュ均衡点になるのです。つまり全ての純戦略がラベルに含まれるときにナッシュ均衡点となるのです。

次に多面体\(P, Q\)を定義します。
\begin{eqnarray*}
P &=& \{ x \in \mathbb{R}^M | x \geq \vec{0}, B^{\mathrm{T}}x \leq \vec{1}\}, \\
Q &=& \{ y \in \mathbb{R}^N | y \geq \vec{0}, Ay \leq \vec{1}\}
\end{eqnarray*}

つまり\(P, Q\)は\(\overline{P}\)と\(\overline{Q}\)の両辺を\(u\)と\(v\)で割って正規化した形ですね。この方が一般的で比較などがしやすいってわけです。

そしてなぜこの多面体を定義したのか!それは先ほど言ったナッシュ均衡点の性質とつながってくるわけです。細かい理論は置いといて結果だけいうと、\((x, y)\)がナッシュ均衡点ならば、\((x, y)\)は\(P, Q\)の頂点の組み合わせなのです。しかし、逆に\(P, Q\)の頂点の組み合わせが全てナッシュ均衡点となるかと聞かれればそれはNOです。

といっても多分イメージしづらいと思うので、具体例で考えてみましょう!

「コナンくん vs 怪盗キッド」というゲームで考えてみます。詳しくはこちら。

【経済学部必見】ゲーム理論入門 ~ナッシュ均衡点とは?~
はじめに ゲーム理論はとてもおもしろい分野で興味を持っている人も結構いると思います。しかし、検索してもちゃんと説明してくれている日本語の記事は少ないですね~。私も教科書や論文ほどがっつりは説明はしませんが、できるだけ深く、わかりやすく解説...

ここでは利得関数は以下のようになっています。

このとき、\(P, Q\)は以下のようになります。

図から分かるように\(P\)の頂点は\((0, 0), (0, 1/5), (1/15, 1/5), (1/15, 0)\)の4つで、\(Q\)の頂点は\((0, 0), (0, 1/10), (1/10, 1/10), (1/10, 0)\)の4つです。そしてこの問題のナッシュ均衡点における戦略は\((1/15, 1/5)\)と\((1/10, 1/10)\)を足して確率1になるように正規化した\((1/4, 3/4)\)と\(1/2, 1/2\)なのです。

しかし、\((0, 1/5)\)と\((1/10, 0)\)の組み合わせなどはナッシュ均衡点にはなりません。つまり、全てのナッシュ均衡点は\(P\)から頂点を1つ、\(Q\)から頂点を1つ選んだ組み合わせで表すことができ、しかし\(P\)から頂点を1つ、\(Q\)から頂点を1つ選んだ組み合わせは全てナッシュ均衡点となるわけではないのです。(さっきよりイメージできたかな?笑)

 

そしてこの性質を用いると次のようなナッシュ均衡点を求めるアルゴリズムが導かれます。

vertexってのはこの多面体の頂点のことです。

しかしこれでも結構時間がかかってしまいます‥頂点の数は例では2次元であったので4つずつでしたが、これが3次元、4次元となるとかなり多くなってしまいます。

そこでこのアルゴリズムをさらに応用したアルゴリズムが次に説明するLemke-Howson algorithmです!でももう説明長くなりすぎましたね(笑)結構省略したんですけどそれでも長くなってしまいます。てことで次の記事に持ち越します~!

ナッシュ均衡点の導出 Part2
以前の記事の続きです。先にこれ読んだ方がわかりやすいと思います! ナッシュ均衡点の導出方法3:Lemke-Howson algorithm これまでに2つのナッシュ均衡点の導出方法を紹介しましたが、どちらも全てのナッシュ...

コメント

タイトルとURLをコピーしました