Loading [MathJax]/jax/output/HTML-CSS/jax.js

最適化理論/ゲーム理論

提供: Internet Web School

UNIQ3ff10f976a520f4a-MathJax-2-QINU2 による版

P,Qの2人がじゃんけんをする. 負けたら10円を相手に払い,勝ったら相手から10円貰うというルールで, じゃんけんを繰り返す. 無論,「アイコ」の場合は,支払うお金,貰うお金とも0円である.

PQの出す手によって,貰えるお金,支払うお金がどうなるか, Pの立場で以下のような表になる. ファイル:Game01.jpg 「-10」はQに10円払う事を表す.

Pの立場に立ってみる.先ず,このゲームの利得表には鞍点がない. 双方が選択の余地のない「平衡状態」にする戦略はないわけである.出す手をランダムしてゲームを繰り返す方法以外ない. このような問題を混合戦略問題といいます. じゃんけんを繰り返すわけであるが,どのような「戦略」があるか?

グーを出し続けとすると,Qはそれを直ぐ見破って, パーを出し続けてくるであろう.続ければ続けるほどPは大損である. 同様にパーを出し続けても,チョキを出し続けるのも駄目である.

結局,例えばサイコロを用意して,出た目によって出す手を決めるランダムな手の繰り返す方法であろう.

(1か6ならグー,2か5ならパー,3か4ならチョキなど)

問題は,どんな割合で(確率で)グー,チョキ,パーを出すべきかである. 相手のQPの出す手を監視しながらPと対戦するので,Pが選択したグー,チョキ,パーの確率を直ぐに見破り, それでも,自分にとって有利な手を選択してくると考えるべきである.PQの立場を替えても全く同じである.


ゲームの理論を創始し,この種の問題に解を与えたのが,ノイマン(vonNuemann 現在の計算機の原理開発者としても有名)である.

鞍点のある問題と異なり,一工夫が必要である.それは,ゲームの利得 G(P,Q)の替わりに期待値E(P,Q)を使います.以下,その説明をする.

Pが選択する戦略(グー,チョキ,パーを出す確率)をp1,p2,p3とし, P=(p1,p2,p3)で表しておく.

このゲームの場合,「戦略」は幾つかある「手」をランダムに選んで繰り返す 確率の組み合わせになるわけである.


同様にQが選択する戦略をQ=(q1,q2,q3)で表しておく.


Pがグーを出し,Qもグーを出す確率はp1q1でこのとき

Pは損得なし(0円の儲け),

Pがグーを出し,Qがチョキを出す確率はp1q2 でこのとき,Pは10円の儲け,

Pがグーを出し,Qがパーを出す確率はp1q3でこのとき, Pは10円の損失(-10の儲け),

という計算を全て行うと

P=(p1,p2,p3),Q=(q1,q2,q3) でのPの儲けの期待値E(P,Q)

E(P,Q)=0p1q1+10p1q2+(10)p1q3+(10)p2q1+0p2q2+10p2q3+10p3q1+(10)p3q2+0p3q3

である. P=(p1,p2,p3),Q=(q1,q2,q3)は それぞれ,グー,チョキ,パーを出す確率を表しているから, これらについての制約は

1p10,1p20,1p30,p1+p2+p3=11q10,1q20,1q30,q1+q2+q3=1

である.

簡単のためP,Qの採り得る集合を

PO={(p1,p2,p3)|1p10,1p20,1p30,p1+p2+p3=1}QO={(q1,q2,q3)|1q10,1q20,1q30,q1+q2+q3=1}

で表しておく.前節のP0,Q0と異なり,それぞれ,確率を要素にもつベクトルの 集合になっている.

P=(p1,p2,p3)POの中から選択されるとQはこれに対抗して E(P,Q)が最小になるように (自分の損失が最小になるように) Q=(q1,q2,q3)QO中で選択するはずである. すなわち

min{E(P,Q)|QQO}

が実現されるとなるようなQQOの中で探す. この最小値を

minQE(P,Q) で表しておく.

Pはこれを見越して,自分の利益が最大になるようにするため,

max{minQE(P,Q)|PPO}

が実現されるとなるようなPPOの中から探すことになる. この最大値を

maxPminQE(P,Q)

で表しておく.

まっく逆のQの立場からは, Q=(q1,q2,q3)Q0の中から選択されるとPはこれに対抗して

E(P,Q)が最大になるように

P=(p1,p2,p3)P0中で選択するはずである. すなわち

max{E(P,Q)|PPO}

が実現されるとなるようなPP0の中から探す.この最小値を minPE(P,Q) で表しておく.

Qはこれを見越して,自分の損失を最小にするため,

min{maxPE(P,Q)|QQO} が実現されるとなるようなQQ0の中で探すことになる.この最大値を minQmaxPE(P,Q) で表しておく.


以上出てきた,2つの値には一般には

maxPminQE(P,Q)minQmaxPE(P,Q)

という関係が成り立っている.

ノイマンは上のような問題では,PO,Q0の中に

P=(p1,p2,p3),Q=(q1,q2,q3)

があって

maxPminQE(P,Q)=minQmaxPE(P,Q)=E(P,Q)maxPE(P,Q)=E(P,Q)=minQE(P,Q)

となることを証明した.

このPQを具体的求めることにする.

問題を解きやすくするため,最初に出てきた<利得表> (損失と利益の表)の要素に全て10を加えておく.


これでは,一方的なPのゲームになるかもしれないが,

P=(p1,p2,p3),Q=(q1,q2,q3)

を計算するためだけであり,このような,利得表の平行移動やっても解は同じである.


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}

で,

1q10,1q20,1q30,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)

という条件を満たせば,任意のQQ0について E(P,Q)E(P,Q) が成り立つ.従って

E(P,Q)minQE(P,Q)

が成り立つ.

(1)(3)PP0 即ち

1p1,p2,p30,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

に注意すると

110r10r220r3 (1)120r110r20r3 (2)10r120r210r3 (3)

r1r2r3=(p1p2p3)/E(P,Q)=1/E(P,Q)

から

E(P,Q)P r1+r2+r3


結局,線形計画法の問題

110r1+0r2+20r3(1)120r1+10r2+0r3(2)10r1+20r2+10r3(3)

かつ

r1,r2,r30

の制約条件で

r1+r2+r3

を最小化する という問題が出てくる.

Microsoft Excel のsolver などツールが利用できる.

その解から

p1=r1/(r1+r2+r3)p2=r2/(r1+r2+r3)p3=r3/(r1+r2+r3)

とすれば,Pの最適戦略が求まる.

PQの役目を交換しても全く同じなので,P=Qである. 最初の<利得表2>を用いれば,E(P,Q)も求まる.


ゲーム理論

個人用ツール