支配戦略 (しはいせんりゃく、)とは、戦略型ゲームにおけるあるプレイヤーの戦略で、他のプレイヤーの戦略の選択によらず他の全ての戦略“よりも” (あるいは“以上に”) 高い利得を得られる戦略のことである。
以下、プレイヤーの集合を 、混合戦略空間を 、混合戦略利得関数を とする。また、戦略 と戦略プロファイル のもとで、戦略プロファイル は、プレイヤー が戦略 を選択し、それ以外のプレイヤーが にしたがって戦略を選択する戦略プロファイルを表す。
支配戦略はと強支配戦略に二分される。弱支配戦略は、戦略 が任意の戦略 を弱支配するときの で定義される。
支配関係 はあるプレイヤーが選択可能な 2 つの戦略間に見出される、他プレイヤーの戦略選択に依らない利得の大小関係である。
強支配 +利得行列 は他プレイヤーの戦略に依らず、一方の戦略の利得が他方の戦略の利得より常に大きいという支配関係である。
戦略 が次の関係、
を満たすとき、 と は強支配の関係にあるという。
このとき支配の方向に着目して「 は を強支配する」()、「 は に強支配される」() という。 は強支配される戦略 () という。
例として、プレイヤー を利得行列 で表現する戦略型有限確定ゲームを考える（表参照）。このとき に関して 、 に関して が成立しているため、他プレイヤーの戦略に依らず の利得は の利得より常に大きい。よって は を強支配する。
弱支配 +利得行列 は他プレイヤーの戦略に依らず、一方の戦略の利得が「常に他方の戦略の利得以上」かつ「『常に他方と一致』ではない」という支配関係である。
戦略 が次の関係、
を満たすとき、 と は弱支配の関係にあるという。
このとき支配の方向に着目して「 は を弱支配する」()、「 は に弱支配される」() という。 は弱支配される戦略 () という。
例として、プレイヤー を利得行列 で表現する戦略型有限確定ゲームを考える（表参照）。このとき に関して 、 に関して が成立しているため、他プレイヤーの戦略に依らず の利得は の利得以上であり、かつ、 では の利得が の利得より大きい。よって は を弱支配する。 合理性と支配戦略均衡 あるプレイヤーが合理的 (rational) であるとは、そのプレイヤーが強支配される戦略を決して選択しないことである。また、どのプレイヤーも強支配戦略を持つならば、その組による戦略プロファイルを支配戦略均衡 (dominant strategy equilibrium)という。支配戦略均衡の存在するゲームでは、全てのプレイヤーが合理的であるならば支配戦略均衡が実現する。しかし、支配戦略均衡は必ずしもパレート効率的であるとは限らない。囚人のジレンマはパレート効率的でない支配戦略均衡をもつゲームの典型例である。
最適反応およびナッシュ均衡との関連 ある戦略プロファイルに対して最適反応となる戦略は強支配されず、したがって、ナッシュ均衡をなす戦略はいずれも強支配されない。特に、完全混合戦略のみからなる戦略プロファイルに対して最適反応となる戦略は弱支配されず、また、弱支配されない戦略のみからなるナッシュ均衡 (支配されない (undominated) ナッシュ均衡) はいかなる戦略型ゲームにも必ず存在することが知られている。
強支配される戦略の繰り返し消去 強支配される戦略の繰り返し消去 (Iterated elimination of strictly dominated strategies (IESDS))「繰り返し」は「反復(的)」や「逐次(的)」とされることもある。「消去」は「削除」とされることもある。とは、基本的なゲームの解法のひとつである。
戦略型ゲーム が与えられたときに、次のように を定める。
とする。 次に、 について、以下のように から を定める (帰納的定義)。 を、プレイヤー の純粋戦略のうち、 において強支配されない戦略の集合とする強支配される純粋戦略を選択する確率が正である混合戦略は必ず強支配される戦略である。なぜならば、強支配される純粋戦略を選択する代わりにその戦略を強支配している純粋戦略を選択すれば任意の戦略プロファイルに対して利得がより大きくなるからである。。これにより純粋戦略空間 が定まる。 (結合)純粋戦略利得関数を とする。
与えられたゲーム が有限ゲームの場合は、ある が存在して、任意の に対して となる。このとき、 の各純粋戦略は反復的に強支配されない (not iteratively strictly dominated)という。特に、各プレイヤーの純粋戦略がそれぞれ一つずつしか残らない場合、 は強支配により可解 (strictly dominance solvable)であるという。この解の実現には、全プレイヤーが合理的であることに加えて、「全プレイヤーが合理的である」という共有知識が必要である。上記の説明では全プレイヤーについて強支配される戦略の消去を同時に行うが、最終的な は、各プレイヤーを順に周回して戦略を消去する、戦略を一つずつ消去する、といった戦略の消去順によらず一意である強支配関係にある2戦略について、他プレイヤーの純粋戦略の削除によって厳密に利得が異なる戦略プロファイルが全て消去されることは無く、必ず強支配関係が保たれる。。
以上と同様の繰り返し消去を弱支配される戦略について行うことも可能だが、一部のナッシュ均衡が消去される可能性があり、また、最終的な は戦略の消去順によって異なることがある弱支配関係にある2戦略について、他プレイヤーの純粋戦略の削除によって厳密に利得が異なる戦略プロファイルが全て消去された場合、もはや弱支配関係が成り立たない。。
b1 b2 b3 a1 0, 3 1, 1 2, 0 a2 1, 0 3, 2 0, 5 IESDSでは純粋戦略のみについて消去をするが、これはに述べたように、強支配される純粋戦略の消去が同時に強支配される混合戦略の消去になっていることによる。他方、ある純粋戦略が他のいかなる純粋戦略にも強支配されないことは、その純粋戦略が強支配されないことを含意しない。例えば、右の双行列ゲームにおいてプレイヤーBの純粋戦略の間に支配関係は無いが、b1とb3をそれぞれ0.5すつの確率で選択する混合戦略はb2を強支配する。
注釈
出典
参考文献
関連項目 支配戦略 強支配戦略 弱支配戦略 非協力ゲーム 社会的ジレンマ 囚人のジレンマ 共有知識 解概念 ナッシュ均衡 リスク支配