Processing math: 8%

最適化理論/ゲーム理論

提供: Internet Web School

(版間での差分)
(鞍点のある問題)
(鞍点のある問題)
31 行: 31 行:
を片付けるのは0点,こっそり抜け出して遊ぶ場合は100点である.
を片付けるのは0点,こっそり抜け出して遊ぶ場合は100点である.
-
父親にしてみれば:
+
父親にしてみれば
-
\begin{eqnarray*}
+
 
-
 &&「昼寝する」を選択したら,自分の失点(息子の得点)は,最大100点
+
「昼寝する」を選択したら,自分の失点(息子の得点)は最大100点
-
 &&「昼寝しない」を選択したら,自分の失点(息子の得点)は,最大50点
+
-
\end{eqnarray*}
+
「昼寝しない」選択したら,自分の失点(息子の得点)は最大50点
-
この二つの最大失点のうち,最小のものは50点である.
+
 
 +
この二つの最大失点のうち最小のものは50点である.
 +
 
 +
息子にしてみれば
 +
 
 +
「勉強する」を選択したら自分の得点は最小-50点
 +
 
 +
「遊ぶ」を選択したら自分の得点は最小50点
 +
 
-
息子にしてみれば:
 
-
\begin{eqnarray*}
 
-
  &&「勉強する」を選択したら,自分の得点は,最小-50点
 
-
  &&「遊ぶ」を選択したら,  自分の得点は,最小50点
 
-
\end{eqnarray*}
 
この二つの最小得点のうち,最大ものは50点である.
この二つの最小得点のうち,最大ものは50点である.
この例では
この例では
-
「最大失点のうち,最小のもの」=「最小得点のうち,最大もの」
+
最大失点のうち,最小のもの」=「最小得点のうち,最大もの」
が成立っている.
が成立っている.
-
結局,父親が昼寝をしなければ,父親にとっては,最悪でも息子は,50点
+
結局,父親が昼寝をしなければ,父親にとっては,最悪でも息子の得点は50点
息子にしてみれば,「遊ぶ」を選択したら最悪でも自分の得点は50点
息子にしてみれば,「遊ぶ」を選択したら最悪でも自分の得点は50点
である.このような状況を「このゲームには鞍点がある」という.
である.このような状況を「このゲームには鞍点がある」という.
 +
この話を一般化しておく.
この話を一般化しておく.
-
二人の競技者<math>P,Q</math>が取り得「戦略」の集合を<math>P_0,Q_O</math>とする.そして,
+
 
-
この二人がそれぞれ「戦略」の集合<math>P_0,Q_O</math>の中から戦略<math>P,Q</math>を選択したときの
+
二人の競技者<math>P,Q</math>が取り得る「戦略」の集合を<math>P_O,Q_O</math>とする.そして,
 +
この二人がそれぞれ「戦略」の集合<math>P_O,Q_O</math>の中から戦略<math>P,Q</math>を選択したときの
得点を<math>G(P,Q)</math>で表しておく.
得点を<math>G(P,Q)</math>で表しておく.
-
上の例では,<math>P=息子,Q=父親<math>で,<math>P_0=\{ 勉強する,遊ぶ \} <math>
+
上の例では,<math>P=息子,Q=父親</math>で,<math>P_0=\{ 勉強する,遊ぶ \}</math>
-
<math>Q_0=\{ 昼寝する,昼寝しない \} <math>です。<math>G(P,Q)</math>は上の利得表1で与えらる.
+
<math>Q_0=\{ 昼寝する,昼寝しない \} </math>である.
 +
<math>G(P,Q)</math>は上の利得表1で与えらる.
<math>P</math>が<math>P_O</math>の中から選択されると<math>Q</math>はこれに対抗して
<math>P</math>が<math>P_O</math>の中から選択されると<math>Q</math>はこれに対抗して
<math>G(P,Q)</math>が最小になるように
<math>G(P,Q)</math>が最小になるように
-
(自分の損失が最小になるように)
+
(自分の損失が最小になるように)
<math>Q</math>を<math>Q_O</math>中で選択するはずである.
<math>Q</math>を<math>Q_O</math>中で選択するはずである.
 +
すなわち
すなわち
-
  <math>\min \{  G(P,Q) |Q \in Q_O\}<math>  
+
 
 +
  <math>\min \{  G(P,Q) |Q \in Q_O\}</math>  
 +
 
が実現されるとなるような<math>Q</math>を<math>Q_O</math>の中で探す.
が実現されるとなるような<math>Q</math>を<math>Q_O</math>の中で探す.
-
この最小値を
+
 
-
<math>\min_Q G(P,Q)</math>
+
この最小値を<math>\min_Q G(P,Q)</math> で表しておく.
-
で表しておきます。
+
 
<math>P</math>はこれを見越して,自分の利益が最大になるようにするため,
<math>P</math>はこれを見越して,自分の利益が最大になるようにするため,
-
  <math>\max \{  \min_Q G(P,Q) |P \in P_O\}<math>
+
   
 +
<math>\max \{  \min_Q G(P,Q) |P \in P_O\}</math>
 +
 
 +
が実現されるとなるような<math>P</math>を<math>P_O</math>の中から探すことになる.
-
が実現されるとなるような<math>P</math>を<math>P_0</math>の中から探すことになる.
 
この最大値を
この最大値を
-
<math>\max_P \min_Q G(P,Q) <math>
+
 
 +
<math>\max_P \min_Q G(P,Q) </math>
 +
 
で表しておく.
で表しておく.
86 行: 99 行:
<math>P</math>を<math>P_0</math>中で選択するはずである.
<math>P</math>を<math>P_0</math>中で選択するはずである.
すなわち
すなわち
-
  <math>\max \{  G(P,Q) |P \in P_O\}<math>  
+
 
-
が実現されるとなるような<math>P</math>を<math>P_0</math>の中から探す.この最小値を
+
  <math>\max \{  G(P,Q) |P \in P_O\}</math>  
 +
 
 +
が実現されるとなるような<math>P</math>を<math>P_0</math>の中から探す.
 +
この最小値を
 +
 
<math>\min_P G(P,Q)</math>
<math>\min_P G(P,Q)</math>
 +
で表しておく.
で表しておく.
 +
<math>Q</math>はこれを見越して,自分の損失を最小にするため,
<math>Q</math>はこれを見越して,自分の損失を最小にするため,
-
  <math>\min \{  \max_P G(P,Q) |Q \in Q_O\}<math>
+
 
-
が実現されるとなるような<math>Q</math>を<math>Q_0</math>の中で探すことになる.この最大値を
+
  <math>\min \{  \max_P G(P,Q) |Q \in Q_O\}</math>
 +
 
 +
が実現されるとなるような<math>Q</math>を<math>Q_0</math>の中で探すことになる.
 +
 
 +
この最大値を
 +
 
<math>\min_Q \max_P E(P,Q)</math>  
<math>\min_Q \max_P E(P,Q)</math>  
 +
で表しておく.
で表しておく.
102 行: 127 行:
という関係が成り立っている.
という関係が成り立っている.
-
{\bf [証明]}
+
 
-
<math>Q</math>を<math>Q_O</math>の中で動かして,
+
なぜばら,
 +
<math>Q</math>を<math>Q_O</math>の中で動かして,
 +
 
<math>\min_Q G(P,Q)  \le  G(P,Q)</math>
<math>\min_Q G(P,Q)  \le  G(P,Q)</math>
 +
  が任意の<math>P</math>(両辺),<math>Q</math>(右辺)について成立
  が任意の<math>P</math>(両辺),<math>Q</math>(右辺)について成立
 +
  次に上の不等式の右辺について<math>P</math>を<math>P_0</math>中で動かして,
  次に上の不等式の右辺について<math>P</math>を<math>P_0</math>中で動かして,
-
  <math>\min_Q G(P,Q)  \le  \max_P G(P,Q)</math> が任意の<math>P</math>(左辺),<math>Q</math>
+
 
 +
  <math>\min_Q G(P,Q)  \le  \max_P G(P,Q)</math>  
 +
 
 +
が任意の<math>P</math>(左辺),<math>Q</math>
 +
 
(右辺)について成立
(右辺)について成立
 +
  さらに上の不等式の左辺について<math>P</math>を<math>P_0</math>の中で動かして,
  さらに上の不等式の左辺について<math>P</math>を<math>P_0</math>の中で動かして,
-
<math>\max_P \min_Q G(P,Q)  \le  \max_P G(P,Q)</math>
+
 
-
が任意の<math>Q</math>(右辺)について成立
+
<math>\max_P \min_Q G(P,Q)  \le  \max_P G(P,Q)</math>
-
最後に右辺の<math>Q</math>を<math>Q_0</math>の中で動かして
+
 
 +
が任意の<math>Q</math>(右辺)について成立
 +
 
 +
最後に右辺の<math>Q</math>を<math>Q_0</math>の中で動かして
 +
 
<math> \max_P \min_Q G(P,Q)  \le  \min_Q \max_P G(P,Q)</math>
<math> \max_P \min_Q G(P,Q)  \le  \min_Q \max_P G(P,Q)</math>
-
[証明終]
 
 +
である.

2020年11月26日 (木) 08:30時点における版

鞍点のある問題

  教育熱心な父親と,遊び盛りの息子がいる. この父親,ご多分に洩れず仕事の疲れがたまり,日曜は昼寝することが多いのですが,子煩悩で息子の勉強も気になる.

息子にしてみれば,日曜日に頼みもしないのに,父親に小言を言われながら―父親にしてみれば指導なのですが―勉強させられるのは最悪である。

鬱陶しい」が父親が起きていても,時間を稼ぎながら話題をはぐらかして,なんとか家でゲームでもした方がましと考えている.

父親が大人しく昼寝してくれて,こっそり抜け出すことができれば友人の家にでもゲームでもしに行くのだが, それができなくても,溜まった宿題を一人で片付けるほうがまだましと考えている.


父親は「昼寝をする.しない.」息子は「勉強する.遊ぶ.」でそれぞれ「戦略」に選択肢がある.

そこで,二人に「戦略」の選択によってかわる利害得失を下のように単純化して表にしてみる.

<利得表1>

\begin{tabular}{|c|c|c|} \hline  &勉強する&遊ぶ \hline  昼寝しない&-50&50 \hline  昼寝する&0&100 \hline  \end{tabular}


この表の値は,息子の側に立ったものである.父親が昼寝しないで「指導」を受けながら勉強する最悪な場合は得点-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=で,P0={,} Q0={,}である.

G(P,Q)は上の利得表1で与えらる.


PPOの中から選択されるとQはこれに対抗して G(P,Q)が最小になるように (自分の損失が最小になるように) QQO中で選択するはずである.

すなわち

min 

が実現されるとなるようなQQ_Oの中で探す.

この最小値を\min_Q G(P,Q) で表しておく.

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

\max \{ \min_Q G(P,Q) |P \in P_O\}

が実現されるとなるようなPP_Oの中から探すことになる.

この最大値を

\max_P \min_Q G(P,Q)

で表しておく.

まっく逆のQの立場からは, QQ_0の中から選択されるとPはこれに対抗して G(P,Q)が最大になるように PP_0中で選択するはずである. すなわち

\max \{   G(P,Q) |P \in P_O\} 

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

\min_P G(P,Q)

で表しておく.

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

\min \{   \max_P G(P,Q) |Q \in Q_O\}

が実現されるとなるようなQQ_0の中で探すことになる.

この最大値を

\min_Q \max_P E(P,Q)

で表しておく.


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

\max_P \min_Q G(P,Q) \le \min_Q \max_P G(P,Q)

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

なぜばら, QQ_Oの中で動かして,

\min_Q G(P,Q) \le G(P,Q)

が任意のP(両辺),Q(右辺)について成立
次に上の不等式の右辺についてPP_0中で動かして,
\min_Q G(P,Q)  \le  \max_P G(P,Q) 

が任意のP(左辺),Q

(右辺)について成立

さらに上の不等式の左辺についてPP_0の中で動かして,

\max_P \min_Q G(P,Q) \le \max_P G(P,Q)

が任意のQ(右辺)について成立

最後に右辺のQQ_0の中で動かして

\max_P \min_Q G(P,Q) \le \min_Q \max_P G(P,Q)

である.


特に「鞍点」が存在する場合,戦略P^* \in P_0,Q^* \in Q_Oが存在して \max_P \min_Q G(P,Q) =G(P^*,Q^*)= \min_Q \max_P G(P,Q) となる. この場合,競技者P,Qはそれぞれ戦略P^* \in P_0,Q^* \in Q_O 以外の戦略を選択すると損をすることになり,この意味で平衡状態になる.


\vspace{5cm} \par (図2.1 鞍点)

鞍点のない問題

P,Qの2人がじゃんけんをする. 負けたら10円を相手に払い,勝ったら相手から10円貰うというルールで, じゃんけんを繰り返す.

無論,「アイコ」の場合は,支払うお金,貰うお金とも0円である.

PQの出す手によって,貰えるお金,支払うお金がどうなるか, Pの立場で以下のような表になる.

利得表1 ファイル:Game01.jpg

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

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

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

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

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


ゲームの理論を創始し,この種の問題に解を与えたのが,ノイマン(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)で表しておく.


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

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

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

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

という計算を全て行うと

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\}

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

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

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

max \{ min_Q E(P,Q) |P \in P_O\}

が実現されるとなるようなPP_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\}

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

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

min \{ max_P E(P,Q) |Q \in Q_O \} が実現されるとなるようなQQ_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を加えておく.

利得表2 ファイル:Game02.jpg


これでは,一方的な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^*の最適戦略が求まる.

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


ゲーム理論

個人用ツール