2017-06-17 (Sat.)
ここでは次のようなゲームを考える.
特に最後のルールが特別で、同時に (唯一つの) 手を見せ合ってポイントを分け合うようなゲームを考えている.
互いの利得関数の和が常にゼロであるようなゲーム: \[\forall i, j .~ f_1(i, j) + f_2(i, j) = 0\] のことを ゼロ和ゲーム という. 後述するが (実は) ゼロでなく定数であっても本質は変わらない (戦略的同値) ので、そういう場合もゼロ和ゲームという.
とりあえずは利得の和がゼロになるようなゼロ和ゲームだけのことを考える.
\(a_{ij} = f_1(i, j) = - f_2(i, j)\) とすると、行列 \((a_{ij})\) が描けて、これを利得行列という. プレイヤー \(1, 2\) はそれぞれ、
を目指す.
単に行列ゲームという時、ゼロ和ゲームのことを指し、利得行列 \(A=(a_{ij})\) のことを言う.
互いに相手の手は分からないが、お互い最善を尽くして戦略を考えることを仮定して戦略を考える. 適当な考えの下で、唯一つの戦略を選択することを 純粋戦略 と言う. (実際にプレイできる戦略はただ一つなのだから唯一つの戦略を選択するのは当たり前に思える.)
ゼロ和ゲームの純粋戦略を考える. ゼロ和では相手の最善は自分の最悪であるので、相手は自分にとって常に悪い手を取ると考えたほうが良い. 具体的には、相手が自分にとって最悪の手を取ったとしても最もマシな利得が得られるような戦略を考える.
例えば次のような利得行列について \[A = \left(\begin{array}{ccc} 1 & 1 & -1 \\ 2 & -2 & 0 \\ 1 & 1 & -2 \\ \end{array}\right)\] プレイヤー \(1\) が 1 を選ぶとき、第\(1\)行ベクトル \[a_{1\cdot} = \left(\begin{array}{ccc} 1 & 1 & -1 \\ \end{array}\right)\] が選ばれる. プレイヤー \(1\) にとっての最悪の事態とはこの中の最小が選ばれることで、すなわち プレイヤーが \(3\) を選ぶことによって利得 \[a_{13} = -1\] が得られることである.
同様に、\(2\) を選んだ場合は \[a_{22}=-2\] が最悪. \(3\) を選んだ場合は \[a_{33}-2\] が最悪.
というわけで \(1\) を選んでいれば、最低でも \(-1\) の利得が得られることが分かるので、最もマシな純粋戦略は \(1\) だということが分かる.
以上のようにプレイヤー \(1\) の指針は \[\max_i \min_j a_{ij}\] によって \(i\) を選ぶこと.
逆も同様で、プレイヤー \(2\) の指針は \[\min_j \max_i a_{ij}\] によって \(j\) を選ぶこと.
利得行列 \((a_{ij})\) について \[\max_i \min_j a_{ij} = \min_j \max_i a_{ij} ~~(=v)\] が成立するとき、このゲームは厳密に決定されるといい、これが成立する \(i, j\) を \(i^*, j^*\) と書いて、\((i^*, j^*)\) を 均衡点 という. 均衡点が存在するときに \(v\) を ゲームの値 という.
実行列 \((a_{ij})\) について \[\max_i \min_j a_{ij} \leq \min_j \max_i a_{ij}\] が常に成り立つ.
\(v_1 = \max_i \min_j a_{ij}\) とおく. この値は行列 \((a_{ij})\) の各行ベクトルの最小値の最大値. すなわち、ある第 \(i\) 行目において、成分の値は全て \(v_1\) 以上. これがあるので、各列ベクトルにおける最大値は \(v_1\) 以上. 列ベクトルの最大値の最小値も \(v_1\) 以上. それはまさに \(v_2 = \min_j \max_i a_{ij}\) のことである. というわけで \(v_1 \leq v_2\) が成立する.
ゲームが厳密に定まらないような行列ゲームはいくらでもある. 厳密に定まるかどうかを判定するための定理がある.
利得行列に鞍点があることが厳密に定まることの必要十分条件.
ここで鞍点とはある \((i^*, j^*)\) のことで, \[\forall i, j .~ a_{i j^*} \leq a_{i^* j^*} \leq a_{i^* j}\] が成立する点のこと. 鞍点があるとき、明らかにその鞍点自体が均衡点となる.
証明は地道に確かめるだけなので略.
鞍点として \((i_1, j_1)\) と \((i_2, j_2)\) とがあるとき、 \((i_1, j_2)\) と \((i_2, j_1)\) もまた鞍点である.
さてゲームが厳密に定まらない、すなわち鞍点が存在しない例としてじゃんけんがある. \[A = \left(\begin{array}{ccc} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{array}\right)\]
マックスミニ値 \((v_1 = \max_i \min_j a_{ij})\) は \(-1\) でミニマックス値 \((v_2 = \min_j \max_i a_{ij})\) は \(1\) である. もちろん鞍点も存在しない.
これが純粋戦略の限界.
純粋戦略がまずかったのは確定的に唯一つの戦略を選ぼうとしたことだった. 次は複数の戦略を混ぜることを考える. すなわち、戦略集合の上の確率分布を戦略だと考えこれを 混合戦略 と呼ぶ.
戦略集合 \(I\) に対して
このような行ベクトル \(p\) が混合戦略.
実際に戦略を選択する場合に、\(p\) に従って \(i \in I\) を選択してプレイする. 何度も繰り返しプレイする場合は明らかにこの混合戦略の考え方が有効そうだが、ただ一回きりのプレイにおいても (あなたが期待値というものを信用するのなら) 有効な考え方である. また純粋戦略は混合戦略の特別な場合 (ある \(i\) についてのみ \(p_i=1\) なる混合戦略) だと言える.
利得行列 \((a_{ij})\) の代わりにその期待値、 期待利得 \(E\) というものを考えるべきである. プレイヤー \(1, 2\) が混合戦略 \(p, q\) を取る場合の期待利得は \[E(p, q) = \sum_i \sum_j p_i q_i a_{ij}\] と計算できる.
ところで \(p, q\) を行ベクトルとして定義してるのでこれは \[E(p, q) = p A q^T\] とも書ける (\(A = (a_{ij})\)).
略記法として、\(E\) の引数に \(I, J\) を渡すことを許して \[E : I \times \mathcal{Q} \to \mathbb{R}\] \[E(i, q) = \sum_j q_j a_{ij}\] \[E : \mathcal{P} \times J \to \mathbb{R}\] \[E(p, j) = \sum_i p_i a_{ij}\] も定義する. \(E(p, q) = \sum_i p_i E(i, q) = \sum_j q_j E(p, j)\) である.
純粋戦略の時と同様にミニマックス原理を混合戦略に当てはめる. すなわち、 プレイヤー \(1\) は \[v_1 = \max_p \min_q E(p, q)\] を指標にし、プレイヤー \(2\) は \[v_2 = \min_q \max_p E(p, q)\] を指標にする. また同様に \[\max_p \min_q E(p, q) = \min_q \max_p E(p, q) ~~(=v)\] のとき、\(v\) をゲームの値といい、そのときの \((p, q)\) を \((p^*, q^*)\) と書いて最適戦略と呼ぶ. これら \(((p^*, q^*), v)\) をまとめてゲームの解などという.
純粋戦略のときに成立する性質がほぼほぼ成り立つことを見ていく.
\(E(p,q) = pAq^T\) について \[\max_p \min_q E(p, q) \leq \min_q \max_p E(p, q)\]
純粋戦略のときと全く同様.
最適戦略が \((p^*, q^*)\) であることは次と同値. \[\forall p, q .~ E(p, q^*) \leq E(p^*, q^*) \leq E(p^*, q)\]
純粋戦略のときは鞍点の存在として紹介した.
\((\Rightarrow)\) \((p^*, q^*)\) が最適戦略だとする.
仮に \(E(p, q^*) > E(p^*, q^*)\) とすると \(E(p^*, q^*) = \max_p \min_q E(p, q)\) に矛盾し、\(p^*\) の代わりに \(p\) を使ったほうがより最適になる. 従って、 \(E(p, q^*) \leq E(p^*, q^*)\). \(q\) についても同様.
\((\Leftarrow)\) \(E(p, q^*) \leq E(p^*, q^*)\) とは \[\max_p E(p, q^*) = E(p^*, q^*)\] ということ. そして一般に \[\min_q \max_p E(p, q) \leq \max_p E(p, q^*)\] は成立するので、\(q\) についても同様に考えると \[\min_q \max_p E(p, q) \leq (E(p^*, q^*) \leq) \max_p \min_q E(p, q)\] が得られる.
先の補題と組み合わせると \[\min_q \max_p E(p, q) = (E(p^*, q^*) =) \max_p \min_q E(p, q)\] を得る.
最適戦略として \((p_1, q_1)\) と \((p_2, q_2)\) とがあるとき、 \((p_1, q_2)\) と \((p_2, q_1)\) もまた最適戦略である.
混合戦略の場合、確率分布どうしの鞍点みたいなものを探す必要がありそうだが、次の定理によって、もう少し探索範囲が小さくできる.
ゲームの解が \(((p^*, q^*), v)\) であることは次と同値. \[\forall i, j .~ E(i, q^*) \leq v \leq E(p^*, j)\]
すなわち、混合戦略 vs 純粋戦略での利得だけを考慮すればよい.
先ほどの定理から \[\forall p, q .~ E(p, q^*) \leq v \leq E(p^*, q)\] と同値であることは言える.
\(\max_i E(i, q^*)\) を考えた時、そのような \(i\) が \(i_0\) とすると、 \(\max_p E(p, q^*) = E(i_0, q^*)\) である (すなわち \(p_{i_0} = 1\)).
なぜなら \(p_{i_0} < 1\) とする \(p'\) を用いると、 \[\begin{align*} E(i_0, q^*) - E(p', q^*) & = E(i_0, q^*) - \sum_i p'_i E(i, q^*) \\ & \geq E(i_0, q^*) - \sum_i p'_i E(i_0, q^*) \\ & = E(i_0, q^*) - E(i_0, q^*) \\ & = 0 \end{align*}\] だから \(E(i_0, q^*) \geq E(p', q^*)\) を得る. 当たり前.
つまり \(\max_p E(p, q^*) = \max_i E(i, q^*)\) である.
というわけで、 \(\forall p. E(p, q^*) \leq v\) は \(\forall i. E(i, q^*) \leq v\) と言い換えても構わない.
どういうに \(q\) も \(j\) で言い換えられる.
ゲームの解が \(((p^*, q^*), v)\) であるとき、 \[\max_i E(i, q^*) = v = \min_j E(p^*, j)\]
で、重要な次の定理がある.
任意の行列ゲームに対して必ず解が存在する.
つまり実行列 \(A\) に対して \[\max_p \min_q pAq^T = \min_q \max_p pAq^T\] が常に成立する.
後でより一般的な場合 (双行列ゲーム) で示す.
利得行列が歪対称行列になっている、すなわち \[A = -A^T\] となるような行列ゲームを 対称行列 という. 歪対称行列の特性として正方行列であること. 従って2人のプレイヤーの取れる戦略は同じ集合だと見なせる. また対角成分はゼロである. 例えばじゃんけんが対称ゲームの例である.
対称ゲームのゲームの値はゼロである.
ミニマックス定理からゲームの解 \(((p^*, q^*), v)\) の存在は保証されている.
これが解であることと同値な条件は前述した鞍点定理から、任意の \(p, q\) について \[pAq^{*T} \leq p^*Aq^{*T} \leq p^*Aq^T\] が成立することであった.
これの各項の転置を取って \[q^*A^Tp^{*T} \leq q^* A^T p^{*T} \leq q A^T p^{*T}\]
\(A^T=-A\) を代入して \[q^*Ap^{*T} \geq q^* A p^{*T} \geq q A p^{*T}\]
鞍点定理より、\((q^*, p^*)\) もまた最適戦略であることが示された. 即ち、プレイヤー \(1\) にとっての最適戦略はプレイヤー \(2\) にとってもそのまま最適戦略となっており、逆も然りであることが分かる. 各プレイヤーの最適戦略の集合というものを考えた時、対称ゲームにおいてそれらは一致する.
というわけで、ゲームの値は \[v = p^* A q ^{*T} = q^* A p^{*T}\] となる. 最後のを転置すると \[v (= v^T) = (q^* A p^{*T})^T = p^* A^T q^{*T} = - p^* A q^{*T} = - v\] 従って \[v=0\] を得る.
プレイヤー2人の利得の和がゼロ (或いは、定数) とは限らないゲームを考える. 2種類の利得を管理する必要があるので行列は2つ必要である. 従って双行列で管理する.
に対して、
ゼロ和ゲームでは \(B = -A\) という関係があったので単に \(A\) だけを持っていれば良かったが今は2つを持っておく. 2つの行列のタプル、または成分を2つの成分のタプルにした行列を双行列という. \[(A, B) = \left( (a_{ij}, b_{ij}) \right)\]
これによって表現される2人非ゼロ和ゲームを 双行列ゲーム (bimatrix game) という. 初めに説明した行列ゲームの1つだとして、同様に
これらを仮定する. またプレイ (各々が戦略を選ぶ行為) は一回きりのものとする.
囚人のジレンマ 1 は双行列ゲームの典型例. 参考文献の Wikipedia では懲役年数が行列になっているが今は最大化を目標にしたいので、これのマイナスを利得だと思えば良い. \[(A, B) = \left[\begin{array}{cc} (-2, -2) & (-10, 0) \\ (0, -10) & (-5, -5) \end{array}\right]\]
ジレンマの囚人のストーリーではこの一列一行目のことを「協力」、二列二行目のことを「裏切り」などとして説明されている.
ところで囚人のジレンマは \((2,2)\) 成分 (二人共裏切り) に落ち着くしか無い. なぜなら、相手がどちらの戦略を選択するにしても、自分は裏切りを選択したほうが利得が上がるからである (\(-2 \mapsto 0; -10 \mapsto -5\)).
基本的には今まで言ってた均衡点と同じ概念.
\(f_1, f_2\) の引数に混合戦略を渡すことを許して期待利得を表現する.
2人の混合戦略の集合 \(\mathcal{P}, \mathcal{Q}\) のある点 \((p^*, q^*)\) が ナッシュ均衡 であるとは
を満たすこと. また \(v = (f_1(p^*, q^*), f_2(p^*, q^*))\) を 均衡利得 という.
今考えるゲームは相手の手を知らずに自分の手を決めているが、仮に、相手の戦略を知ってから自分の最適な戦略を考えるとする.
プレイヤー \(1\) の 最適反応 とはプレイヤー \(2\) が用いる混合戦略 \(q\) に対する最適戦略の集合のことで \(R_1(q)\) と書く. 同様にプレイヤー \(2\) の最適反応はプレイヤー \(1\) の混合戦略 \(p\) に対して \(R_2(p)\) と書く.
具体的な定義は大体分かるでしょうけど
明らかにナッシュ均衡 \((p^*, q^*)\) について
ということ.
\((p^*, q^*)\) がナッシュ均衡であることと、 写像 \(T(p, q) = (R_1(q), R_2(p))\) の不動点であることは同値.
最適反応の定義から明らか.
また次のように言い換えることも出来る.
ナッシュ均衡の集合 \(D=\{(p^*, q^*)\}\) 及び最適反応の集合
を用いて \[D = D_1 \cap D_2\] が言える.
ここらへんの定理を用いて、頑張ってナッシュ均衡が求められる.
行列ゲームのときと同様の言い方も出来る.
双行列ゲームについて \((p^*, q^*)\) がナッシュ均衡であることは次の同値.
任意の \(p, q\) に対して \[f_1(p^*, q^*) \geq f_1(p, q^*)\] \[f_2(p^*, q^*) \geq f_2(p^*, q)\]
\(B=-A\) を代入して以前の鞍点定理が出てくる.
前回も混合戦略と純粋戦略を比較すればよかったように、今回もそれが成り立つ.
双行列ゲーム \((A, B)\) について \((p^*, q^*)\) がナッシュ均衡であることは次の同値.
任意の \(p, q\) に対して \[\forall i .~ f_1(p^*, q^*) \geq f_1(i, q^*)\] \[\forall j .~ f_2(p^*, q^*) \geq f_2(p^*, j)\]
双行列ゲームは均衡点を1つ以上持つ.
もちろんゼロ和ゲームは双行列ゲームの特別な場合だから、これが成り立つなら先ほどのミニマックス定理が示されたことに成る.
証明は2つ前の不動点で均衡点を表現する定理を使う. なんか Brower の不動点定理ってのと組み合わせると出来るらしいけどわからん.