最適化理論/ゲーム理論
提供: Internet Web School
ゲーム理論の概要は
ゲーム理論(Wikipedia)
に書かれている. ここでは,例を2つあげて説明する.
鞍点のある問題
教育熱心な父親と,遊び盛りの息子がいる. この父親,ご多分に洩れず仕事の疲れがたまり,日曜は昼寝することが多いが,子煩悩で息子の勉強も気になる.
息子にしてみれば,日曜日に頼みもしないのに,父親に小言を言われながら―父親にしてみれば指導なのですが―勉強させられるのは最悪である.
鬱陶しい」が父親が起きていても,時間を稼ぎながら話題をはぐらかして,なんとか家でゲームでもした方がましと考えている.
父親が大人しく昼寝してくれて,こっそり抜け出すことができれば友人の家にでもゲームでもしに行くのだが,それができなくても,溜まった宿題を一人で片付けるほうがまだましと考えている.
父親は「昼寝をする.しない.」息子は「勉強する.遊ぶ.」でそれぞれ「戦略」に選択肢がある.
そこで,二人に「戦略」の選択によってかわる利害得失を下のように単純化して表にしてみる.
<利得表1>
この表の値は,息子の側に立ったものである.父親が昼寝しないで「指導」を受けながら勉強する最悪な場合は得点-50点
何とか,はぐらかしながら,遊ぶ場合は あまり楽しめないが50点,父親が昼寝して,一人で勉強して,溜まっている宿題 を片付けるのは0点,こっそり抜け出して遊ぶ場合は100点である.
父親にしてみれば
「昼寝する」を選択したら,自分の失点(息子の得点)は最大100点
「昼寝しない」選択したら,自分の失点(息子の得点)は最大50点
この二つの最大失点のうち最小のものは50点である.
息子にしてみれば
「勉強する」を選択したら自分の得点は最小-50点
「遊ぶ」を選択したら自分の得点は最小50点
この二つの最小得点のうち,最大ものは50点である.
この例では
最大失点のうち,最小のもの」=「最小得点のうち,最大もの」
が成立っている.
結局,父親が昼寝をしなければ,父親にとっては,最悪でも息子の得点は50点
息子にしてみれば,「遊ぶ」を選択したら最悪でも自分の得点は50点 である.このような状況を「このゲームには鞍点がある」という.
この話を一般化しておく.
二人の競技者P,Qが取り得る「戦略」の集合をPO,QOとする.
この二人がそれぞれ「戦略」の集合PO,QOの中から戦略P,Qを選択したときの 得点をG(P,Q)で表しておく.
上の例では,P=息子,Q=父親で,PO={勉強する,遊ぶ} QO={昼寝する,昼寝しない}である.
G(P,Q)は上の利得表1で与えらる.
PがPOの中から選択されるとQはこれに対抗して
G(P,Q)が最小になるように (自分の損失が最小になるように) QをQO中で選択するはずである.
すなわち
min{G(P,Q)|Q∈QO}
が実現されるとなるようなQをQOの中で探す.
この最小値をminQG(P,Q) で表しておく.
Pはこれを見越して,自分の利益が最大になるようにするため,
max{minQG(P,Q)|P∈PO}
が実現されるとなるようなPをPOの中から探すことになる.
この最大値を
maxPminQG(P,Q)
で表しておく.
まっく逆のQの立場からは, QがQOの中から選択されるとPはこれに対抗して
G(P,Q)が最大になるように PをP0中で選択するはずである. すなわち
max{G(P,Q)|P∈PO}
が実現されるとなるようなPをPOの中から探す. この最小値を
minPG(P,Q)
で表しておく.
Qはこれを見越して,自分の損失を最小にするため,
min{maxPG(P,Q)|Q∈QO}
が実現されるとなるようなQをQ0の中で探すことになる.
この最大値を
minQmaxPE(P,Q)
で表しておく.
以上出てきた,2つの値には一般には
maxPminQG(P,Q)≤minQmaxPG(P,Q)
という関係が成り立っている.
この不等式の導出は以下による.
まずQをQOの中で動かして,
minQG(P,Q)≤G(P,Q)
が任意のP(両辺),Q(右辺)について成立
次に上の不等式の右辺についてPをP0中で動かして,
minQG(P,Q)≤maxPG(P,Q)
が任意のP(左辺),Q
(右辺)について成立
さらに上の不等式の左辺についてPをPOの中で動かして,
maxPminQG(P,Q)≤maxPG(P,Q)
が任意のQ(右辺)について成立
最後に右辺のQをQOの中で動かして
maxPminQG(P,Q)≤minQmaxPG(P,Q)
である.
特に「鞍点」が存在する場合,戦略P∗∈PO,Q∗∈QOが存在して
maxPminQG(P,Q)=G(P∗,Q∗)=minQmaxPG(P,Q)
となる. この場合,競技者P,Qはそれぞれ戦略P∗∈PO,Q∗∈QO 以外の戦略を選択すると損をすることになり,この意味で平衡状態になる.
(図2.1 鞍点)
鞍点のない問題
P,Qの2人がじゃんけんをする. 負けたら10円を相手に払い,勝ったら相手から10円貰うというルールで, じゃんけんを繰り返す.
無論,「アイコ」の場合は,支払うお金,貰うお金とも0円である.
PとQの出す手によって,貰えるお金,支払うお金がどうなるか, Pの立場で以下のような表になる.
「-10」はQに10円払う事を表す. Pの立場に立ってみる.先ず,このゲームの利得表には鞍点がない. 双方が選択の余地のない「平衡状態」にする戦略はないわけである.出す手をランダムしてゲームを繰り返す方法以外ない. このような問題を混合戦略問題とう. じゃんけんを繰り返すわけであるが,どのような「戦略」があるか?
グーを出し続けとすると,Qはそれを直ぐ見破って, パーを出し続けてくるであろう.続ければ続けるほどPは大損である. 同様にパーを出し続けても,チョキを出し続けるのも駄目である.
結局,例えばサイコロを用意して,出た目によって出す手を決めるランダムな手の繰り返す方法であろう.
(1か6ならグー,2か5ならパー,3か4ならチョキなど)
問題は,どんな割合で(確率で)グー,チョキ,パーを出すべきかである. 相手のQはPの出す手を監視しながらPと対戦するので,Pが選択したグー,チョキ,パーの確率を直ぐに見破り, それでも,自分にとって有利な手を選択してくると考えるべきである.PとQの立場を替えても全く同じである.
ゲームの理論を創始し,この種の問題に解を与えたのが,ノイマン(vonNuemann 現在の計算機の原理開発者としても有名)である.
鞍点のある問題と異なり,一工夫が必要である.それは,ゲームの利得 G(P,Q)の替わりに期待値E(P,Q)を使う.以下,その説明をする.
Pが選択する戦略(グー,チョキ,パーを出す確率)をp1,p2,p3とし, P=(p1,p2,p3)で表しておく.
このゲームの場合,「戦略」は幾つかある「手」をランダムに選んで繰り返す 確率の組み合わせになるわけである.
同様にQが選択する戦略をQ=(q1,q2,q3)で表しておく.
Pがグーを出し,Qもグーを出す確率はp1・q1でこのとき
Pは損得なし(0円の儲け),
Pがグーを出し,Qがチョキを出す確率はp1・q2 でこのとき,Pは10円の儲け,
Pがグーを出し,Qがパーを出す確率はp1・q3でこのとき, Pは10円の損失(-10の儲け),
という計算を全て行うと
P=(p1,p2,p3),Q=(q1,q2,q3) でのPの儲けの期待値E(P,Q)は
E(P,Q)=0・p_1・q_1+10・p_1・q_2+(-10)・p_1・q_3 +(‐10)・p_2・q_1+0・p_2・q_2+10・p_2・q_3 +10・p_3・q_1+(‐10)・p_3・q_2+0・p_3・q_3
である. P=(p_1,p_2,p_3),Q=(q_1,q_2,q_3)は それぞれ,グー,チョキ,パーを出す確率を表しているから, これらについての制約は
1 \ge p_1 \ge 0,1 \ge p_2 \ge 0,1 \ge p_3 \ge 0, p_1+p_2+p_3=1 \\ 1 \ge q_1 \ge 0,1 \ge q_2 \ge 0,1 \ge q_3 \ge 0, q_1+q_2+q_3=1
である.
簡単のためP,Qの採り得る集合を
P_O= \{ (p_1,p_2,p_3)|1 \ge p_1 \ge 0,1 \ge p_2 \ge 0,1 \ge p_3 \ge 0, p_1+p_2+p_3=1\} \\ Q_O= \{ (q_1,q_2,q_3)|1 \ge q_1 \ge 0,1 \ge q_2 \ge 0,1 \ge q_3 \ge 0, q_1+q_2+q_3=1\}
で表しておく.前節のP_0,Q_0と異なり,それぞれ,確率を要素にもつベクトルの 集合になっている.
P=(p_1,p_2,p_3)がP_Oの中から選択されるとQはこれに対抗して E(P,Q)が最小になるように (自分の損失が最小になるように) Q=(q_1,q_2,q_3)をQ_O中で選択するはずである. すなわち
min \{ E(P,Q) |Q \in Q_O\}
が実現されるとなるようなQをQ_Oの中で探す. この最小値を
min_Q E(P,Q) で表しておく.
Pはこれを見越して,自分の利益が最大になるようにするため,
max \{ min_Q E(P,Q) |P \in P_O\}
が実現されるとなるようなPをP_Oの中から探すことになる. この最大値を
max_P min_Q E(P,Q)
で表しておく.
まっく逆のQの立場からは, Q=(q_1,q_2,q_3)がQ_0 の中から選択されるとPはこれに対抗して
E(P,Q)が最大になるように
P=(p_1,p_2,p_3)をP_0 中で選択するはずである. すなわち
max \{ E(P,Q) |P \in P_O\}
が実現されるとなるようなPをP_0の中から探す.この最小値を min_P E(P,Q) で表しておく.
Qはこれを見越して,自分の損失を最小にするため,
min \{ max_P E(P,Q) |Q \in Q_O \} が実現されるとなるようなQをQ_0の中で探すことになる.この最大値を min_Q max_P E(P,Q) で表しておく.
以上出てきた,2つの値には一般には
max_P min_Q E(P,Q) \le min_Q max_P E(P,Q)
という関係が成り立っている.
ノイマンは上のような問題では,P_O,Q_0の中に
P^*=(p_1^*,p_2^*,p_3^*), Q^*=(q_1^*,q_2^*,q_3^*)
があって
max_P min_Q E(P,Q) = min_Q max_P E(P,Q)=E(P^*,Q^*) \\ max_P E(P,Q^*)=E(P^*,Q^*)= min_Q E(P^*,Q)
となることを証明した.
このP^*とQ^*を具体的求めることにする.
問題を解きやすくするため,最初に出てきた<利得表> (損失と利益の表)の要素に全て10を加えておく.
これでは,一方的なPのゲームになるかもしれないが,
P^*=(p_1^*,p_2^*,p_3^*),Q^*=(q_1^*,q_2^*,q_3^*)
を計算するためだけであり,このような,利得表の平行移動やっても解は同じである.
P^*も,Q^*も,E(P^*,Q^*)も未知な量であるが
E(P^*,Q^*)は判っているもの
として
max_P E(P,Q^*)=E(P^*,Q^*)=min_Q E(P^*,Q)
に注目する.
E(P,Q)=q_1 \{ 10p_1+0p_2+20p_3\} +q_2 \{ 20p_1+10p_2+0p_3\} +q_3 \{ 0p_1+20p_2+10p_3\}
で,
1 \ge q_1 \ge 0,1 \ge q_2 \ge 0,1 \ge q_3 \ge 0, q_1+q_2+q_3=1
であるので
E(P^*,Q^*) \le 10p_1+0p_2+20p_3~ (1) \\ E(P^*,Q^*) \le 20p_1+10p_2+0p_3~ (2) \\ E(P^*,Q^*) \le 0p_1+20p_2+10p_3~ (3)
という条件を満たせば,任意のQ \in Q_0について E(P^*,Q^*) \le E(P,Q) が成り立つ.従って
E(P^*,Q^*) \le min_Q E(P,Q)
が成り立つ.
(1)~(3)とP \in P_0 即ち
1 \ge p_1,p_2,p_3 \ge 0, p_1+p_2+p_3=1
の制約条件下で
E(P,Q^*)=max_P E(P,Q^*)となるP
を求めれば,
E(P,Q^*)=E(P^*,Q^*) となるわけである.
しかし,これではまだE(P^*,Q^*)が未知量であるので,
(1)~(3)の両辺をE(P,Q^*) で割り,
r_1=p_1/E(P,Q^*) \\ r_2=p_2/E(P,Q^*) \\ r_3=p_3/E(P,Q^*)
として, E(P^*,Q^*)/E(P,Q^*) \ge 1
に注意すると
1 \le 10r_1+0r_2+20r_3~(1') \\ 1 \le 20r_1+10r_2+0r_3~(2') \\ 1 \le 0r_1+20r_2+10r_3~(3')
r_1+r_2+r_3 =(p_1+p_2+p_3)/E(P,Q^*) =1/E(P,Q^*)
から
E(P,Q^*)のPについての最大化 \Leftrightarrow 「r_1+r_2+r_3の最小化」
結局,線形計画法の問題
1 \le 10r_1+0r_2+20r_3(1') \\ 1 \le 20r_1+10r_2+0r_3(2') \\ 1 \le 0r_1+20r_2+10r_3(3')
かつ
r_1,r_2,r_3 \ge 0
の制約条件で
r_1+r_2+r_3
を最小化する という問題が出てくる.
Microsoft Excel のsolver などツールが利用できる.
その解から
p_1^*=r_1/(r_1+r_2+r_3) \\ p_2^*=r_2/(r_1+r_2+r_3) \\ p_3^*=r_3/(r_1+r_2+r_3)
とすれば,P^*の最適戦略が求まる. 生産計画でも説明した Microsoft Excel のソルバーを使って解くこともできる.
PとQの役目を交換しても全く同じなので,P^*=Q^*である.
最初の<利得表2>を用いれば,E(P^*,Q^*)も求まる.