最適化理論/ゲーム理論
提供: Internet Web School
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・p1・q1+10・p1・q2+(−10)・p1・q3+(‐10)・p2・q1+0・p2・q2+10・p2・q3+10・p3・q1+(‐10)・p3・q2+0・p3・q3
である. P=(p1,p2,p3),Q=(q1,q2,q3)は それぞれ,グー,チョキ,パーを出す確率を表しているから, これらについての制約は
1≥p1≥0,1≥p2≥0,1≥p3≥0,p1+p2+p3=11≥q1≥0,1≥q2≥0,1≥q3≥0,q1+q2+q3=1
である.
簡単のためP,Qの採り得る集合を
PO={(p1,p2,p3)|1≥p1≥0,1≥p2≥0,1≥p3≥0,p1+p2+p3=1}QO={(q1,q2,q3)|1≥q1≥0,1≥q2≥0,1≥q3≥0,q1+q2+q3=1}
で表しておく.前節のP0,Q0と異なり,それぞれ,確率を要素にもつベクトルの 集合になっている.
P=(p1,p2,p3)がPOの中から選択されるとQはこれに対抗して E(P,Q)が最小になるように (自分の損失が最小になるように) Q=(q1,q2,q3)をQO中で選択するはずである. すなわち
min{E(P,Q)|Q∈QO}
が実現されるとなるようなQをQOの中で探す. この最小値を
minQE(P,Q) で表しておく.
Pはこれを見越して,自分の利益が最大になるようにするため,
max{minQE(P,Q)|P∈PO}
が実現されるとなるようなPをPOの中から探すことになる. この最大値を
maxPminQE(P,Q)
で表しておく.
まっく逆のQの立場からは, Q=(q1,q2,q3)がQ0の中から選択されるとPはこれに対抗して
E(P,Q)が最大になるように
P=(p1,p2,p3)をP0中で選択するはずである. すなわち
max{E(P,Q)|P∈PO}
が実現されるとなるようなPをP0の中から探す.この最小値を minPE(P,Q) で表しておく.
Qはこれを見越して,自分の損失を最小にするため,
min{maxPE(P,Q)|Q∈QO} が実現されるとなるようなQをQ0の中で探すことになる.この最大値を minQmaxPE(P,Q) で表しておく.
以上出てきた,2つの値には一般には
maxPminQE(P,Q)≤minQmaxPE(P,Q)
という関係が成り立っている.
ノイマンは上のような問題では,PO,Q0の中に
P∗=(p∗1,p∗2,p∗3),Q∗=(q∗1,q∗2,q∗3)
があって
maxPminQE(P,Q)=minQmaxPE(P,Q)=E(P∗,Q∗)maxPE(P,Q∗)=E(P∗,Q∗)=minQE(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∗)は判っているもの
として
maxPE(P,Q∗)=E(P∗,Q∗)=minQE(P∗,Q)
に注目する.
E(P,Q)=q1{10p1+0p2+20p3}+q2{20p1+10p2+0p3}+q3{0p1+20p2+10p3}
で,
1≥q1≥0,1≥q2≥0,1≥q3≥0,q1+q2+q3=1
であるので
E(P∗,Q∗)≤10p1+0p2+20p3 (1)E(P∗,Q∗)≤20p1+10p2+0p3 (2)E(P∗,Q∗)≤0p1+20p2+10p3 (3)
という条件を満たせば,任意のQ∈Q0について E(P∗,Q∗)≤E(P,Q) が成り立つ.従って
E(P∗,Q∗)≤minQE(P,Q)
が成り立つ.
(1)~(3)とP∈P0 即ち
1≥p1,p2,p3≥0,p1+p2+p3=1
の制約条件下で
E(P,Q∗)=maxPE(P,Q∗)となるP
を求めれば,
E(P,Q∗)=E(P∗,Q∗) となるわけである.
しかし,これではまだE(P∗,Q∗)が未知量であるので,
(1)~(3)の両辺をE(P,Q∗) で割り,
r1=p1/E(P,Q∗)r2=p2/E(P,Q∗)r3=p3/E(P,Q∗)
として, E(P∗,Q∗)/E(P,Q∗)≥1
に注意すると
1≤10r1+0r2+20r3 (1′)1≤20r1+10r2+0r3 (2′)1≤0r1+20r2+10r3 (3′)
r1+r2+r3=(p1+p2+p3)/E(P,Q∗)=1/E(P,Q∗)
から
E(P,Q∗)のPについての最大化 ⇔「r1+r2+r3の最小化」
結局,線形計画法の問題
1≤10r1+0r2+20r3(1′)1≤20r1+10r2+0r3(2′)1≤0r1+20r2+10r3(3′)
かつ
r1,r2,r3≥0
の制約条件で
r1+r2+r3
を最小化する という問題が出てくる.
Microsoft Excel のsolver などツールが利用できる.
その解から
p∗1=r1/(r1+r2+r3)p∗2=r2/(r1+r2+r3)p∗3=r3/(r1+r2+r3)
とすれば,P∗の最適戦略が求まる.
PとQの役目を交換しても全く同じなので,P∗=Q∗である. 最初の<利得表2>を用いれば,E(P∗,Q∗)も求まる.