「《ゲームの解の計算》」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【ゲームのかいのけいさん (computation of solutions of games) 】''' 1. 2人ゼロ和ゲームのマックスミニ戦略の計算  次のような[[利得行...')
 
 
(5人の利用者による、間の10版が非表示)
6行目: 6行目:
  
  
 +
<center>
 +
 +
[[画像:sk-0079-a-g-11-1.png]]
 +
 +
</center>
 +
 +
<!--
 +
\[
 
\begin{array}{c|ccc}
 
\begin{array}{c|ccc}
 
           & 1            & \ldots  & n                      \\ \hline
 
           & 1            & \ldots  & n                      \\ \hline
12行目: 20行目:
 
m        &  a_{m1}  & \ldots  & a_{mn}
 
m        &  a_{m1}  & \ldots  & a_{mn}
 
\end{array}
 
\end{array}
 +
\]
 +
-->
 +
  
  
[[プレイヤー]]1の[[混合戦略]]}$p = (p_1, p_2, \ldots, p_m)$, プレイヤー2の混合戦略を$q = (q_1, q_2, \ldots, q_n)$, $ 0 \leq p_i, q_j \leq 1 $, $ \sum_{i=1}^{m} p_i = 1$, $ \sum_{j=1}^{n} q_j = 1 $とするとき, プレイヤー1の[[マックスミニ戦略]]は, 次の線形計画問題の最適解として得られ, 最適値が[[マックスミニ値]]となる.
+
[[プレイヤー]]1の[[混合戦略]]を<math>p = (p_1, p_2, \ldots, p_m)\, </math>, プレイヤー2の混合戦略を<math>q = (q_1, q_2, \ldots, q_n)\, </math>, <math> 0 \leq p_i, q_j \leq 1 \, </math>, <math>\textstyle \sum_{i=1}^{m} p_i = 1\, </math>,   <math>\textstyle \sum_{j=1}^{n} q_j = 1\, </math> とするとき, プレイヤー1の[[マックスミニ戦略]]は, 次の線形計画問題の最適解として得られ, 最適値が[[マックスミニ値]]となる.
  
  
\begin{array}{ll}
+
<center>
 +
<math>\begin{array}{ll}
 
     \mbox{maximize}  & v \\
 
     \mbox{maximize}  & v \\
 
     \mbox{subject to} & a_{1j}p_1 + a_{2j}p_2 + \ldots + a_{mj}p_m \geq v  \  (j = 1, 2, \ldots, n), \\
 
     \mbox{subject to} & a_{1j}p_1 + a_{2j}p_2 + \ldots + a_{mj}p_m \geq v  \  (j = 1, 2, \ldots, n), \\
 
                       & p_1 + p_2 + \ldots + p_m = 1,\;\;  p_1,  p_2,  \ldots, p_m \geq 0.
 
                       & p_1 + p_2 + \ldots + p_m = 1,\;\;  p_1,  p_2,  \ldots, p_m \geq 0.
     \end{array}  
+
     \end{array}\, </math>
 +
</center>
  
  
プレイヤー2の[[ミニマックス戦略]]はこの問題の[[双対問題 (線形計画の)|双対問題]]を解いて求められる. 少なくとも一方のプレイヤーの[[純戦略]]が2個だけである場合には, マックスミニ戦略, ミニマックス戦略はより簡単に計算することができる. 例えば, $m=2$とすると,  プレイヤー1のマックスミニ戦略は,  
+
プレイヤー2の[[ミニマックス戦略]]はこの問題の[[双対問題 (線形計画の)|双対問題]]を解いて求められる. 少なくとも一方のプレイヤーの[[純戦略]]が2個だけである場合には, マックスミニ戦略, ミニマックス戦略はより簡単に計算することができる. 例えば, <math>m=2\, </math>とすると,  プレイヤー1のマックスミニ戦略は,  
  
\max_{0 \leq p_1 \leq 1} \min
+
 
 +
<center>
 +
<math>\max_{0 \leq p_1 \leq 1} \min
 
               \{a_{11}p_1 + a_{21}(1-p_1),  a_{12}p_1 + a_{22}(1-p_1),  
 
               \{a_{11}p_1 + a_{21}(1-p_1),  a_{12}p_1 + a_{22}(1-p_1),  
                 \ldots ,  a_{1n}p_1 + a_{2n}(1-p_1) \}  
+
                 \ldots ,  a_{1n}p_1 + a_{2n}(1-p_1) \}\, </math>
 +
</center>
 +
 
  
の解となる. いま, 各$j$について$ a_{1j}p_1 + a_{2j}(1-p_1) $のグラフを描き, $n$個のグラフの最小の部分をたどるグラフ (図1(a)の太線) を描く. このグラフの最大値を与える$p_1$$p^*$とすると, プレイヤー1のマックスミニ戦略は$(p^*, 1-p^*)$で与えられる. 図1(a)は$n=3$の場合である. プレイヤー2については, $p^*$を与える2つの戦略$j, j'$について同様の計算を行ってミニマックス戦略を求めることができる. 詳しくは, 例えば [4] を参照.  
+
の解となる. いま, 各jについて <math>a_{1j}p_1 + a_{2j}(1-p_1)\, </math> のグラフを描き, <math>n\, </math>個のグラフの最小の部分をたどるグラフ (図1(a)の太線) を描く. このグラフの最大値を与える<math>p_1\, </math><math>p^*\, </math>とすると, プレイヤー1のマックスミニ戦略は<math>(p^*, 1-p^*)\, </math>で与えられる. 図1(a)は<math>n=3\, </math>の場合である. プレイヤー2については, <math>p^*\, </math>を与える2つの戦略<math>j, j'\, </math>について同様の計算を行ってミニマックス戦略を求めることができる. 詳しくは, 例えば [4] を参照.  
  
 
2. 非ゼロ和ゲームのナッシュ均衡の計算
 
2. 非ゼロ和ゲームのナッシュ均衡の計算
  
 次のような$ 2 \times 2 $の[[利得双行列 (ゲームの)|利得双行列]]をもつ2人[[非ゼロ和ゲーム]]を考える.  
+
 次のような <math>2 \times 2\, </math> の[[利得双行列 (ゲームの)|利得双行列]]をもつ2人[[非ゼロ和ゲーム]]を考える.  
 +
 
  
 +
<center>
 +
[[画像:sk-0079-a-g-11-2.png]]
  
\begin{array}{c|cc}
+
</center>
 +
 
 +
<!--
 +
\[ \begin{array}{c|cc}
 
       &  1  &  2 \\  \hline
 
       &  1  &  2 \\  \hline
 
     1  &  a_{11}, b_{11}  &  a_{12}, b_{12} \\
 
     1  &  a_{11}, b_{11}  &  a_{12}, b_{12} \\
 
     2  &  a_{21}, b_{21}  & a_{22}, b_{22} \\
 
     2  &  a_{21}, b_{21}  & a_{22}, b_{22} \\
\end{array}  
+
\end{array} \]
 +
-->
  
  
プレイヤー1, 2の混合戦略を各々 $(p, 1-p)$$(q, 1-q)$, $ 0 \leq p, q \leq 1$とする.  
+
プレイヤー1, 2の混合戦略を各々 <math>(p, 1-p)\, </math><math>(q, 1-q)\, </math>,  <math>0 \leq p, q \leq 1\, </math>とする.  
  
 $ A_1 \equiv a_{11}q+a_{12}(1-q),  A_2 \equiv a_{21}q+a_{22}(1-q) $ とおくと, プレイヤー1の利得の期待値 (期待利得) は$ p A_1 + (1-p) A_2 $となるから, [[最適反応 (ゲーム理論における)|最適反応]]は$ A_1 > A_2 $のとき$ p=1 $, $ A_1 = A_2 $のとき$ 0 \leq p \leq 1 $, $ A_1 < A_2 $のとき$ p=0 $となる. 同様にプレイヤー2の最適反応は, $ B_1 = b_{11}p+b_{21}(1-p),  B_2 = b_{12}p+b_{22}(1-p) $とおいて, $ B_1 > B_2 $のとき$ q=1 $, $ B_1 = B_2 $のとき$ 0 \leq q \leq 1 $, $ B_1 < B_2 $のとき$ q=0 $となる. 従って, 両者の最適反応は, もし, $ a_{11}>a_{21},  a_{12}<a_{22},  b_{11}>b_{12},  b_{21}<b_{22} $であれば, 図1(b)のように表現される.  
+
 <math>A_1 \equiv a_{11}q+a_{12}(1-q),  A_2 \equiv a_{21}q+a_{22}(1-q) \, </math> とおくと, プレイヤー1の利得の期待値 (期待利得) は <math>p A_1 + (1-p) A_2\, </math> となるから, [[最適反応 (ゲーム理論における)|最適反応]]は <math>A_1 > A_2\, </math> のとき <math>p=1\, </math> , <math>A_1 = A_2\, </math> のとき <math>0 \leq p \leq 1\, </math> , <math>A_1 < A_2\, </math> のとき <math>p=0\, </math> となる. 同様にプレイヤー2の最適反応は, <math>B_1 = b_{11}p+b_{21}(1-p),  B_2 = b_{12}p+b_{22}(1-p)\, </math> とおいて, <math>B_1 > B_2\, </math> のとき <math>q=1\, </math> , <math>B_1 = B_2\, </math> のとき <math>0 \leq q \leq 1 , B_1 < B_2\, </math> のとき <math>q=0\, </math> となる. 従って, 両者の最適反応は, もし,   <math>a_{11}>a_{21},  a_{12}<a_{22},  b_{11}>b_{12},  b_{21}<b_{22}\, </math> であれば, 図1(b) のように表現される.  
  
  
\begin{figure}
+
<center><table><tr><td align=center>[[画像:0079-a-g-11fig.png|center|図1:2人ゲームのマックスミニ戦略およびナッシュ均衡の計算]]</td></tr>
\includegraphics[scale=0.8]{0079-a-g-11fig.eps}
+
<td align=center>図1:2人ゲームのマックスミニ戦略およびナッシュ均衡の計算
\caption{2人ゲームのマックスミニ戦略およびナッシュ均衡の計算} \label{A-G-11-f1}
+
</td></table></center>
\end{figure}
 
  
  
 [[ナッシュ均衡]]は両者の最適反応の交点 (図1(b)の3つの交点) で与えられるから, この場合には, 純戦略に対応する$ p=q=1 $$ p=q=0 $および, $ A_1 = A_2 $かつ$ B_1 = B_2 $を満たす混合戦略に対応する$ p=(b_{22}-b_{21})/(b_{11}-b_{12} + b_{22}-b_{21}) $, $ q=(a_{12}-a_{22})/(a_{21}-a_{11} + a_{12}-a_{22}) $の合計3通りのナッシュ均衡が存在する. $ a_{11}>a_{21},  a_{12}<a_{22},  b_{11}>b_{12},  b_{21}<b_{22}$以外の場合など, 詳しくは, 例えば [4] を参照.  
+
 [[ナッシュ均衡]]は両者の最適反応の交点 (図1(b)の3つの交点) で与えられるから, この場合には, 純戦略に対応する <math>p=q=1\, </math> <math>p=q=0\, </math> および, <math>A_1 = A_2\, </math> かつ <math>B_1 = B_2\, </math> を満たす混合戦略に対応する <math>p=(b_{22}-b_{21})/(b_{11}-b_{12} + b_{22}-b_{21})\, </math> ,  <math>q=(a_{12}-a_{22})/(a_{21}-a_{11} + a_{12}-a_{22})\, </math> の合計3通りのナッシュ均衡が存在する.   <math>a_{11}>a_{21},  a_{12}<a_{22},  b_{11}>b_{12},  b_{21}<b_{22}\, </math>以外の場合など, 詳しくは, 例えば [4] を参照.  
  
 $ 2 \times 2 $よりも大きな利得行列をもつ2人非ゼロ和ゲームのナッシュ均衡を求める方法としては, シャープレイのラベル法}{シャープレイ(L. S. Shapley)のラベル法}(Shapley's labelling method) [6] がある. $3$人以上のプレイヤーからなる[[戦略形ゲーム]]においては, [[不動点アルゴリズム]]を用いて, ナッシュ均衡の近似値を計算することができる. [7] を参照.  
+
 <math>2 \times 2\, </math> よりも大きな利得行列をもつ2人非ゼロ和ゲームのナッシュ均衡を求める方法としては, [[シャープレイのラベル法|シャープレイ(L. S. Shapley)のラベル法]](Shapley's labelling method) [6] がある. <math>3\, </math>人以上のプレイヤーからなる[[戦略形ゲーム]]においては, [[不動点アルゴリズム]]を用いて, ナッシュ均衡の近似値を計算することができる. [7] を参照.  
  
 
 [[展開形ゲーム]]における[[部分ゲーム完全均衡]], [[完全均衡]], [[逐次均衡]]などの計算については, [4] を参照.  
 
 [[展開形ゲーム]]における[[部分ゲーム完全均衡]], [[完全均衡]], [[逐次均衡]]などの計算については, [4] を参照.  
63行目: 86行目:
 
3. 提携形 (特性関数形) ゲームの解の計算
 
3. 提携形 (特性関数形) ゲームの解の計算
  
 提携形ゲーム}{提携形ゲーム}$(N, v)$のコア}{コア}の配分$ (x_i)_{i \in N }$を計算するために, まず$ 2^n-1 $本の制約式をもつ次の線形計画問題P$_1$を考える($ |N|=n,  x(S)=\sum_{i \in S} x_i $).  
+
 [[提携形ゲーム]]<math>(N, v)\, </math>の[[コア]]の配分 <math>(x_i)_{i \in N }\, </math>を計算するために, まず <math>2^n-1\, </math> 本の制約式をもつ次の線形計画問題<math>P_1\, </math>を考える (<math>\textstyle |N|=n,  x(S)=\sum_{i \in S} x_i \, </math>).  
  
  
\begin{array}{lll}
+
<center>
 +
<math>\begin{array}{lll}
 
     \mbox{minimize}  & e \\
 
     \mbox{minimize}  & e \\
 
     \mbox{subject to} & x(S) + e \geq v(S) &
 
     \mbox{subject to} & x(S) + e \geq v(S) &
 
                         (S \subset N, \ S \neq N, \emptyset), \\
 
                         (S \subset N, \ S \neq N, \emptyset), \\
 
                       & x(N) = v(N).  
 
                       & x(N) = v(N).  
     \end{array}  
+
     \end{array}\, </math>
   
+
</center>
   
+
 
問題P$_1$の最適解において, $ e \leq 0 $となっているならば, ゲーム$(N, v)$のコアは空集合ではなく, $ e \leq 0 $を満たす実行可能解すべてからなる集合がコアとなる. また,  コアが空であろうと非空であろうと, 問題P$_1$の最適解の全体はゲーム$(N, v)$の[[最小コア (ゲーム理論の)|最小コア]]になる.  
+
 
 +
問題<math>P_1\, </math>の最適解において,   <math>e \leq 0\, </math> となっているならば, ゲーム<math>(N, v)\, </math>のコアは空集合ではなく, <math>e \leq 0\, </math> を満たす実行可能解すべてからなる集合がコアとなる. また,  コアが空であろうと非空であろうと, 問題<math>P_1\, </math>の最適解の全体はゲーム<math>(N, v)\, \, </math>の[[最小コア (ゲーム理論の)|最小コア]]になる.  
  
 [[仁]]は, 線形計画問題を繰り返し解く[[コペロウィッツ (A. Kopelowitz)のアルゴリズム]] (Kopelowitz' algorithm) [2] によって求められる. まず,  問題P$_1$の最適解における$e$の値を$e_1$とする. もしも最適解が唯一でない場合は, すべての最適解を求め, 不等式制約条件がその全最適解において等号で成立しているような$S$の族を$A_1$とおく. さらに, $A_1$に含まれるすべての$S$に対して問題P$_1$の制約式$ x(S) + e \geq v(S) $$ x(S) + e_1 = v(S) $に置き換えて新たな問題P$_2$をつくり, その最適解を求める. このプロセスを繰り返し, あるステップで, 最適解が唯一であればそれが仁の配分である. このアルゴリズムは$n-1$回以内の繰り返しで必ず終了する. ただし, 1回の繰り返しの中での計算量は膨大になることがある. 仁のより効率的な計算方法については, [1], [5] を参照.  
+
 [[仁]]は, 線形計画問題を繰り返し解く[[コペロウィッツのアルゴリズム]] (Kopelowitz' algorithm) [2] によって求められる. まず,  問題<math>P_1\, </math>の最適解における<math>e\, </math>の値を<math>e_1\, </math>とする. もしも最適解が唯一でない場合は, すべての最適解を求め, 不等式制約条件がその全最適解において等号で成立しているような<math>S\, </math>の族を<math>A_1\, </math>とおく. さらに, <math>A_1\, </math>に含まれるすべての<math>S\, </math>に対して問題<math>P_1\, </math>の制約式 <math>x(S) + e \geq v(S)\, </math> <math>x(S) + e_1 = v(S)\, </math> に置き換えて新たな問題<math>P_2\, </math>をつくり, その最適解を求める. このプロセスを繰り返し, あるステップで, 最適解が唯一であればそれが仁の配分である. このアルゴリズムは<math>n-1\, </math>回以内の繰り返しで必ず終了する. ただし, 1回の繰り返しの中での計算量は膨大になることがある. 仁のより効率的な計算方法については, [1], [5] を参照.  
  
 
 [[シャープレイ値]]の計算方法については, [3] を参照.  
 
 [[シャープレイ値]]の計算方法については, [3] を参照.  
83行目: 108行目:
  
 
----
 
----
 
 
'''参考文献'''
 
'''参考文献'''
  
 
[1] G. Bruyneel, "Computation of the Nucleolus of a Game by Means of Minimal Balanced Sets," ''Operations Research Verfahren'', '''34''' (1979), 35-51.  
 
[1] G. Bruyneel, "Computation of the Nucleolus of a Game by Means of Minimal Balanced Sets," ''Operations Research Verfahren'', '''34''' (1979), 35-51.  
  
[2] A. Kopelowitz, "Computation of the Kernels of Simple Games and the Nucleolus of $n$-Person Games," "Research Program in Game Theory and Mathematical Economics", RM 31, The Hebrew University of Jerusalem, 1967.  
+
[2] A. Kopelowitz, "Computation of the Kernels of Simple Games and the Nucleolus of n-Person Games," "Research Program in Game Theory and Mathematical Economics", RM 31, The Hebrew University of Jerusalem, 1967.  
  
 
[3] 武藤滋夫, 小野理恵, 「投票システムのゲーム分析」, 日科技連出版社,  1998.  
 
[3] 武藤滋夫, 小野理恵, 「投票システムのゲーム分析」, 日科技連出版社,  1998.  
94行目: 118行目:
 
[4] 岡田章, 「ゲーム理論」, 有斐閣, 1996.  
 
[4] 岡田章, 「ゲーム理論」, 有斐閣, 1996.  
  
[5] J. K. Sankaran, "On Finding the Nucleolus of an $n$-Person Cooperative Game," ''International Journal of Game Theory'', '''19''' (1991), 329-338.  
+
[5] J. K. Sankaran, "On Finding the Nucleolus of an n-Person Cooperative Game," ''International Journal of Game Theory'', '''19''' (1991), 329-338.  
  
 
[6] L. S. Shapley, "A Note on the Lemke-Howson Algorithm," ''Mathematical Programming Study'', '''1''' (1974), 175-189.  
 
[6] L. S. Shapley, "A Note on the Lemke-Howson Algorithm," ''Mathematical Programming Study'', '''1''' (1974), 175-189.  
  
 
[7] Z. -F. Yang, ''Computing Equilibria and Fixed Points'', Kluwer Academic Publishers, 1999.
 
[7] Z. -F. Yang, ''Computing Equilibria and Fixed Points'', Kluwer Academic Publishers, 1999.
 +
 +
[[category:ゲーム理論|げーむのかいのけいさん]]

2007年8月9日 (木) 14:48時点における最新版

【ゲームのかいのけいさん (computation of solutions of games) 】

1. 2人ゼロ和ゲームのマックスミニ戦略の計算

 次のような利得行列をもつ2人ゼロ和ゲームを考える.


Sk-0079-a-g-11-1.png



プレイヤー1の混合戦略, プレイヤー2の混合戦略を, , , とするとき, プレイヤー1のマックスミニ戦略は, 次の線形計画問題の最適解として得られ, 最適値がマックスミニ値となる.



プレイヤー2のミニマックス戦略はこの問題の双対問題を解いて求められる. 少なくとも一方のプレイヤーの純戦略が2個だけである場合には, マックスミニ戦略, ミニマックス戦略はより簡単に計算することができる. 例えば, とすると, プレイヤー1のマックスミニ戦略は,



の解となる. いま, 各jについて のグラフを描き, 個のグラフの最小の部分をたどるグラフ (図1(a)の太線) を描く. このグラフの最大値を与えるとすると, プレイヤー1のマックスミニ戦略はで与えられる. 図1(a)はの場合である. プレイヤー2については, を与える2つの戦略について同様の計算を行ってミニマックス戦略を求めることができる. 詳しくは, 例えば [4] を参照.

2. 非ゼロ和ゲームのナッシュ均衡の計算

 次のような 利得双行列をもつ2人非ゼロ和ゲームを考える.


Sk-0079-a-g-11-2.png


プレイヤー1, 2の混合戦略を各々 , , とする.

  とおくと, プレイヤー1の利得の期待値 (期待利得) は となるから, 最適反応 のとき , のとき , のとき となる. 同様にプレイヤー2の最適反応は, とおいて, のとき , のとき のとき となる. 従って, 両者の最適反応は, もし, であれば, 図1(b) のように表現される.


図1:2人ゲームのマックスミニ戦略およびナッシュ均衡の計算
図1:2人ゲームのマックスミニ戦略およびナッシュ均衡の計算


 ナッシュ均衡は両者の最適反応の交点 (図1(b)の3つの交点) で与えられるから, この場合には, 純戦略に対応する および, かつ を満たす混合戦略に対応する , の合計3通りのナッシュ均衡が存在する. 以外の場合など, 詳しくは, 例えば [4] を参照.

  よりも大きな利得行列をもつ2人非ゼロ和ゲームのナッシュ均衡を求める方法としては, シャープレイ(L. S. Shapley)のラベル法(Shapley's labelling method) [6] がある. 人以上のプレイヤーからなる戦略形ゲームにおいては, 不動点アルゴリズムを用いて, ナッシュ均衡の近似値を計算することができる. [7] を参照.

 展開形ゲームにおける部分ゲーム完全均衡, 完全均衡, 逐次均衡などの計算については, [4] を参照.

3. 提携形 (特性関数形) ゲームの解の計算

 提携形ゲームコアの配分 を計算するために, まず 本の制約式をもつ次の線形計画問題を考える ().



問題の最適解において, となっているならば, ゲームのコアは空集合ではなく, を満たす実行可能解すべてからなる集合がコアとなる. また, コアが空であろうと非空であろうと, 問題の最適解の全体はゲーム最小コアになる.

 は, 線形計画問題を繰り返し解くコペロウィッツのアルゴリズム (Kopelowitz' algorithm) [2] によって求められる. まず, 問題の最適解におけるの値をとする. もしも最適解が唯一でない場合は, すべての最適解を求め, 不等式制約条件がその全最適解において等号で成立しているようなの族をとおく. さらに, に含まれるすべてのに対して問題の制約式 に置き換えて新たな問題をつくり, その最適解を求める. このプロセスを繰り返し, あるステップで, 最適解が唯一であればそれが仁の配分である. このアルゴリズムは回以内の繰り返しで必ず終了する. ただし, 1回の繰り返しの中での計算量は膨大になることがある. 仁のより効率的な計算方法については, [1], [5] を参照.

 シャープレイ値の計算方法については, [3] を参照.



参考文献

[1] G. Bruyneel, "Computation of the Nucleolus of a Game by Means of Minimal Balanced Sets," Operations Research Verfahren, 34 (1979), 35-51.

[2] A. Kopelowitz, "Computation of the Kernels of Simple Games and the Nucleolus of n-Person Games," "Research Program in Game Theory and Mathematical Economics", RM 31, The Hebrew University of Jerusalem, 1967.

[3] 武藤滋夫, 小野理恵, 「投票システムのゲーム分析」, 日科技連出版社, 1998.

[4] 岡田章, 「ゲーム理論」, 有斐閣, 1996.

[5] J. K. Sankaran, "On Finding the Nucleolus of an n-Person Cooperative Game," International Journal of Game Theory, 19 (1991), 329-338.

[6] L. S. Shapley, "A Note on the Lemke-Howson Algorithm," Mathematical Programming Study, 1 (1974), 175-189.

[7] Z. -F. Yang, Computing Equilibria and Fixed Points, Kluwer Academic Publishers, 1999.