行列ゲーム

2017-06-17 (Sat.)

ゲーム理論

index

行列ゲームとは何か
ゼロ和ゲームとは何か
純粋戦略
混合戦略
双行列ゲーム (非ゼロ和ゲーム)
ナッシュ均衡 (非協力均衡点)
参考文献リスト

行列ゲームとは何か

ここでは次のようなゲームを考える.

プレイヤーは2人
プレイヤー $1, 2$ に対し、戦略の選択肢の集合 $I, J$ がある
- $I, J$ は有限集合 - $I = {1, 2, \dots, | I |}$ , $J = {1, 2, \dots, | J |}$ とする
プレイヤー $k$ に対し 利得関数 $f_{k}$ がある
- $f_{1} : I \times J \to R$
- $f_{2} : I \times J \to R$
- これを評価関数や損失関数と呼んだりする
プレイヤー $1$ は $max f_{1} (i, j)$ を目指して戦略 $i (\in I)$ を選び、プレイヤー $2$ は同様に $max f_{2} (i, j)$ を目指して戦略 $j$ を選ぶ
互いのプレイヤーは相手のプレイヤーの戦略を知ることはできない

特に最後のルールが特別で、同時に (唯一つの) 手を見せ合ってポイントを分け合うようなゲームを考えている.

ゼロ和ゲームとは何か

互いの利得関数の和が常にゼロであるようなゲーム:

\forall i, j . f_{1} (i, j) + f_{2} (i, j) = 0

のことを ゼロ和ゲーム という. 後述するが (実は) ゼロでなく定数であっても本質は変わらない (戦略的同値) ので、そういう場合もゼロ和ゲームという.

とりあえずは利得の和がゼロになるようなゼロ和ゲームだけのことを考える.

$a_{i j} = f_{1} (i, j) = - f_{2} (i, j)$ とすると、行列 $(a_{i j})$ が描けて、これを利得行列という. プレイヤー $1, 2$ はそれぞれ、

プレイヤー $1$ : $max_{i} a_{i j}$
プレイヤー $2$ : $min_{j} a_{i j}$

を目指す.

単に行列ゲームという時、ゼロ和ゲームのことを指し、利得行列 $A = (a_{i j})$ のことを言う.

純粋戦略

互いに相手の手は分からないが、お互い最善を尽くして戦略を考えることを仮定して戦略を考える. 適当な考えの下で、唯一つの戦略を選択することを 純粋戦略 と言う. (実際にプレイできる戦略はただ一つなのだから唯一つの戦略を選択するのは当たり前に思える.)

純粋戦略のミニマックス原理

ゼロ和ゲームの純粋戦略を考える. ゼロ和では相手の最善は自分の最悪であるので、相手は自分にとって常に悪い手を取ると考えたほうが良い. 具体的には、相手が自分にとって最悪の手を取ったとしても最もマシな利得が得られるような戦略を考える.

例えば次のような利得行列について

A = (\begin{array}{ccc} 1 & 1 & - 1 \\ 2 & - 2 & 0 \\ 1 & 1 & - 2 \end{array})

プレイヤー $1$ が 1 を選ぶとき、第 $1$ 行ベクトル

a_{1 \cdot} = (\begin{array}{ccc} 1 & 1 & - 1 \end{array})

が選ばれる. プレイヤー $1$ にとっての最悪の事態とはこの中の最小が選ばれることで、すなわちプレイヤーが $3$ を選ぶことによって利得

a_{13} = - 1

が得られることである.

同様に、 $2$ を選んだ場合は

a_{22} = - 2

が最悪. $3$ を選んだ場合は

a_{33} - 2

が最悪.

というわけで $1$ を選んでいれば、最低でも $- 1$ の利得が得られることが分かるので、最もマシな純粋戦略は $1$ だということが分かる.

以上のようにプレイヤー $1$ の指針は

max_{i} min_{j} a_{i j}

によって $i$ を選ぶこと.

逆も同様で、プレイヤー $2$ の指針は

min_{j} max_{i} a_{i j}

によって $j$ を選ぶこと.

定義

利得行列 $(a_{i j})$ について

max_{i} min_{j} a_{i j} = min_{j} max_{i} a_{i j} (= v)

が成立するとき、このゲームは厳密に決定されるといい、これが成立する $i, j$ を $i^{*}, j^{*}$ と書いて、 $(i^{*}, j^{*})$ を 均衡点 という. 均衡点が存在するときに $v$ を ゲームの値 という.

定理

実行列 $(a_{i j})$ について

max_{i} min_{j} a_{i j} \leq min_{j} max_{i} a_{i j}

が常に成り立つ.

証明

$v_{1} = max_{i} min_{j} a_{i j}$ とおく. この値は行列 $(a_{i j})$ の各行ベクトルの最小値の最大値. すなわち、ある第 $i$ 行目において、成分の値は全て $v_{1}$ 以上. これがあるので、各列ベクトルにおける最大値は $v_{1}$ 以上. 列ベクトルの最大値の最小値も $v_{1}$ 以上. それはまさに $v_{2} = min_{j} max_{i} a_{i j}$ のことである. というわけで $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 = (\begin{array}{ccc} 0 & 1 & - 1 \\ - 1 & 0 & 1 \\ 1 & - 1 & 0 \end{array})

マックスミニ値 $(v_{1} = max_{i} min_{j} a_{i j})$ は $- 1$ でミニマックス値 $(v_{2} = min_{j} max_{i} a_{i j})$ は $1$ である. もちろん鞍点も存在しない.

これが純粋戦略の限界.

混合戦略

純粋戦略がまずかったのは確定的に唯一つの戦略を選ぼうとしたことだった. 次は複数の戦略を混ぜることを考える. すなわち、戦略集合の上の確率分布を戦略だと考えこれを 混合戦略 と呼ぶ.

戦略集合 $I$ に対して

$p = (p_{i} : i \in I, p_{i} > 0)$
$\sum_{i} p_{i} = 1$

このような行ベクトル $p$ が混合戦略.

実際に戦略を選択する場合に、 $p$ に従って $i \in I$ を選択してプレイする. 何度も繰り返しプレイする場合は明らかにこの混合戦略の考え方が有効そうだが、ただ一回きりのプレイにおいても (あなたが期待値というものを信用するのなら) 有効な考え方である. また純粋戦略は混合戦略の特別な場合 (ある $i$ についてのみ $p_{i} = 1$ なる混合戦略) だと言える.

利得行列 $(a_{i j})$ の代わりにその期待値、 期待利得 $E$ というものを考えるべきである. プレイヤー $1, 2$ が混合戦略 $p, q$ を取る場合の期待利得は

E (p, q) = \sum_{i} \sum_{j} p_{i} q_{i} a_{i j}

と計算できる.

ところで $p, q$ を行ベクトルとして定義してるのでこれは

E (p, q) = p A q^{T}

とも書ける ( $A = (a_{i j})$ ).

略記法として、 $E$ の引数に $I, J$ を渡すことを許して

E : I \times Q \to R

E (i, q) = \sum_{j} q_{j} a_{i j}

E : P \times J \to R

E (p, j) = \sum_{i} p_{i} a_{i j}

も定義する. $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) = p A q^{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{aligned} 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{aligned}

だから $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} p A q^{T} = min_{q} max_{p} p A q^{T}

が常に成立する.

証明

後でより一般的な場合 (双行列ゲーム) で示す.

対称行列

利得行列が歪対称行列になっている、すなわち

A = - A^{T}

となるような行列ゲームを 対称行列 という. 歪対称行列の特性として正方行列であること. 従って2人のプレイヤーの取れる戦略は同じ集合だと見なせる. また対角成分はゼロである. 例えばじゃんけんが対称ゲームの例である.

定理

対称ゲームのゲームの値はゼロである.

証明

ミニマックス定理からゲームの解 $((p^{*}, q^{*}), v)$ の存在は保証されている.

これが解であることと同値な条件は前述した鞍点定理から、任意の $p, q$ について

p A q^{* T} \leq p^{*} A q^{* T} \leq p^{*} A q^{T}

が成立することであった.

これの各項の転置を取って

q^{*} A^{T} p^{* T} \leq q^{*} A^{T} p^{* T} \leq q A^{T} p^{* T}

$A^{T} = - A$ を代入して

q^{*} A p^{* 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つ必要である. 従って双行列で管理する.

プレイヤー $1$ の利得: $f_{1} (i, j)$
プレイヤー $2$ の利得: $f_{2} (i, j)$

に対して、

$n \times m$ 行列 $A = (a_{i j} = f_{1} (i, j))$
$n \times m$ 行列 $B = (b_{i j} = f_{2} (i, j))$

ゼロ和ゲームでは $B = - A$ という関係があったので単に $A$ だけを持っていれば良かったが今は2つを持っておく. 2つの行列のタプル、または成分を2つの成分のタプルにした行列を双行列という.

(A, B) = ((a_{i j}, b_{i j}))

これによって表現される2人非ゼロ和ゲームを 双行列ゲーム (bimatrix game) という. 初めに説明した行列ゲームの1つだとして、同様に

プレイヤー $1$ は $max f_{1} (i, j)$ を目指して戦略 $i$ を選び、プレイヤー $2$ は同様に $max f_{2} (i, j)$ を目指して戦略 $j$ を選ぶ
互いのプレイヤーは相手のプレイヤーの戦略を知ることはできない

これらを仮定する. またプレイ (各々が戦略を選ぶ行為) は一回きりのものとする.

例. 囚人のジレンマ

囚人のジレンマ [^1] は双行列ゲームの典型例. 参考文献の Wikipedia では懲役年数が行列になっているが今は最大化を目標にしたいので、これのマイナスを利得だと思えば良い.

(A, B) = [\begin{array}{cc} (- 2, - 2) & (- 10, 0) \\ (0, - 10) & (- 5, - 5) \end{array}]

ジレンマの囚人のストーリーではこの一列一行目のことを「協力」、二列二行目のことを「裏切り」などとして説明されている.

ところで囚人のジレンマは $(2, 2)$ 成分 (二人共裏切り) に落ち着くしか無い. なぜなら、相手がどちらの戦略を選択するにしても、自分は裏切りを選択したほうが利得が上がるからである ( $- 2 \mapsto 0; - 10 \mapsto - 5$ ).

ナッシュ均衡 (非協力均衡点)

基本的には今まで言ってた均衡点と同じ概念.

$f_{1}, f_{2}$ の引数に混合戦略を渡すことを許して期待利得を表現する.

2人の混合戦略の集合 $P, Q$ のある点 $(p^{*}, q^{*})$ が ナッシュ均衡 であるとは

$f_{1} (p^{*}, q^{*}) = max_{p} f_{1} (p, q^{*})$
$f_{2} (p^{*}, q^{*}) = max_{q} f_{2} (p^{*}, q)$

を満たすこと. また $v = (f_{1} (p^{*}, q^{*}), f_{2} (p^{*}, q^{*}))$ を 均衡利得 という.

最適反応

今考えるゲームは相手の手を知らずに自分の手を決めているが、仮に、相手の戦略を知ってから自分の最適な戦略を考えるとする.

プレイヤー $1$ の 最適反応 とはプレイヤー $2$ が用いる混合戦略 $q$ に対する最適戦略の集合のことで $R_{1} (q)$ と書く. 同様にプレイヤー $2$ の最適反応はプレイヤー $1$ の混合戦略 $p$ に対して $R_{2} (p)$ と書く.

具体的な定義は大体分かるでしょうけど

$R_{1} (q) = {p : f_{1} (p, q) = max_{p} f_{1} (p, q)}$
$R_{2} (p) = {q : f_{2} (p, q) = max_{q} f_{2} (p, q)}$

明らかにナッシュ均衡 $(p^{*}, q^{*})$ について

$p^{*} \in R_{1} (q^{*})$
$q^{*} \in R_{2} (p^{*})$

ということ.

定理

$(p^{*}, q^{*})$ がナッシュ均衡であることと、写像 $T (p, q) = (R_{1} (q), R_{2} (p))$ の不動点であることは同値.

最適反応の定義から明らか.

また次のように言い換えることも出来る.

定理

ナッシュ均衡の集合 $D = {(p^{*}, q^{*})}$ 及び最適反応の集合

$D_{1} = {(p, q) : p \in R_{1} (q), q \in Q}$
$D_{2} = {(p, q) : q \in R_{2} (p), p \in P}$

を用いて

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 の不動点定理ってのと組み合わせると出来るらしいけどわからん.

参考文献リスト

[^1] : 囚人のジレンマ - Wikipedia