《ゲームの解の計算》

提供: ORWiki
2007年7月18日 (水) 17:29時点における122.17.2.240 (トーク)による版
ナビゲーションに移動 検索に移動

【ゲームのかいのけいさん (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.