（自分用）第２章　逐次消去均衡

１.逐次消去均衡

　第1章で支配戦略の説明をしたが、この考え方を応用すれば、支配戦略が存在しないゲームにおいても各プレイヤーはより良い選択が可能である。

　簡単に説明すると、ある戦略が他の戦略に支配されているとき、その戦略を削除する（戦略の逐次消去）。そうすることで戦略形ゲームを少しづつ縮小していき、これを繰り返して最終的に残された戦略の組が逐次消去均衡である。

２.戦略の逐次消去とそのプロセス

　ここからは以下の例を用いて説明する。

$$
\begin{array}{|c|c|c|c|c|} \hline
1/2 & E & F &G&H\\ \hline
A & (10,20) & (1,10)& (1,20)&(1,10)\\ \hline
B & (20,1) & (2,20) &(2,10)&(2,10)\\ \hline
C & (1,1) & (3,2) &(3,20)&(3,10)\\ \hline
D & (0,1) & (0,2) &(4,3)&(4,4)\\ \hline
\end{array}
$$

　まず、各プレイヤーの戦略のうち、支配関係にある戦略の組を探す。この例だと、プレイヤー1について戦略Aが戦略Bに強支配されていることが確認できる。このため、まずプレイヤー1は戦略Aを消去する。その結果、利得表は以下のように更新される。

$$
\begin{array}{|c|c|c|c|c|} \hline
1/2 & E & F &G&H\\ \hline
B & (20,1) & (2,20) &(2,10)&(2,10)\\ \hline
C & (1,1) & (3,2) &(3,20)&(3,10)\\ \hline
D & (0,1) & (0,2) &(4,3)&(4,4)\\ \hline
\end{array}
$$

　更新された利得表を見ると、今度はプレイヤー2について戦略Eが戦略Fに強支配されている（戦略Aが消えた結果である）。よってプレイヤー2は戦略Eを消去する。

$$
\begin{array}{|c|c|c|c|} \hline
1/2  & F &G&H\\ \hline
B  & (2,20) &(2,10)&(2,10)\\ \hline
C  & (3,2) &(3,20)&(3,10)\\ \hline
D  & (0,2) &(4,3)&(4,4)\\ \hline
\end{array}
$$

　同様の操作を繰り返すと次は戦略B、その次は戦略F、その次は戦略C、最後に戦略Gが消去され、最後に残った戦略Dと戦略Hの組が逐次消去均衡ということになる。

　上の例では強支配による逐次消去だったが、弱支配による逐次消去も可能である。

$$
\begin{array}{|c|c|c|c|c|} \hline
1/2 & E & F &G&H\\ \hline
A & (10,10) & (10,5)& (10,5)&(5,20)\\ \hline
B & (15,5) & (10,10) &(10,0)&(5,0)\\ \hline
C & (0,5) & (15,5) &(10,10)&(5,0)\\ \hline
D & (20,0) & (0,0) &(15,0)&(0,10)\\ \hline
\end{array}
$$

　弱支配による逐次消去では、消去する順番によって残される戦略が異なる。プレイヤー1から消去を始めると(A,E)と(A,F)の2つの戦略の組が残る一方、プレイヤー2から消去を始めると(A,E)と(B,E)の2つの戦略の組が残り、残る戦略の組が異なる（プロセスは強支配の時と同じなので省略）。
　このとき、両プレイヤーが同時に消去を始めた場合に残る(A,E)が逐次消去均衡になる。

3．戦略の逐次消去と共有知識の仮定

　逐次消去均衡は前述した方法で求めることができるわけだが、この均衡の求め方は「相手は合理的だから支配されている戦略は取らないだろう」という推論のもと成り立っている。そのため逐次消去均衡を求めるためには以下の条件を満たす必要がある。
1.自分は相手が合理的であることを知っている
2.相手も自分が合理的であることを知っている
（いうまでもなく自分も相手も合理的である必要がある）
3.お互いがお互いの利得や戦略を知っている
※これらを共有知識という

４.美人投票ゲームと複占市場ゲーム（複占市場ゲームは省略）

　ここからは逐次消去均衡を用いた美人投票ゲームというゲームについて記述する。ルールは以下の通りだ。

1.プレイヤー（n人）は1~99までの整数から1つを選ぶ
2.全員の選んだ整数の平均の2/3（以下、目標数とよぶ）に最も近い人が勝利

　もし全員が99を選んだとすると、目標数は66になる。したがって、目標数が67以上になることはなく、67以上の整数を選んでも６６を選んだ人に勝てない。したがって、「67以上の整数を選ぶ」という戦略は「66を選ぶ」という戦略に強支配される。したがって「67以上の整数を選ぶ」という戦略を消去する。
　ここで、全員が66を選んだとすると目標数は44になる。したがって、目標数が45以上になることはなく、45以上の整数を選んでも44を選んだ人に勝てない。したがって、「45以上の整数を選ぶ」という戦略は「44を選ぶ」という戦略に強支配される。したがって「45以上の整数を選ぶ」という戦略を消去する。
　これを延々と繰り返すと、残る戦略は「1を選ぶ」のみになる。1だけは他の戦略に支配されないため、消去されないのである。したがって「すべてのプレイヤーが1を選ぶ」のが美人投票ゲームの逐次消去均衡となるわけだ。
　注意しておきたいのは、美人投票ゲームで1を選ぶのは決して必勝の手ではないことである。
　たとえば5人でこのゲーム行い、1人だけ1、その他は99を選ぶと目標数は約53になり、100を選んだ4人の勝利になる。したがって、実際に美人投票ゲームを行うときは相手が合理的か、あるいはどこまで合理的かを考える必要がある。