部分ゲーム完全均衡(ざっくりとした説明)

部分ゲーム完全均衡について、ざっくりと説明します。

部分ゲーム完全均衡(Subgame Perfect Equilibrium, SPE)とは「ある点から後がゲーム(部分ゲーム)とみなせるときには、プレイヤーはそのゲームのナッシュ均衡を選んでいる」と考えるゲームの解です。

次のようなゲームを考えてみましょう。

このゲームは最初にプレイヤー1がYNかを選択。Nを選べば右上の戦略形ゲーム(同時ゲーム)に突入し、Nを選べばゲームは終了してプレイヤー1と2の利得が共に2となるゲームです。

このゲームの解はどうなると予想されるでしょう?プレイヤー1は最初の点で、Yを選んだときに、その結果がどうなるかを予想しなければなりません。右上の戦略形ゲームでは、ナッシュ均衡は(B,B)なので、プレイヤー1の利得は1になると予想されます。

このことからプレイヤー1は最初の点でYを選べば利得は1、Nを選べば利得は2になるのでNを選ぶと考えられます。部分ゲーム完全均衡は「プレイヤー1は最初の点でYを選び、次の戦略形ゲームでプレイヤー1と2は共にBを選ぶ」となります。

部分ゲーム完全均衡を正確に学ぶためには、(1)展開形ゲームはどのように書けて、それを戦略形ゲームに変換するにはどうするのか、(2)展開形ゲームにおいて、ある点から後をゲーム(部分ゲーム)とみなせるのはどういうときか、を学ぶ必要があります。それはまた今度にします。今はこちらの動画を参考にしてください。

部分ゲーム完全均衡はナッシュ均衡の1つ

部分ゲーム完全均衡はナッシュ均衡の1つ(精緻化されたもの)です。例を使って、(ボンヤリとですが)説明してみましょう。

次のゲームを考えます。

  • 最初にプレイヤー1がUDを選びます。Uを選べばゲームは終わり、プレイヤー1と2の利得は1と3になります。
  • プレイヤー1がDを選ぶと、プレイヤー2がLRを選びます。Lを選べばゲームプレイヤー1と2の利得は0と1、Rを選べばプレイヤー1と2の利得は共に2となります。

このゲームは、プレイヤー1がUDを選び、プレイヤー2がLRを選ぶ戦略形ゲーム(同時のゲーム)と考えることもできます。

ここで「交互にプレイする展開形ゲームを、同時にプレイする戦略形ゲームに変換できるのか?」という疑問があるかと思います。確かにそこが最大のポイントですね。確かにプレイヤー2は、プレイヤー1がDを選んだのを知ってから、LかRを選ぶわけです。しかし、プレイヤー2はゲームが始まる前に「もしプレイヤー1がDを選んだらどうするか」を決めておくことはできるはずです。またプレイヤー1は、「もしDを選んだらプレイヤー2はどうするか」を推測しなければ自分の選択を決めることができません。プレイヤー1の頭の中では、プレイヤー2がどうするかは、自分が選択をする前(ゲームが始まる前)に決まっていなければなりません。このように展開形ゲームでは「すべてのプレイが行われる前に、各プレイヤーはどの点で何が選ばれるかを決定しておく」として、戦略形ゲームとして考えることができるわけです。

この戦略形ゲームのナッシュ均衡は(U,L)(D,R)の2つです。

一方、このゲームの部分ゲーム完全均衡はどうなるでしょう。プレイヤー2が行動する点は部分ゲームと考えることができます。プレイヤー2はLを選べば利得1、Rを選べば利得2ですからRを選びます。このプレイヤー2の行動を推測すると、プレイヤー1はDを選びます。

部分ゲーム完全均衡は「プレイヤー1がDを選び、プレイヤー2がRを選ぶ」です。この考え方は完全情報展開形ゲームバックワードインダクションと同じですね。このように完全情報展開形ゲームでは部分ゲーム完全均衡はバックワードダクションの解になるのです。

この部分ゲーム完全均衡は、戦略形ゲームに変換したときのナッシュ均衡の1つ(D,R)になります。このように部分ゲーム完全均衡はナッシュ均衡の1つになるのです。

均衡の精緻化

ナッシュ均衡がすべて、部分ゲーム完全均衡になるわけではありません。ここで、部分ゲーム完全均衡ではない(U,L)というナッシュ均衡が、どういうものかを考えてみましょう。図では以下のようになりますね。

このナッシュ均衡では、各プレイヤーが(U,L)が起こると予想しています。プレイヤー2は、プレイヤー1がUを選ぶと予想すれば、Lを選んでもRを選んでも利得は同じなので、Lを選んでも悪くはありません。そして、プレイヤー1は、プレイヤー2がLを選ぶと予想すれば、Uを選ぶことが最適です。したがって、この戦略の組は「すべてのプレイヤーにとって、相手がその戦略を選ぶならば、自分にとって最適な戦略を選んでいる」ようなナッシュ均衡になるのです。

確かにプレイヤー2は「プレイヤー1がUを選んだと予想したときは、Lを選んでもRを選んでも利得は同じ」です。しかし、このゲームは同時のゲームではありません。予想ではなく、実際にプレイヤー1がDを選んだ場合には、プレイヤー2は、もはやLを選ばずRを選ぶでしょう。

このように展開形ゲームを戦略形ゲームに変換すると、「プレイヤーが選択した行動の情報」を考慮せずに、プレイヤーの推測を考えることになってしまうように見えます(そう見えますが、本当にそうかどうかは、難しいところです)。

そのため、変換した戦略形ゲームのナッシュ均衡をそのまま解として考えると不完全で、展開形ゲームの構造を考慮して、ナッシュ均衡の中から適切でない解を除く必要があります。これを均衡の精緻化(equilibrium refinement)と呼びます。部分ゲーム完全均衡はナッシュ均衡の精緻化による解の1つです。

まとめ

  • 部分ゲーム完全均衡は「ある点から後がゲーム(部分ゲーム)とみなせるときには、プレイヤーはそのゲームのナッシュ均衡を選んでいる」と考えるゲームの解
  • 部分ゲーム完全均衡はナッシュ均衡の1つ
  • ナッシュ均衡から、適切でない解を取り除き、解の候補を絞り込むことを均衡の精緻化と言う
  • 完全情報ゲームにおいては、部分ゲーム完全均衡はバックワードインダクションにいよる解になります。

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

バックワードインダクションで展開形ゲームを解く

完全情報展開形ゲームとその解き方であるバックワードインダクション(backward induction)について「展開形ゲームとは?ゲームの木とは?」で、ざっくりと話しました。ここではバックワードインダクションによるゲームの解き方を、もう少し詳しく説明します。

バックワードインダクションでゲームを解く

バックワードインダクションは完全情報展開形ゲームの解き方です。各プレイヤーは自分よりあとに行動するプレイヤーの行動を先読みし、自分の利得を最大にするように行動を選ぶのでした。

これを言い換えるとゲームは「時間的に後から行動するプレイヤーの行動から順番に解いてゆく」ということになります(有限時間の場合)。後から帰納的に(順番に)解くという意味でバックワードインダクションと呼ばれるのです。

バックワードインダクション(backward induction)は翻訳すると「後向き帰納法」「後向き遡及法」などと翻訳されるのですが、しっくりこないんでカタカナ語で書いたりすることが多いです。

具体的には、次のようにゲームを解いていきます。

1。最後のプレイヤー、つまり「そのプレイヤーが何を選んでもゲームが終わる」ようなプレイヤーの行動を求めます。そのプレイヤーは、自分が行動を選ぶと自分の利得が決まるので、そのプレイヤーが自分の利得を最大にする行動を決定することができます。
2。既に行動を求めたプレイヤーの直前に行動するプレイヤーの中から、<そのプレイヤー以降に行動するプレイヤーの行動がすべて決まっているプレイヤー>の行動を求めます。そのプレイヤーは、自分が行動を選ぶと、それ以降のプレイヤーの行動が決まっている(か、またはゲームが終わる)ために利得が決まるので、利得を最大にする行動を決定することができます。
3。2を繰り返して行き、一番最初のプレイヤーの行動が求められたら終わり…です。

例題

いくつかの例題を見てみましょう。説明をするためには、ゲームの木の点に名前がついていると便利ですので、そうしておきます。(正確には意思決定点にラベルを付けておきます。ゲームの木を少し詳しく説明!も参照してください。)

(例1)まず最初は「展開形ゲームとは?ゲームの木とは?」で説明した<コンビニ立地ゲーム>の例(図1)を、バックワードインダクションの手順の観点から、もう一度解いてみます。

図1:コンビニ立地ゲームの例

1。最後に行動するプレイヤーは、\(x2\),\(x3\)で行動するファミモなので、そこでの行動を決めます。 \(x_2\)では、ファミモはAを選べば利得が400、Bを選べば利得が300となのでAを選びます。 \(x_3\)では、ファミモはAを選べば利得が600、Bを選べば利得が200なのでAを選びます。こうして最後に行動するプレイヤーの行動が決まります。

2。次に、既に行動を求めたプレイヤーの直前に行動するプレイヤーは\(x_1\)で行動するセレブだけなので、そこでの行動を決めます。\(x_1\)では、セレブは、Aを選ぶと(ファミモがAを選ぶので)利得が200、Bを選ぶと(ファミモがAを選ぶので)利得が300となるのでBを選ぶ、というように行動が決定できます。これで最初のプレイヤーまで遡って行動が決まったので、おしまいです(図2)。

図2:例1のバックワードインダクション

(例2)もう少し複雑な例を考えてみましょう(図3)。今度は3人のゲームです。

図3はプレイヤー1,2,3の3人からなる、以下のようなゲームです。

図3:3人ゲーム、ゲームをプレイする順番は不規則
  • はじめにプレイヤー1が\(x_1\)で\(A\)か\(B\)を選びます。
  • もしプレイヤー1が\(A\)を選んだときは、プレイヤー3が\(x_2\)で\(C\)か\(D\)を選び、ゲームは終わります。
  • プレイヤー1が\(B\)を選んだときは、プレイヤー2が\(x_3\)で\(E\)か\(F\)を選びます。\(E\)を選ぶと、そこでゲームが終わります。
  • プレイヤー2が\(F\)を選ぶと、\(x_4\)でもう一度プレイヤー1の手番となり、プレイヤー1は\(G\)か\(H\)を選び、そこでゲームが終わります。

図3において、各点の上の数字は行動するプレイヤーを表しています。ゲームが終わったときの利得は、常に左からプレイヤー1、2、3の順になっています。

このゲームを、バックワードインダクションの手順に従い解いてみましょう。

1。最後に行動するプレイヤー(そのプレイヤーが何を選んでもゲームが終了するプレイヤー)の行動です。このゲームでは\(x_2\)で行動するプレイヤー3と、\(x_4\)で行動するプレイヤー1なので、そこでの行動を決めます。 \(x_2\)では、プレイヤー3は\(C\)を選べば利得が1、\(D\)を選べば利得が0なので\(D\)を選びます。\(x_4\)ではプレイヤー1は\(G\)を選べば利得が6、\(H\)を選べば利得が1なので\(G\)を選びます。こうして最後に行動するプレイヤーの行動が決まります。

2。次に、<そのプレイヤー以降に行動するプレイヤーの行動がすべて決まっているプレイヤー>は、\(x_2\)で行動するプレイヤー2なので、そこでの行動を決めます。\(x_2\)でプレイヤー2は、\(E\)を選ぶと利得が5、\(F\)を選ぶと(プレイヤー1がGを選ぶので)利得が4、となるので\(E\)を選ぶ、ということになります。(図4)

図4:例2のバックワードインダクション-その1

3。次に、\(x_1\)で行動するプレイヤー1の行動を決めます。\(x_1\)でプレイヤー1は、\(A\)を選ぶと(プレイヤー3が\(C\)を選ぶので) 利得が4、\(B\)を選ぶと(プレイヤー2が\(E\)を選ぶので)利得が3となるので\(E\)を選ぶ、ということになります。

図5:例2のバックワードインダクション

解と結果(均衡経路)を区別する

以上、バックワードインダクションによる完全情報ゲームの解の求め方について解説しました。このときバックワードインダクションで得られるゲームの解と、それによって予測されるゲームの結果は何であるか、について区別しなければなりません。ここで

ゲームの解とは、すべての点で各プレイヤーが何を選ぶかを、すべて明らかにしていること
ゲームの結果とは、ゲームの解によって、最初(初期点)のプレイヤーから順番にどのような行動が選ばれゲームが進行して、どの点でゲームが終わるかを示したもの

です。

例えば最初の例1を見てみましょう(図6)。

図6:ゲームの解と結果を区別する(例1)

このときゲームの解は「 \(x_1\)でセレブがBを選び、\(x_2\)と\(x_3\)でファミモはAを選ぶ」となります。このようにゲームの解はすべての点でプレイヤーが何を選ぶかを定めたものです。

これに対し、\(x_1\)でセレブがBを選べば、次に\(x_3\)でファミモがAを選んでゲームは終わり、実際には\(x_2\) は実現しません。ゲームの解によって、実際に起きる結果は解の一部です。

「すべての点(正しくは意思決定点)で何が選ばれるか」が決まると、「最初のプレイヤー(初期点)から、順番にどのプレイヤーがどの行動を選んでゲームが進行して、最後のプレイヤーの行動が決まって利得が決まるところ(終点)」まで一本の経路(path)ができます。この経路は均衡経路(equilibrium path)と呼ばれます。この均衡経路はゲームの結果であると考えられます。 この例の場合、均衡経路(=ゲームの結果)は「 \(x_1\)でセレブがBを選び、\(x_3\)で、ファミモはAを選ぶ」となります。

「すべての意思決定点で何が選ばれるか」は「戦略の組(strategy profile)」に対応するものです。またこれは1つの経路を実現すると考えても良いし、1つの終点が決まると考えても良いです。なお途中で確率による選択(混合戦略)があると、経路は1つではなく、複数の経路が確率的に決定されると考えられます。

ゲームの解において、均衡経路ではない意思決定点は均衡外経路(off-equilibrium path)と呼ばれます。 例1では\(x_2\)は均衡外経路です。このことよりゲームの解が異なってもゲームの結果が同じになることがあることに注意しましょう。

例2で、ゲームの解とゲームの結果が何であるかを練習してみましょう。


図7:ゲームの解と結果を区別する(例2)

この例2の場合は

  • ゲームの解は、プレイヤー1が\(x_1\)で\(A\)を\(x_4\)で\(G\)を選び、プレイヤー2が\(x_3\)で\(E\)を選び、プレイヤー3が\(x_2\)で\(C\)を選ぶ。
  • ゲームの結果は、プレイヤー1が\(x_1\)で\(A\)を選び、プレイヤー3が\(x_2\)で\(C\)を選ぶ。

となります。いかがでしょうか。

バックワードインダクションはゲーム理論だけではない

<後から解く>バックワードインダクションは、時間経過を伴う最適化問題である動的最適化(マクロ経済学、ファイナンス理論)、ネットワーク最適化問題にも用いられる一般的手法です。この概念を方程式に直すといわゆるベルマン方程式となります。

以下も参考にしてください。

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

展開形ゲームとは?ゲームの木とは?

ゲーム理論のゲームには、戦略形ゲーム(strategic form)と展開形ゲーム(extensive form)という2つの「表現」があります。戦略形ゲームは、プレイヤーは同時に行動を選ぶと考えてゲームを表します。これに対し、展開形ゲームは、先手と後手のあるゲームなど、どんなゲームでも表現できて、プレイヤーは同時に行動しなくても良いのです。

このような展開形ゲームの中でも、プレイヤーが1人ずつ順番に行動を選び(同時に行動することはなく)、各プレイヤーは自分より先に行動したプレイヤーが何を選んだかがすべて分かるゲームを完全情報(perfect information)の展開形ゲームと言います。代表的な例は、チェス、囲碁、将棋です。将棋で「自分より前に指した手が、何か分からん!」ってことはありませんよね?

完全情報ではないゲームは不完全情報(imperfect information)と呼びます、あたりまえですね。不完全情報ゲームの例としては、たとえば...「2人でじゃんけんをするとき、まず1人がグー・チョキ・パーを選んで紙に書いて相手に見えないように封筒に入れ、次にもう1人が改めてグー・チョキ・パーを選ぶ」という面倒なじゃんけんは不完全情報ゲームです.

...って、あれ?戦略形ゲームで勉強したように、これは同時に行動することと同じでした。「プレイヤーが同時に行動する戦略形ゲーム」は「不完全情報の展開形ゲーム」の典型的な例です。これはまた別の機会に。

ここでは完全情報の展開形ゲームとその解き方について学んで行きます。乱暴に言うと

  • 戦略形ゲームは利得行列で表しナッシュ均衡で解く
  • 完全情報展開形ゲームはゲームの木で表し、バックワードインダクションで解く

ということになります。乱暴すぎてかなり間違ってますが、細かいことは気にせず、ざっくり説明します。正確な定義や説明はゲーム理論のテキストなど読んでください。

完全情報展開形ゲームの例

以下の例を考えましょう。戦略形ゲームの支配戦略やナッシュ均衡の説明で使った例と同じです。今度はプレイヤーは同時に行動を選ぶのではなく、セレブ、ファミモの順に選びます。

2つのコンビニ、セレブ(セレブイレブン)とファミモ(ファミリーモール)が、A駅とB駅のどちらか一方に出店しようと考えている。コンビニを1日に利用する客はA駅が600人、B駅が300人である。セレブとファミモが違う駅を選べば利用客を独占できる。しかし同じ駅に出店すると、ファミモが人気で、ファミモはセレブの2倍の客数を獲得できる。すなわち両方がA駅に出店すると、セレブ200人、ファミモ400人。B駅に出店すると、セレブ250人、ファミモ500人である。ここで客数を利得と考える。

ここでは、まずセレブが先にどちらの駅を選ぶかを決定し、ファミモはそれを知ってから自分がどちらの駅に出店するかを決める。セレブとファミモはどちらの駅に出店するだろうか?

戦略形ゲームのように同時に行動するのではなく、プレイヤーが順番に行動をするゲームが展開形ゲームです。展開形ゲームは次のようなゲームの木で表します。

ゲームの木

ゲームの木の正確な定義は後でやろうと思いますが、ざっくりと理解したい人には、ゲームの木の説明は不要でしょう?まず最初にセレブがAかBかを選び、次にそれを知ってからファミモがAかBかを選ぶと、結果が決まるのでセレブとファミモの利得がそこに書いてある、とそんな感じです。

ゲームを解く

ではさっそく、このゲームを解いてみましょう。皆さんがセレブだったらAとBのどちらを選ぶでしょうか?セレブがAを選ぶと、うまく行けば(ファミモがBを選べば)600の利得を得られますし、Bを選ぶとヘタをすれば(ファミモがBを選べば)100の利得になってしまいますね。だから、セレブはAを選ぶことが答のように思えるかも知れません。

しかし、ゲーム理論の答ではセレブはBを選びます。

なぜでしょうか?このゲームでは、セレブだけではなく、相手プレイヤーのファミモも利得を大きくしたいと考えています。セレブは「うまく行けば」「ヘタをすると」と、自分勝手に考えるのではなく、ファミモの行動を考えて、自分の行動を選択する必要があります。このためにはセレブの次に行動するファミモの行動を先読みする必要があるわけです。

ファミモの行動を先読みしてゲームを解いてみましょう。

  • セレブがAを選ぶと、ファミモはAを選べば利得が400、Bを選べば利得が300となるなのでAを選ぶ
  • セレブがBを選ぶと、ファミモはAを選べば利得が600、Bを選べば利得が200なのでAを選ぶ

これを先読みするとセレブは、Aを選ぶと(ファミモがAを選ぶので)利得が200、Bを選ぶと(ファミモがAを選ぶので)利得が300となるのでBを選ぶ、ということになります(下図)。

ゲームは先読みで解く

結果は「セレブがBを選び、ファミモがAを選ぶ」となります。これが(完全情報)展開形ゲームの解き方です。この先読みによるゲームの解き方はバックワードインダクションと呼ばれます。

以上、とりあえず完全情報展開形ゲームについての簡単な説明と解き方でした。乱暴に言うと

  • 戦略形ゲームは利得行列で表しナッシュ均衡で解く
  • 完全情報展開形ゲームはゲームの木で表し、バックワードインダクションで解く

ということでしたね。乱暴すぎて、かなり間違ってますが、最初は細かいことは気にせず、そんな感じで覚えておけばよいでしょう。正確な定義や説明はゲーム理論のテキストなど読んでくださいね。なお。

  • バックワードインダクションによってゲームを解く方法は、「バックワードインダクションで展開形ゲームを解く」で、もう少し詳しく説明することにします。
  • ゲームの木については「ゲームの木について、ちょい詳しく」でお話します。
  • 一般の不完全情報ゲームとはどんなもので、どのように解くかは、またの機会に。お急ぎの方は「ゼミナールゲーム理論入門」で!

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)