強支配される戦略の繰り返し消去
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/13 02:32 UTC 版)
「支配戦略」の記事における「強支配される戦略の繰り返し消去」の解説
強支配される戦略の繰り返し消去 (Iterated elimination of strictly dominated strategies (IESDS))とは、基本的なゲームの解法のひとつである。 戦略型ゲーム G が与えられたときに、次のように G t = (I, S t = ∏i∈I Sit, π t ) (t ∈ ℕ) を定める。 G 0 = G とする。 次に、t ≥ 0 について、以下のように G t から G t +1 を定める (帰納的定義)。Sit +1 ⊂ Sit を、プレイヤー i ∈ I の純粋戦略のうち、Gt において強支配されない戦略の集合とする。これにより純粋戦略空間 S t +1 = ∏i∈I Sit +1 ⊂ S t が定まる。 (結合)純粋戦略利得関数をπ t +1 = π t |S t +1 とする。 与えられたゲーム G が有限ゲームの場合は、ある T ∈ ℕ が存在して、任意の t ∈ {n ∈ ℕ | t ≥ T} に対して G t = G t +1 となる。このとき、G T の各純粋戦略は反復的に強支配されない (not iteratively strictly dominated)という。特に、各プレイヤーの純粋戦略がそれぞれ一つずつしか残らない場合、G は強支配により可解 (strictly dominance solvable)であるという。この解の実現には、全プレイヤーが合理的であることに加えて、「全プレイヤーが合理的である」という共有知識が必要である。上記の説明では全プレイヤーについて強支配される戦略の消去を同時に行うが、最終的な G T は、各プレイヤーを順に周回して戦略を消去する、戦略を一つずつ消去する、といった戦略の消去順によらず一意である。 以上と同様の繰り返し消去を弱支配される戦略について行うことも可能だが、一部のナッシュ均衡が消去される可能性があり、また、最終的な G T は戦略の消去順によって異なることがある。 B A b1b2b3a10, 3 1, 1 2, 0 a21, 0 3, 2 0, 5 IESDSでは純粋戦略のみについて消去をするが、これはに述べたように、強支配される純粋戦略の消去が同時に強支配される混合戦略の消去になっていることによる。他方、ある純粋戦略が他のいかなる純粋戦略にも強支配されないことは、その純粋戦略が強支配されないことを含意しない。例えば、右の双行列ゲームにおいてプレイヤーBの純粋戦略の間に支配関係は無いが、b1とb3をそれぞれ0.5すつの確率で選択する混合戦略はb2を強支配する。
※この「強支配される戦略の繰り返し消去」の解説は、「支配戦略」の解説の一部です。
「強支配される戦略の繰り返し消去」を含む「支配戦略」の記事については、「支配戦略」の概要を参照ください。
- 強支配される戦略の繰り返し消去のページへのリンク
