《ゲームの解の計算》

出典: ORWiki

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

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

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


画像:sk-0079-a-g-11-1.png



プレイヤー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 \,, \textstyle \sum_{i=1}^{m} p_i = 1\,, \textstyle \sum_{j=1}^{n} q_j = 1\, とするとき, プレイヤー1のマックスミニ戦略は, 次の線形計画問題の最適解として得られ, 最適値がマックスミニ値となる.


\begin{array}{ll} \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), \\ & p_1 + p_2 + \ldots + p_m = 1,\;\; p_1, p_2, \ldots, p_m \geq 0. \end{array}\,


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


\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), \ldots , a_{1n}p_1 + a_{2n}(1-p_1) \}\,


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

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

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


画像:sk-0079-a-g-11-2.png


プレイヤー1, 2の混合戦略を各々 (p, 1-p)\,, (q, 1-q)\,, 0 \leq p, q \leq 1\,とする.

　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}\, であれば, 図１(b) のように表現される.


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


　ナッシュ均衡は両者の最適反応の交点 (図１(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] を参照.

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

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

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

　提携形ゲーム(N, v)\,のコアの配分 (x_i)_{i \in N }\,を計算するために, まず 2^n-1\, 本の制約式をもつ次の線形計画問題P_1\,を考える (\textstyle |N|=n, x(S)=\sum_{i \in S} x_i \,).


\begin{array}{lll} \mbox{minimize} & e \\ \mbox{subject to} & x(S) + e \geq v(S) & (S \subset N, \ S \neq N, \emptyset), \\ & x(N) = v(N). \end{array}\,


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

　仁は, 線形計画問題を繰り返し解くコペロウィッツのアルゴリズム (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] を参照.

　シャープレイ値の計算方法については, [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.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E8%A7%A3%E3%81%AE%E8%A8%88%E7%AE%97%E3%80%8B" より作成