支配戦略

支配関係（しはいかんけい、（英: dominance relation）はあるプレイヤーが選択可能な 2 つの戦略間に見出される、他プレイヤーの戦略選択に依らない利得の大小関係である^[3]。

強支配

さらに見る 利得行列 ...

利得行列 ${\displaystyle \textstyle A_{i}}$

${\displaystyle z_{-i}}$ ​ ${\displaystyle \delta _{i}}$	${\displaystyle z_{-i,1}}$	${\displaystyle z_{-i,2}}$
${\displaystyle x_{i}}$	${\displaystyle \textstyle 2}$	${\displaystyle \textstyle 4}$
${\displaystyle y_{i}}$	${\displaystyle \textstyle 1}$	${\displaystyle \textstyle 3}$

閉じる

強支配（きょうしはい、（英: strict dominance）は他プレイヤーの戦略に依らず、一方の戦略の利得が他方の戦略の利得より常に大きいという支配関係である。

戦略 ${\displaystyle \textstyle x_{i},y_{i}\in \Delta _{i}}$ が次の関係、

${\displaystyle \forall z\in \Theta$ ;\quad u_{i}(x_{i},z_{-i})>u_{i}(y_{i},z_{-i})}

を満たすとき、${\displaystyle \textstyle x_{i}}$ と ${\displaystyle \textstyle y_{i}}$ は強支配の関係にあるという。

このとき支配の方向に着目して「 ${\displaystyle \textstyle x_{i}}$ は ${\displaystyle \textstyle y_{i}}$ を強支配する」(英: ${\displaystyle x_{i}}$ strictly dominates ${\displaystyle y_{i}}$)^{[3][注 2]}、「 ${\displaystyle \textstyle y_{i}}$ は ${\displaystyle \textstyle x_{i}}$ に強支配される」(英: ${\displaystyle y_{i}}$ is strictly dominated by ${\displaystyle x_{i}}$) という。${\displaystyle \textstyle y_{i}}$ は強支配される戦略 (英: strictly dominated strategy) という。

例として、プレイヤー ${\displaystyle \textstyle i}$ を利得行列 ${\displaystyle \textstyle A_{i}}$で表現する戦略型有限確定ゲームを考える（表参照）。このとき ${\displaystyle \textstyle z_{-i,1}}$ に関して ${\displaystyle \textstyle u_{i}(x_{i},z_{-i,1})=2>u_{i}(y_{i},z_{-i,1})=1}$、${\displaystyle \textstyle z_{-i,2}}$ に関して ${\displaystyle \textstyle u_{i}(x_{i},z_{-i,2})=4>u_{i}(y_{i},z_{-i,2})=3}$ が成立しているため、他プレイヤーの戦略に依らず ${\displaystyle \textstyle x_{i}}$ の利得は ${\displaystyle \textstyle y_{i}}$ の利得より常に大きい。よって ${\displaystyle \textstyle x_{i}}$ は ${\displaystyle \textstyle y_{i}}$ を強支配する。

弱支配

さらに見る 利得行列 ...

利得行列 ${\displaystyle \textstyle B_{i}}$

${\displaystyle z_{-i}}$ ​ ${\displaystyle \delta _{i}}$	${\displaystyle z_{-i,1}}$	${\displaystyle z_{-i,2}}$
${\displaystyle x_{i}}$	${\displaystyle \textstyle 1}$	${\displaystyle \textstyle 4}$
${\displaystyle y_{i}}$	${\displaystyle \textstyle 1}$	${\displaystyle \textstyle 3}$

閉じる

弱支配（じゃくしはい、（英: weak dominance）は他プレイヤーの戦略に依らず、一方の戦略の利得が「常に他方の戦略の利得以上」かつ「『常に他方と一致』ではない」という支配関係である^[4]。

戦略 ${\displaystyle \textstyle x_{i},y_{i}\in \Delta _{i}}$ が次の関係、

${\displaystyle \forall z\in \Theta ,\ u_{i}(x_{i},z_{-i})\geq u_{i}(y_{i},z_{-i});\quad {\text{and}}\quad \exists z\in \Theta ,\ u_{i}(x_{i},z_{-i})>u_{i}(y_{i},z_{-i})}$

を満たすとき、${\displaystyle \textstyle x_{i}}$ と ${\displaystyle \textstyle y_{i}}$ は弱支配の関係にあるという^[4]。

このとき支配の方向に着目して「 ${\displaystyle \textstyle x_{i}}$ は ${\displaystyle \textstyle y_{i}}$ を弱支配する」(英: ${\displaystyle x_{i}}$ weakly dominates ${\displaystyle y_{i}}$)^[3][4]、「 ${\displaystyle \textstyle y_{i}}$ は ${\displaystyle \textstyle x_{i}}$ に弱支配される」(英: ${\displaystyle y_{i}}$ is weakly dominated by ${\displaystyle x_{i}}$) という。${\displaystyle \textstyle y_{i}}$ は弱支配される戦略 (英: weakly dominated strategy) という。

例として、プレイヤー ${\displaystyle \textstyle i}$ を利得行列 ${\displaystyle \textstyle B_{i}}$で表現する戦略型有限確定ゲームを考える（表参照）。このとき ${\displaystyle \textstyle z_{-i,1}}$ に関して ${\displaystyle \textstyle u_{i}(x_{i},z_{-i,1})=1\geq u_{i}(y_{i},z_{-i,1})=1}$、${\displaystyle \textstyle z_{-i,2}}$ に関して ${\displaystyle \textstyle u_{i}(x_{i},z_{-i,2})=4>u_{i}(y_{i},z_{-i,2})=3}$ が成立しているため、他プレイヤーの戦略に依らず ${\displaystyle \textstyle x_{i}}$ の利得は ${\displaystyle \textstyle y_{i}}$ の利得以上であり、かつ、${\displaystyle \textstyle z_{-i,2}}$ では ${\displaystyle \textstyle x_{i}}$ の利得が ${\displaystyle \textstyle y_{i}}$ の利得より大きい。よって ${\displaystyle \textstyle x_{i}}$ は ${\displaystyle \textstyle y_{i}}$ を弱支配する。

あるプレイヤーが合理的 (rational) であるとは、そのプレイヤーが強支配される戦略を決して選択しないことである^[3]。また、どのプレイヤーも強支配戦略を持つならば、その組による戦略プロファイルを支配戦略均衡 (dominant strategy equilibrium)^[1]という。支配戦略均衡の存在するゲームでは、全てのプレイヤーが合理的であるならば支配戦略均衡が実現する。しかし、支配戦略均衡は必ずしもパレート効率的であるとは限らない。囚人のジレンマはパレート効率的でない支配戦略均衡をもつゲームの典型例である。

ある戦略プロファイルに対して最適反応となる戦略は強支配されず、したがって、ナッシュ均衡をなす戦略はいずれも強支配されない。特に、完全混合戦略のみからなる戦略プロファイルに対して最適反応となる戦略は弱支配されず、また、弱支配されない戦略のみからなるナッシュ均衡 (支配されない (undominated) ナッシュ均衡) はいかなる戦略型ゲームにも必ず存在することが知られている^{[注 3]}。

強支配される戦略の繰り返し消去 (Iterated elimination of strictly dominated strategies (IESDS))^{[注 4]}とは、基本的なゲームの解法のひとつである。

戦略型ゲーム G が与えられたときに、次のように G ^t = (I, S ^t = ∏_i∈I S_i^t, π ^t ) (t ∈ ℕ) を定める。

1. G ⁰ = G とする。
2. 次に、t ≥ 0 について、以下のように G ^t から G ^{t +1} を定める (帰納的定義)。
   1. S_i^{t +1} ⊂ S_i^t を、プレイヤー i ∈ I の純粋戦略のうち、G^t において強支配されない戦略の集合とする^{[注 5]}。これにより純粋戦略空間 S ^{t +1} = ∏_i∈I S_i^{t +1} ⊂ S ^t が定まる。
   2. (結合)純粋戦略利得関数をπ ^{t +1} = π ^t |_{S ^{t +1}} とする。

与えられたゲーム G が有限ゲームの場合は、ある T ∈ ℕ が存在して、任意の t ∈ {n ∈ ℕ | t ≥ T} に対して G ^t = G ^{t +1} となる。このとき、G ^T の各純粋戦略は反復的に強支配されない (not iteratively strictly dominated)^[3]という。特に、各プレイヤーの純粋戦略がそれぞれ一つずつしか残らない場合、G は強支配により可解 (strictly dominance solvable)^{[3][注 6]}であるという。この解の実現には、全プレイヤーが合理的であることに加えて、「全プレイヤーが合理的である」という共有知識が必要である。上記の説明では全プレイヤーについて強支配される戦略の消去を同時に行うが、最終的な G ^T は、各プレイヤーを順に周回して戦略を消去する、戦略を一つずつ消去する、といった戦略の消去順によらず一意である^{[1][3][注 7]}。

以上と同様の繰り返し消去を弱支配される戦略について行うことも可能だが、一部のナッシュ均衡が消去される可能性があり、また、最終的な G ^T は戦略の消去順によって異なることがある^{[1][注 8]}。

IESDSでは純粋戦略のみについて消去をするが、これは^{[注 5]}に述べたように、強支配される純粋戦略の消去が同時に強支配される混合戦略の消去になっていることによる。他方、ある純粋戦略が他のいかなる純粋戦略にも強支配されないことは、その純粋戦略が強支配されないことを含意しない。例えば、右の双行列ゲームにおいてプレイヤーBの純粋戦略の間に支配関係は無いが、b₁とb₃をそれぞれ0.5すつの確率で選択する混合戦略はb₂を強支配する。