合理化可能性

ゲーム理論において合理化可能性 (ごうりかかのうせい，英: rationalisability, 独: Rationalisierbarkeit) とは，ナッシュ均衡の一般化である解概念のひとつ．合理化可能性は，決して最適反応にならないような戦略の逐次消去にもとづいている．この消去の過程を生き残った戦略を，合理化可能であるという．プレーヤーの行動に関する根本的な仮定に，ゲームの構造についての知識と，合理性についての共有知識がある．合理化可能性の概念は，はじめ Bernheim (1984) と Pearce (1984) によって独立に導入され，その後 Aumann (1987) と Brandenburger and Dekel (1987) で用いられた． Bernheim (1984) と Pearce (1984) は，合理性についての仮定だけから，プレーヤーたちの行動に関する個人の予想に，どのような制約が課されるかということを問題にした．彼らは，ゲームの構造と，プレーヤーが全員合理的であるという事実とが共有知識であるとして，どんな戦略が合理化可能かを検討した．プレーヤーの行動に課される制約は，それぞれの行動がこの共有知識と整合的であるということである．合理化可能戦略に関する中心的な結果は次のもの： ある戦略が合理化可能 (rationalisable, rationalisierbar) であるとは，それがほかの合理化可能戦略に対して最適反応 (best response, beste Antwort) になっているということである．したがって， ナッシュ均衡を構成する各戦略は，合理化可能である． 以下の用語は，合理化可能性の定義に密接に関係するものである． 予想 (信念) プレーヤー i にとって，相手プレーヤーの戦略の選択 σ − i {\displaystyle \sigma _{-i}} に関する予想は，確率分布 σ − i ∈ ∏ j ≠ i Σ j {\displaystyle \textstyle \sigma _{-i}\in \prod _{j\neq i}\Sigma _{j}} である．ここで Sj は各プレーヤー j の戦略集合で， Σ j {\displaystyle \Sigma _{j}} は Sj 上の確率分布の集合である．この定義で，プレーヤー i は，相手プレーヤーが独立に行動すると予想している． 合理的なプレーヤー 合理的なプレーヤーは，最適戦略である σ i {\displaystyle \sigma _{i}} について，相手プレーヤーの戦略の選択に関する可能な予想 σ − i {\displaystyle \sigma _{-i}} があるとき，戦略 σ i {\displaystyle \sigma _{i}} だけをプレーする．プレーヤー i が合理的にふるまうという仮定は，他のプレーヤー j による戦略の選択が合理的かどうかについては何も言っていない (最後に，合理的でない相手プレーヤーは，どんなプレーもしうる)． 最適戦略 プレーヤー i の戦略 σ i ∈ Σ i {\displaystyle \sigma _{i}\in \Sigma _{i}} が σ − i {\displaystyle \sigma _{-i}} に対する最適戦略であるとは，任意の σ i ′ ∈ Σ i {\displaystyle \sigma _{i}'\in \Sigma _{i}} に対して u i ( σ i , σ − i ) ≥ u i ( σ i ′ , σ − i ) {\displaystyle u_{i}(\sigma _{i},\sigma _{-i})\geq u_{i}(\sigma _{i}',\sigma _{-i})} が成りたつことをいう． 合理性に関する共有知識 (common knowledge of rationality, gemeinsame Wissen der Rationalität) として言われるのは以下のことである： すべてのプレーヤは合理的であるとみなされる； 全員が合理的に行動する，ということを全員が知っている，ということを全員が知っている……，というように全員の合理性は共有知識である． したがって， σ − i {\displaystyle \sigma _{-i}} もまた合理的でなければならない． 合理性が共有知識になっているか否かで，プレーヤーの戦略の選択は異なりうることに注意せよ． 次の例は Bernheim (1984) の論文からとったものである． 合理性が共有知識であるとき この場合，プレーヤーは戦略 b4 を決して選ばない．なぜならばそれはプレーヤー 1 のどの戦略に対しても最適反応にならないからである．すると今度は，プレーヤー 1 にとって，a4 をプレーすることは得にならない．というのもこれは b4 に対してのみ 1 に得な戦略だからである．それゆえ b4 と a4 は合理化できない．残った戦略を見ると，これらは合理化可能であることがわかる：戦略 a1, b3, a3, b1 は，この順で最適反応のサイクルをなしており，a2 と b2 は互いに最適反応になっている． 合理性が共有知識でないとき そのときプレーヤー 1 は，プレーヤー 2 は b4 をプレーするかもしれないということを考えに入れねばならず，この場合 a4 は最適反応になりしたがって合理的になる． 合理化可能性は，決して最適反応にならない戦略を逐次消去していく再帰法によって定義される．プレーが合理的であるとすると，この再帰段階は，非空な戦略の集合であってそのなかの少なくとも 1 つの他の戦略に対して最適反応になっているようなもので終わるだろう． 正規形ゲームを所与とする．数学的には，合理化可能性は次のように再帰的に定義される． Σ ~ i 0 ≡ Σ i {\displaystyle {\widetilde {\Sigma }}_{i}^{0}\equiv \Sigma _{i}} とする．各 i と各 n ≥ 1 に対して， Σ ~ i n = { σ i ∈ Σ ~ i n − 1 ∣ ∃ σ − i ∈ ∏ j ≠ i conv ⁡ ( Σ ~ j n − 1 ) s.t. u i ( σ i , σ − i ) ≥ u i ( σ i ′ , σ − i ) for all σ i ′ ∈ Σ ~ i n − 1 } {\displaystyle {\widetilde {\Sigma }}_{i}^{n}=\left\{\sigma _{i}\in {\widetilde {\Sigma }}_{i}^{n-1}\mid \exists \sigma _{-i}\in \prod _{j\neq i}\operatorname {conv} ({\widetilde {\Sigma }}_{j}^{n-1})\;{\mbox{s.t.}}\;u_{i}(\sigma _{i},\sigma _{-i})\geq u_{i}(\sigma _{i}',\sigma _{-i})\;{\mbox{for all}}\;\sigma _{i}'\in {\widetilde {\Sigma }}_{i}^{n-1}\right\}} と定める． プレーヤー i の合理化可能戦略とは， R i = ⋂ n = 0 ∞ Σ ~ i n {\displaystyle R_{i}=\bigcap _{n=0}^{\infty }{\widetilde {\Sigma }}_{i}^{n}} のことである． 言葉で言うと， Σ ~ − i n − 1 {\displaystyle {\widetilde {\Sigma }}_{-i}^{n-1}} は，第 (n - 1) 段階で生き残ったすべての相手プレーヤーの戦略の集合であり， Σ ~ i n {\displaystyle {\widetilde {\Sigma }}_{i}^{n}} は， Σ ~ − i n − 1 {\displaystyle {\widetilde {\Sigma }}_{-i}^{n-1}} の特定の戦略に対する最適反応をなすような，生き残った戦略の集合である．決して最適反応にならない戦略の逐次消去を生き残った戦略を，プレーヤーの合理化可能戦略という． 合理化可能性の定義では， Σ ~ j n − 1 {\displaystyle {\widetilde {\Sigma }}_{j}^{n-1}} の凸包が用いられていることに注意せよ．この理由は，プレーヤー j がどんな戦略 σ j ∈ Σ ~ j n − 1 {\displaystyle \sigma _{j}\in {\widetilde {\Sigma }}_{j}^{n-1}} をプレーするか，プレーヤー i には不確かであるということである． σ j ′ , σ j ″ ∈ Σ ~ j n − 1 {\displaystyle \sigma _{j}',\sigma _{j}''\in {\widetilde {\Sigma }}_{j}^{n-1}} であるにもかかわらずその混合 ( 1 2 σ j ′ , 1 2 σ j ″ ) {\displaystyle \left({1 \over 2}\sigma _{j}',{1 \over 2}\sigma _{j}''\right)} が Σ ~ j n − 1 {\displaystyle {\widetilde {\Sigma }}_{j}^{n-1}} に含まれず排除されるということがあってはならない． Bernheim (1984) と Pearce (1984) は，各プレーヤー i について合理化可能戦略の集合 Ri は非空であり，少なくとも 1 つの純粋戦略を含むことを示した． 右のような純粋戦略のゲームを考える． 初期状態 プレーヤー 1 について Σ ~ 1 0 = Σ 1 = { O , M , U } {\displaystyle {\widetilde {\Sigma }}_{1}^{0}=\Sigma _{1}=\{O,M,U\}} , プレーヤー 2 について Σ ~ 2 0 = Σ 2 = { L , R } {\displaystyle {\widetilde {\Sigma }}_{2}^{0}=\Sigma _{2}=\{L,R\}} とする． 第 1 段階 戦略 O は L に，U は R に，L は M に，R は O と U に対して最適反応になっている．まとめると，プレーヤー 1 の戦略 O および U, プレーヤー 2 の戦略 L および R は，少なくとも 1 つの相手プレーヤーの戦略に対して最適反応になっているので，生き残る．言いかえると，戦略 M は，決して最適反応になれないので，この段階で消去される．数学的に書くと，プレーヤー 1 について Σ ~ 1 1 = { O , U } {\displaystyle {\widetilde {\Sigma }}_{1}^{1}=\{O,U\}} , プレーヤー 2 について Σ ~ 2 1 = { L , R } {\displaystyle {\widetilde {\Sigma }}_{2}^{1}=\{L,R\}} である． 第 2 段階 L は，M に対してだけ最適反応だったのだが，M は第 1 段階で生き残れなかった．この段階で戦略 L は，前の段階で残っていた戦略のどれに対しても決して最適反応になれないため，消去される．すなわち，プレーヤー 1 について Σ ~ 1 2 = { O , U } {\displaystyle {\widetilde {\Sigma }}_{1}^{2}=\{O,U\}} , プレーヤー 2 について Σ ~ 2 2 = { R } {\displaystyle {\widetilde {\Sigma }}_{2}^{2}=\{R\}} となる． 第 3 段階 O は，L に対してだけ最適反応だったのだが，L は第 2 段階で生き残れなかった．この段階で戦略 O は，前の段階で残っていた戦略のどれに対しても決して最適反応になれないため，消去される．すなわち，プレーヤー 1 について Σ ~ 1 3 = { U } {\displaystyle {\widetilde {\Sigma }}_{1}^{3}=\{U\}} , プレーヤー 2 について Σ ~ 2 3 = { R } {\displaystyle {\widetilde {\Sigma }}_{2}^{3}=\{R\}} となる． U と R が相互に最適反応になっているので，再帰段階はここで終わる． 定理 2 人ゲームでは合理化可能性と繰りかえし強支配とは等価である． 繰りかえし強支配 (iterierte Eliminierung von streng dominierten Strategien: IESDS; 強く支配される戦略の逐次的消去) の出発点は，合理的なプレーヤーならば決して支配される戦略はプレーしないということである．一方で，合理化可能性の出発点は，合理的なプレーヤーがプレーしうる戦略とはどのようなものだろうかという問いである． 強く支配される戦略は合理化可能ではない．すなわち，相手プレーヤーがどんな戦略をとってくると考えたとしても，それは最適反応には決してなれない： Σ − i {\displaystyle \Sigma _{-i}} に対して， σ i ′ {\displaystyle \sigma _{i}'} が σ i {\displaystyle \sigma _{i}} に強く支配されているとすると，任意の σ − i ∈ Σ − i {\displaystyle \sigma _{-i}\in \Sigma _{-i}} に対して， σ i {\displaystyle \sigma _{i}} は σ i ′ {\displaystyle \sigma _{i}'} よりも厳密によい反応になる．まとめると，繰りかえし強支配のプロセスを生き残ることは，戦略の合理化可能性の必要条件である． Bernheim (1984) と Pearce (1984) は，2 人プレーヤーのゲームでは，繰りかえし強支配の結果生き残る戦略はすべて合理化可能戦略であることを示した．これは戦略の合理化可能性の十分条件である． Bernheim (1984) による例を考えよう．十分条件は次のように確かめられる：合理化可能戦略 a1, a2, a3, b1, b2, b3 は，支配されないので，繰りかえし強支配を生き残る．戦略 b 4 {\displaystyle b_{4}} は，混合戦略 ( 1 3 a 1 , 1 3 a 2 , 1 3 a 3 ) {\displaystyle \left({1 \over 3}a_{1},{1 \over 3}a_{2},{1 \over 3}a_{3}\right)} に強く支配されている．b4 が消去されたあとでは，a4 は a2 に強く支配される． 必要条件も確かめられる：繰りかえし強支配で生き残る戦略は a1, a2, a3, b1, b2, b3 であり，これらは実際に合理化可能戦略である． この例では，2 人ゲームにおいて繰りかえし強支配と合理化可能性とが同値であることが確認できる． すでに見たように，2 人ゲームにおいては繰りかえし強支配と合理化可能性とには同値性がある．ところが多人数ゲームでは，「強く支配されている」ということと「決して最適反応にならない」ということとの同値性はかならずしもあてはまらない．すなわち，多人数ゲームでは，繰りかえし強支配と合理化可能性とはかならずしも同値ではない． 相手プレーヤーの行動に関する予想 (信念) の基礎にあるのは次のことである：もしプレーヤーが，他のプレーヤーは独立に行動してくる (独立な混合) ものと予想するならば，同値性は成りたたない．ここで，「独立な混合」ということは予想の定義 σ − i ∈ ∏ j ≠ i Σ j {\displaystyle \textstyle \sigma _{-i}\in \prod _{j\neq i}\Sigma _{j}} ですでに仮定されていることに注意せよ． 戦略の相関についての予想が可能であるようなゲームにおいてのみ，この同値性が成りたつ．この場合，予想の定義は次のように修正されねばならない：S-i 上の可能な確率分布の全体を Δ S − i {\displaystyle \Delta S_{-i}} とし， σ − i ∈ Δ S − i {\displaystyle \sigma _{-i}\in \Delta S_{-i}} . 次の例は，MIT での Asu Ozdalar によるゲーム理論の講義ノートのものである．相関戦略が許されない 3 人ゲームでは繰りかえし強支配は同等でないことが示される．この例ではすべてのプレーヤーの利得は等しいとする．プレーヤー 1 は A か B, プレーヤー 2 は C か D, プレーヤー 3 は Mi (i = 1, 2, 3, 4) から選ぶ． プレーヤー 1 と 2 の戦略に対して，M2 は決して最適反応になりえないことが，次のようにしてわかる． プレーヤー 1 が A を選ぶ確率を p, プレーヤー 2 が C を選ぶ確率を q とおく．p, q は独立と仮定する．M2 をプレーしたときのプレーヤー 3 の利得 u3 は，u3 (M2, p, q) = 4pq + 4 (1 - p)(1 - q) = 8pq + 4 - 4p - 4q. ある p, q に対して M2 が最適反応であるとすると，次の 3 つの不等式がみたされねばならない： 8pq + 4 - 4p - 4q ≥ u3 (M1, p, q) = 8pq 8pq + 4 - 4p - 4q ≥ u3 (M3, p, q) = 8 + 8pq - 8p - 8q 8pq + 4 - 4p - 4q ≥ u3 (M4, p, q) = 3 最初の 2 つの不等式から，p + q ≤ 1, p + q ≥ 1 となる．したがって，p + q = 1 である．3 番めの不等式で p + q = 1 とすると，pq ≥ 3/8 を得る．q を p で消去すると，p2 - p + 3/8 ≤ 0. 変形すると (p - 1/2)2 + (8/3 - 1/4) ≤ 0 となり，この不等式はどのように p を選んでもみたされないから，M2 は決して最適反応にならない． 一方で，M2 が支配される戦略でないことも明らかである． ナッシュ均衡は合理化可能均衡である．この均衡では最適戦略だけがプレーされている．合理化可能でない戦略は最適戦略にはならない． 合理化可能な戦略プロファイルはかならずしもナッシュ均衡ではない．ナッシュ均衡では，プレーヤーの信念は事後的には実際にみたされているという意味の整合性条件を要求する．言いかえると，ナッシュ均衡では，プレーヤー i の戦略 si はそのプレーヤーのプレーヤー j に関する信念を所与として最適であり，またプレーヤー j にとっても，プレーヤー i は戦略 si を選ぶであろうと正しく予想しているならば，プレーヤー i のもつ信念にあるとおり行動することが実際に最適になっている．したがって，ナッシュ均衡は整合的な信念の組みあわせにもとづいている．合理化可能戦略ではあるがナッシュ均衡ではないようなゲームの帰結では，少なくとも 1 人のプレーヤーが誤った信念をもっている．合理化可能性だけではナッシュ均衡の十分条件にならない．なぜならば，合理化可能性はどんなプレーヤーの確率的予想をも共有知識として要求せず，したがって信念の整合性もみたされないからである． 右の男女の争いゲームを考えよう． このゲームには 2 つの純粋戦略ナッシュ均衡がある．F は F に対し，B は B に対し最適反応なので，戦略 F と B は合理化可能である．合理化可能性による予測では，ゲームは (F, B) で終了し，両プレーヤーの利得は 0 になるというものを許してしまう．(F, B) は，プレーヤー 1 がプレーヤー 2 は F をプレーすると考え，プレーヤー 2 がプレーヤー 1 は F をプレーすると考えるために起こりうる．どちらの予想も，相手プレーヤーについての合理的な予想を通して正当化されうるので，意味をなす．そして両プレーヤーは互いに行き違いになってしまう．このことは，プレーヤーの確率的予想が共有知識でないためである． Brandenburger and Dekel (1987) は，2 人ゲームでは任意の合理化可能戦略プロファイルは主観的相関均衡に等しいことを証明した．主観的相関均衡 (subjektives korreliertes Gleichgewicht) とは，プレーヤーの事前の確率的予想が一致している必要がないような相関均衡 (korreliertes Gleichgewicht) である．多人数ゲームについても似た同値性が成りたつ．プレーヤーたちが，他のプレーヤーたちはすべて独立に戦略を選ばねばならないと考えるか，他のプレーヤーたちの戦略は互いに相関していてもよいと考えるかは，重要な違いである． Aumann (1987) は，プレーヤーたちが異なる事前の確率的予想をもつことを許したゲーム理論的分析によって，概念的な不整合性を示した．このため彼は，そこから出発して，プレーヤーたちが自然の手番に関してだけでなく全プレーヤーの行動についても共通事前分布をもつとする仮定を擁護した．この強い共通事前分布の仮定を採用すると，ナッシュ均衡が相関戦略になるような合理化可能戦略だけが残る (相関均衡を参照のこと)． もっともらしい解を峻別するための手法としての合理化可能性は，それによってはしばしばわずかの戦略しか排除できないので，限定的である．合理化可能性が与えるのは非常に弱い予測であって，合理化可能な帰結どうしではほとんど区別ができない．男女の争いゲームでは，合理化可能戦略の選ぶ結果としてすべての戦略の組みあわせが認められてしまう．ナッシュ均衡となるのはそのうち 2 つだけである．信念の合理性に関する要求は，ここでは戦略の選択に対してなんの制約としても働いていない． ゲーム理論 解概念 支配戦略 ナッシュ均衡 共有知識 相関均衡 Holler/Illing: Einführung in die Spieltheorie, 6. Auflage, Springer, Berlin 2006 Gernot Sieg: Spieltheorie, 3. Auflage, Oldenbourg, München 2010 Harald Wiese: Entscheidungs- und Spieltheorie, Springer, Berlin 2002 Robert Gibbons: A Primer in Game Theory, First Edition, Financial Times, Harlow 1992 Fudenberg, Drew and Jean Tirole: Game Theory, MIT Press, Cambridge, 1993 Bernheim, D. (1984) Rationalizable Strategic Behavior. Econometrica 52: 1007–1028. Pearce, D. (1984) Rationalizable Strategic Behavior and the Problem of Perfection. Econometrica 52: 1029–1050 Jim Ratliff による，アリゾナ大学でのゲーム理論大学院講義 Prof. Dr. Ana B. Ania による，LMU ミュンヘンでのゲーム理論講義ノート Asu Ozdaglar による，MIT でのゲーム理論講義ノート