最適化理論/ゲーム理論

提供: Internet Web School

(版間での差分)
1 行: 1 行:
-
A,Bがじゃんけんを繰り返し,毎回,勝ったほうが10点を得るゲームを行う.
+
<math>P,Q</math>の２人がじゃんけんをす。\\
-
A,Bが繰り出す手によって得られる得点をAの視点から表にしたものが以下である。
+
負けたら10円を相手に払い,勝ったら相手から10円貰うというルールで,
 +
じゃんけんを繰り返す。\\
 +
無論,「アイコ」の場合は,支払うお金,貰うお金とも0円である。\\
-
Aはどのように「グー」「チョキ」「パー」の手を繰り出していけば、得点が最大になるだろうか？
 
-
例えばAが「グー」を出し続けていけば,Bはそれを観て「パー」を出し続けて,Bは勝ちを繰り返すことができる.
 
-
Aが「グー」「チョキ」「パー」をこの順に規則的に繰り返していけば,Bはそれを観て
 
-
「パー」「グー」「チョキ」　という対抗手段を講じて勝ちを繰り返すことができる.
 
-
結局,Aは「グー」「チョキ」「パー」を不規則に出すことになる.それでは,それぞれどのような確率で出せば
 
-
得点の期待値を最大にできるか？　という問題に帰着するだろう.
 
 +
前節と同様に,<math>P</math>と<math>Q</math>の出す手によって,貰えるお金,支払うお金がどうなるか,
 +
<math>P</math>の立場で以下のように
 +
＜利得表2＞に表しておく。\\
 +
 
 +
＜利得表2＞\\
 +
\begin{tabular}{|c|c|c|c|}
 +
\hline
 +
&<math>Gu<math>&<math>Choki<math>&<math>Pa<math>\\
 +
\hline
 +
<math>Gu<math>&0&-10&10 \\
 +
\hline
 +
<math>Choki<math>&10&0&-10\\
 +
\hline
 +
<math>Pa<math>&-10&10&0 \\
 +
\hline
 +
\end{tabular}
 +
<math>
 +
Gu：グー\\
 +
Choki：チョキ\\
 +
Pa：パー
 +
</math>
-
Aが「グー」「チョキ」「パー」を出す確率をそれぞれ
+
「-10」は<math>Q</math>に10円払う事を表す。\\
-
<math>p_1,p_2,p_3</math>とする.
+
-
<math>0  \le p_1,0  \le p_2,0  \le p_3 \qquad  p_1+p_2+p_3=0 \qquad  (1) </math>
 
-
ここで問題の簡単化のため,得点表のそれぞれ要素の値を正数とするため各要素に10を加えておく.
+
<math>P</math>の立場に立ってみます。先ず,このゲームの利得表には、前節で説明した鞍点がない。双方が選択の余地のない「平衡状態」にする戦略はないわけである。出す手をランダムしてゲームを繰り返す方法以外ありません。このような問題を混合戦略問題といいます。 \\
-
Aが得点の期待値を求めれば
+
じゃんけんを繰り返すわけであるが,どのような「戦略」がある？\\
-
Bが「グー」を出すときは
 
-
<math>10p_1+0p_2+20p_3  </math>
+
グーを出し続けとすると,<math>Q</math>はそれを直ぐ見破って,
 +
パーを出し続けてくるであろう。続ければ続けるほど<math>P</math>は大損である。\\
 +
同様にパーを出し続けても,チョキを出し続けるのも駄目である。\\
 +
結局,例えば,サイコロを用意して,出た目によって出す手を決めるランダムな手の繰り返す方法であろう。\\
 +
(1か6ならグー,2か5ならパー,3か4ならチョキなど) \\
-
Bが「チョキ」を出すときは
+
問題は,どんな割合で（確率で）グー,チョキ,パーを出すべきかである。\\
 +
相手の<math>Q</math>は<math>P</math>の出す手を監視しながら
 +
<math>P</math>と対戦するので,<math>P</math>が選択したグー,チョキ,パーの確率を直ぐに見破り,
 +
それでも,自分にとって有利
 +
な手を選択してくると考えるべきである。\\
 +
<math>P</math>と<math>Q</math>の立場を替えても全く同じである。\\
-
<math>20p_1+10p_2+0p_3  </math>
 
-
Bが「パー」を出すときは
+
ゲームの理論を創始し,この種の問題に解を与えたのが,ノイマン（
 +
<math>von Nuemann</math> 現在の計算機の原理開発者としても有名）である。\\
-
<math>0p_1+20p_2+10p_3  </math>
+
鞍点のある問題と異なり,一工夫が必要である。それは,ゲームの利得
 +
<math>G(P,Q)</math>の替わりに期待値<math>E(P,Q)</math>を使います。以下、その説明をする。
 +
<math>P</math>が選択する戦略（グー,チョキ,パーを出す確率）を<math>p_1,p_2,p_3</math>とし,
 +
<math>P=(p_1,p_2,p_3)</math>で表しておく。\\
 +
このゲームの場合、「戦略」は幾つかある「手」をランダムに選んで繰り返す
 +
確率の組み合わせになるわけである。\\
 +
同様に<math>Q</math>が選択する戦略を<math>Q=(q_1,q_2,q_3)</math>で表しておく。\\
 +
\begin{description}
 +
\item <math>P</math>がグーを出し,<math>Q</math>もグーを出す確率は<math>p_1･q_1</math>でこのとき
 +
<math>P</math>は損得なし(0円の儲け),
 +
\item <math>P</math>がグーを出し,<math>Q</math>がチョキを出す確率
 +
は<math>p_1･q_2<math>でこのとき,<math>P</math>は10円の儲け,
 +
\item <math>P</math>がグーを出し,<math>Q</math>がパーを出す確率は<math>p_1･q_3<math>でこのとき,
 +
<math>P</math>は10円の損失(-10の儲け),
 +
\end{description}
-
<math>20p_1+10p_2+0p_3  </math>
+
という計算を全て行うと
 +
<math>P=(p_1,p_2,p_3),Q=(q_1,q_2,q_3)</math>
 +
での<math>P</math>の儲けの期待値<math>E(P,Q)</math>は
 +
<math>
 +
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 
 +
</math>
 +
である。
 +
<math>P=(p_1,p_2,p_3),Q=(q_1,q_2,q_3)</math>は
 +
それぞれ,グー,チョキ,パーを出す確率を表しているから,
 +
これらについての制約は
 +
<math>
 +
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
 +
</math>
 +
である。
 +
簡単のため<math>P,Q</math>の採り得る集合を
 +
<math>
 +
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\}
 +
</math>
 +
で表しておく。前節の<math>P_0,Q_0</math>と異なり,それぞれ,確率を要素にもつベクトルの
 +
集合になっている。
-
<math>0  \le p_1,0  \le p_2,0 \le p_3 \qquad   p_1+p_2+p_3=0 \qquad   (1) </math>
+
<math>P=(p_1,p_2,p_3)</math>が<math>P_O</math>の中から選択されると<math>Q</math>はこれに対抗して
 +
<math>E(P,Q)</math>が最小になるように
 +
（自分の損失が最小になるように）
 +
<math>Q=(q_1,q_2,q_3)</math>を<math>Q_O</math>中で選択するはずである。\\
 +
すなわち
 +
  <math>\min \{   E(P,Q) |Q \in Q_O\}</math>
 +
が実現されるとなるような<math>Q</math>を<math>Q_O</math>の中で探す。\\
 +
この最小値を
 +
<math>\min_Q E(P,Q)</math>
 +
で表しておく。\\
 +
<math>P</math>はこれを見越して,自分の利益が最大になるようにするため,
 +
<math>\max \{   \min_Q E(P,Q) |P \in P_O\}</math>
 +
が実現されるとなるような<math>P</math>を<math>P_O</math>の中から探すことになる。
 +
この最大値を
 +
<math>\max_P \min_Q E(P,Q) </math>
 +
で表しておく。
 +
まっく逆のQの立場からは,
 +
<math>Q=(q_1,q_2,q_3)</math>が<math>Q_0</math>の中から選択されると<math>P</math>はこれに対抗して
 +
<math>E(P,Q)</math>が最大になるように
 +
<math>P=(p_1,p_2,p_3)</math>を<math>P_0</math>中で選択するはずである。\\
 +
すなわち
 +
<math>\max \{  E(P,Q) |P \in P_O\}</math>
 +
が実現されるとなるような<math>P</math>を<math>P_0</math>の中から探す。この最小値を
 +
<math>\min_P E(P,Q)</math>
 +
で表しておく。
 +
<math>Q</math>はこれを見越して,自分の損失を最小にするため,
 +
<math>\min \{  \max_P E(P,Q) |Q \in Q_O\}</math>
 +
が実現されるとなるような<math>Q</math>を<math>Q_0</math>の中で探すことになります。この最大値を
 +
<math>\min_Q \max_P E(P,Q)</math>
 +
で表しておく。
-
である.
 
-
この問題に解が存在するとすれば,その得点の期待値<math>0 \lt G</math> とすれば
 
 +
以上出てきた,２つの値には一般には
 +
 +
<math>\max_P \min_Q E(P,Q)  \le  \min_Q \max_P E(P,Q)</math>
 +
 +
という関係が成り立っている。
 +
 +
ノイマンは上のような問題では,<math>P_O,Q_0</math>の中に
 +
<math>P^*=(p_1^*,p_2^*,p_3^*), Q^*=(q_1^*,q_2^*,q_3^*)</math>
 +
があって
 +
<math>
 +
\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)
 +
</math>
 +
 +
となることを証明した。\\
 +
 +
この<math>P^*<math>と<math>Q^*<math>を具体的求めることにする。\\
 +
 +
問題を解きやすくするため,最初に出てきた＜利得表＞
 +
(損失と利益の表)の要素に全て10を加えて
 +
おく。\\
 +
 +
＜利得表2＞\\
 +
\begin{tabular}{|c|c|c|c|}
 +
\hline
 +
&<math>Gu<math>&<math>Choki<math>&<math>Pa<math>\\
 +
\hline
 +
<math>Gu<math>&10&0&20 \\
 +
\hline
 +
<math>Choki<math>&20&10&0\\
 +
\hline
 +
<math>Pa<math>&0&20&10 \\
 +
\hline
 +
\end{tabular}
 +
<math>
 +
Gu：グー\\
 +
Choki：チョキ\\
 +
Pa：パー
 +
</math>
 +
 +
これでは,一方的な<math>P</math>のゲームになるかもしれないが,\\
 +
<math>P^*=(p_1^*,p_2^*,p_3^*),Q^*=(q_1^*,q_2^*,q_3^*)</math>
 +
を計算するためだけであり,このような,利得表の平行移動やっても解は同じである。\\
 +
 +
 +
<math>P^*<math>も,<math>Q^*<math>も,<math>E(P^*,Q^*)</math>も未知な量であるが
 +
<math>E(P^*,Q^*)</math>は判っているもの
 +
として
 +
<math>\max_P E(P,Q^*)=E(P^*,Q^*)=\min_Q E(P^*,Q)</math>
 +
 +
に注目する。
 +
<math>
 +
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\}
 +
</math>
 +
 +
で,
 +
<math>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<math>
 +
ですので
 +
<math>
 +
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)
 +
</math>
 +
 +
という条件を満たせば,任意の<math>Q \in Q_0</math>について
 +
<math>E(P^*,Q^*)  \le E(P,Q)</math> 
 +
が成り立つ。従って
 +
<math>E(P^*,Q^*)  \le \min_Q E(P,Q)</math>
 +
が成り立つ。\\
 +
<math>(1)</math>～<math>(3)</math>と<math>P \in P_0</math>即ち \\
 +
<math>1 \ge p_1,p_2,p_3 \ge 0, p_1+p_2+p_3=1<math>
 +
の制約条件下で
 +
<math>E(P,Q^*)=\max_P E(P,Q^*)</math>となる<math>P</math>
 +
を求めれば,
 +
<math>E(P,Q^*)=E(P^*,Q^*)</math>
 +
となるわけである。
 +
しかし,これではまだ<math>E(P^*,Q^*)</math>が未知量であるので,
 +
 +
<math>(1)</math>～<math>(3)</math>の両辺を<math>E(P,Q^*)</math>で割り,
 +
<math>
 +
r_1=p_1/E(P,Q^*)\\
 +
r_2=p_2/E(P,Q^*)\\
 +
r_3=p_3/E(P,Q^*)
 +
</math>
 +
 +
として,
 +
<math>E(P^*,Q^*)/E(P,Q^*) \ge 1<math>
 +
に注意すると
 +
<math>
 +
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')
 +
</math>
 +
<math>
 +
r_1＋r_2＋r_3 \\
 +
=(p_1＋p_2＋p_3)/E(P,Q^*)\\
 +
=1/E(P,Q^*)
 +
</math>
 +
 +
から
 +
 +
<math>E(P,Q^*)のPについての最大化
 +
\Leftrightarrow 「r_1+r_2+r_3の最小化」<math>
 +
 +
 +
結局,線形計画法の問題
 +
<math>
 +
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')
 +
</math>
 +
かつ
 +
<math>r_1,r_2,r_3 \ge 0</math>
 +
の制約条件で
 +
 +
<math>r_1+r_2+r_3<math>
 +
 +
を最小化する\\
 +
という問題が出てくる。
 +
 +
Microsoft Excel
 +
のsolver などツールが利用できる。
 +
 +
その解から
 +
<math>
 +
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)
 +
</math>
 +
 +
とすれば,<math>P^*<math>の最適戦略が求まる。\\
 +
 +
<math>P</math>と<math>Q</math>の役目を交換しても全く同じなので,<math>P^*=Q^*<math>である。
 +
最初の＜利得表2＞を用いれば,<math>E(P^*,Q^*)</math>も求まる。
[[ファイル:Game_ページ_1.jpg]]
[[ファイル:Game_ページ_1.jpg]]

2020年11月24日 (火) 12:11時点における版

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


前節と同様に,\(P\)と\(Q\)の出す手によって,貰えるお金,支払うお金がどうなるか, \(P\)の立場で以下のように ＜利得表2＞に表しておく。\\

＜利得表2＞\\ \begin{tabular}{|c|c|c|c|} \hline &\(Gu<math>&<math>Choki<math>&<math>Pa<math>\\ \hline <math>Gu<math>&0&-10&10 \\ \hline <math>Choki<math>&10&0&-10\\ \hline <math>Pa<math>&-10&10&0 \\ \hline \end{tabular} <math> Gu：グー\\ Choki：チョキ\\ Pa：パー \)

「-10」は\(Q\)に10円払う事を表す。\\


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


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

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

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

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


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

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

\(P\)が選択する戦略（グー,チョキ,パーを出す確率）を\(p_1,p_2,p_3\)とし, \(P=(p_1,p_2,p_3)\)で表しておく。\\

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


同様に\(Q\)が選択する戦略を\(Q=(q_1,q_2,q_3)\)で表しておく。\\

\begin{description} \item UNIQ490dfeb715f830b3-MathJax-24-QINUがグーを出し,UNIQ490dfeb715f830b3-MathJax-25-QINUもグーを出す確率はUNIQ490dfeb715f830b3-MathJax-26-QINUでこのとき UNIQ490dfeb715f830b3-MathJax-27-QINUは損得なし(0円の儲け), \item UNIQ490dfeb715f830b3-MathJax-28-QINUがグーを出し,UNIQ490dfeb715f830b3-MathJax-29-QINUがチョキを出す確率 はUNIQ490dfeb715f830b3-MathJax-30-QINUは10円の儲け, \item UNIQ490dfeb715f830b3-MathJax-31-QINUがグーを出し,UNIQ490dfeb715f830b3-MathJax-32-QINUがパーを出す確率はUNIQ490dfeb715f830b3-MathJax-33-QINUは10円の損失(-10の儲け), \end{description}

という計算を全て行うと

\(P=(p_1,p_2,p_3),Q=(q_1,q_2,q_3)\) での\(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)\) で表しておく。


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

\(\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^*<math>と<math>Q^*<math>を具体的求めることにする。\\ 問題を解きやすくするため,最初に出てきた＜利得表＞ (損失と利益の表)の要素に全て10を加えて おく。\\ ＜利得表2＞\\ \begin{tabular}{|c|c|c|c|} \hline &<math>Gu<math>&<math>Choki<math>&<math>Pa<math>\\ \hline <math>Gu<math>&10&0&20 \\ \hline <math>Choki<math>&20&10&0\\ \hline <math>Pa<math>&0&20&10 \\ \hline \end{tabular} <math> Gu：グー\\ Choki：チョキ\\ Pa：パー \)

これでは,一方的な\(P\)のゲームになるかもしれないが,\\ \(P^*=(p_1^*,p_2^*,p_3^*),Q^*=(q_1^*,q_2^*,q_3^*)\) を計算するためだけであり,このような,利得表の平行移動やっても解は同じである。\\


\(P^*<math>も,<math>Q^*<math>も,<math>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<math> ですので <math> 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<math> の制約条件下で <math>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<math> に注意すると <math> 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の最小化」<math> 結局,線形計画法の問題 <math> 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<math> を最小化する\\ という問題が出てくる。 Microsoft Excel のsolver などツールが利用できる。 その解から <math> 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^*<math>の最適戦略が求まる。\\ <math>P\)と\(Q\)の役目を交換しても全く同じなので,\(P^*=Q^*<math>である。 最初の＜利得表2＞を用いれば,<math>E(P^*,Q^*)\)も求まる。

ファイル:Game_ページ_1.jpg



ゲーム理論

「http://ja.iwschool.org/wiki/%E6%9C%80%E9%81%A9%E5%8C%96%E7%90%86%E8%AB%96/%E3%82%B2%E3%83%BC%E3%83%A0%E7%90%86%E8%AB%96」より作成
個人用ツール