みなさん、こんにちは。
２月１０日の研究会は
・入門編 無限回繰り返しゲーム （籠谷会員）
・輪読続き ３章３節後半 （大浦会員）
という内容でした。
それぞれの内容は次の通り。
【無限回繰り返しゲーム】
前回は同じゲームを２回繰り返す場合について考がえてみた。その結
果、個々のゲームではNash均衡とはならないような状態が、２回繰り返
しゲームのサブゲーム完全な結果の中にあらわれる場合があることが明
らかになった。今回は、ステージゲームの繰り返しの回数が無限回の場
合について考えてみよう。
無限回繰り返しゲームを考えるにあたって、２つの点で有限回繰り返
しモデルを拡張する必要がある。１つは無限回繰り返しゲームの「利得」
であり、もう１つは「サブゲーム完全な結果」という解概念である。い
ずれも繰り返しが無限回の場合にはそのままでは使用できない。
まず、利得であるが２回繰り返しゲームの時には、単にそれぞれのス
テージゲームの利得の合計を繰り返しゲームの利得とした。しかし、無
限回繰り返しゲームでステージゲームの利得を合計して行くと、多くの
場合合計が無限となり、戦略間の比較をすることができなくなる。そこ
で２つの方法が取られるが、一つは「割り引き因子」の考え方を導入す
る方法で、１期先の利得は現在の利得のδ倍（０＜δ＜１）の価値しか
ないと考える経済学で良く用いられる方法である。
もう一つは、「ゲームの継続確率」を考える方法で、あるステージゲ
ームが行われた時、次のステージゲームが行われる確率がw（０＜w＜１）
と考える方法である。この場合、例えばステージゲームの利得が毎回ａ
の時を考えると、無限回ゲームの利得ｕは
ｕ＝ａ＋aw＋aw^2＋aw^3＋‥‥
＝ａ/(１−w）
となる。このようにすれば、無限回ゲームの利得が有限となり、戦略の
良し悪しを評価できるようになる。
次に無限回ゲームの解について考えよう。有限回の繰り返しゲームで
は最後のステージゲームにおけるNash均衡をまず考え、次に一つ前のゲ
ームのNash均衡を考え・・という手順で繰り返しゲームのサブゲーム完
全な結果を求めた。しかし、無限回ゲームでは「最後のステージゲーム」
というものは存在しないので、この方法で解を求めることはできない。
そこで新たに「サブゲーム完全Nash均衡」という解概念を導入すること
にする。
サブゲーム完全Nash均衡とは、もとのゲームのどのサブゲームについ
てもNash均衡となっているような戦略プロファイル（各プレーヤーの戦
略の組み合わせ）のことである。ここで、サブゲームとは全体ゲームの
途中のある時点（ゲームの木のある節）からあとのゲーム全体のことで、
繰り返しゲームの場合、任意のステージごとにそれまでのゲーム経過の
バリエーションの数だけ存在する。たとえば、前回考えた
｜ Ｃ Ｄ
−−−−−−−−−−−−−
Ｃ ｜ ４,４ ０,５
Ｄ ｜ ５,０ １,１ （表１）
なるＰＤゲームが繰り返される場合を考えると、第２ステージから始ま
るサブゲームが４通り（第１ステージのCC、CD、DC、DDに対応）、第３
ステージからサブゲームが１６通り・・と言った具合に存在する。これ
らすべてのサブゲーム（および全体ゲーム）についてNash均衡となって
いる戦略プロファイルがサブゲーム完全Nash均衡である。
ちなみに、個々のステージゲームはサブゲームでは無い。サブゲーム
とはある状態からあとに行われるゲーム全体を指す概念である。
★ サブゲーム完全均衡は「どのサブゲームにおいても、逸脱の
誘因のない戦略プロファイル」という点がうりの概念ですが、次
に述べるように繰り返しゲームにおける＜戦略＞はスーパー戦略
なので、はじめに手の出し方はすべて決まっています。あるサブ
ゲームに直面してから、手を考えるのではないことになってます
から、そこに逸脱の誘因があってもすでに手は決まっているので
関係ないはずです。つまり「サブゲーム完全均衡」の概念と「ス
ーパー戦略で考える」という方法論の間には若干のずれがありま
す。このあたりのずれの解消が、展開形ゲームの理論の課題の一
つといえます。
次に、繰り返しゲームの＜戦略＞であるが、これは個々のステージゲ
ームで取られる手そのものではなく、手の出し方についての規則（意志
決定アルゴリズムといっても良い）を意味する。繰り返しゲームの場合、
このような意志決定アルゴリズムは「スーパー戦略」と呼ばれる。
たとえば、「相手の手にかかわらずＣを出し続ける」（AllC）、「始
めＣであとは相手が前に出した手を出す」（しっぺ返し＝TFT）、「始め
Ｃで、次は前回CC、DDならＣ、CD、DCならＤを出す」（パブロフ）など
がスーパー戦略の例である。他にも「ランダムに等確率でＣ、Ｄを出す」
、「１３回DDが続けばＣ、それ以外はＤ」などスーパー戦略は無数に考
えることができる。
スーパー戦略からなる戦略プロファイルがNash均衡であるとは、どの
プレーヤーも自分のスーパー戦略を他のどのスーパー戦略に変えても期
待利得が増えないことを意味する（あるいは、異なる意志決定アルゴリ
ズムを採用しても利得が増えない、といっても良い）。
以上のように利得の概念（ゲームの継続確率で割り引く）と、解概念
（サブゲーム完全均衡を考える）を拡張すれば、無限回の繰り返しゲー
ムについて考察することができるようになる。表１のＰＤゲームが無限
回繰り返される場合を考えてみよう。
この無限ゲームは無数のサブゲーム完全均衡を持つが、その中でも実
現しやすいことが期待されるのは「パレート最適」で「公平」な均衡で
ある（一般に、Nash均衡が複数あるときに実現しやすい均衡は「パレー
ト最適」で「公平」な均衡であることが知られている）。このゲームの
場合、実現値としてCCの組み合わせの続くようなサブゲーム完全均衡が
あれば、それは「パレート最適」で「公平」な均衡となる。そのような
均衡は存在するのであろうか。存在するとすれば、その条件はなんであ
ろうか。
ここで、「始めＣで、相手がＣを出し続ける限りＣを出す。相手が一
度でもＤを出せば、それ以降はずっとＤを出す」というスーパー戦略（
トリガー戦略という）を考える。トリガー戦略同士の組み合わせがNash
均衡となれば、CCの組み合わせが実現するはずである。
まず、トリガー戦略同士の場合の利得を求めてみよう。この場合、CC
の組み合わせが続くので、ゲームの継続確率をwとすれば期待利得は
ｕ＝４＋4w＋4w^2＋4w^3＋‥‥
＝４/(１−w）
となる。
ここでトリガーと対戦した時の利得が、この利得を上回るスーパー戦
略が存在しなければ、（トリガー、トリガー）はNash均衡である。実現
値としてＣを出し続けるスーパー戦略を考えると、CCが続くので利得は
トリガーと同じになる（上回ることはできない）。したがって、トリガ
ーを上回るスーパー戦略があるとすれば、それは途中でＤを出すスーパ
ー戦略のはずである。
ｔ回目にＤを出し、それ以後はずっとＤを出すスーパー戦略を考えよ
う。この相手と対戦するとトリガーはｔ回目まではＣ、ｔ＋１回目から
はずっとＤを出すことになる。したがって、対戦者の利得u'は
u'＝４＋4w＋4w^2‥‥
＋4w^(t-2)＋５w^(t-1)＋１w^t＋１w^(t+1)‥‥
となる。これがuを上回るのは
u'ーu＝w^(t-1)−３w^t−３w^(t+1)‥‥
＝w^(t-1)−３w^t/(１−w）＞０
の時なので、これより
w＜1/4
のときは（トリガー、トリガー）はNash均衡とならないことがわかる。
一方、ｔ回目にＤを出した後、ｔ＋１回目以降にもＣを出すことのあ
る戦略の対トリガーの利得は、u'を常に下回る（トリガーはｔ＋１回目
以降すべてＤなので最適応手はＤだから）ので、任意のｔについてu'≦u
が（トリガー、トリガー）がNash均衡となる十分条件である。これより、
w≧1/4
のときに、（トリガー、トリガー）がNash均衡となることが分かる。
次に（トリガー、トリガー）のサブゲーム完全性を吟味してみよう。
ｋ回目（k＞１）のステージゲームから始まるサブゲームを考える。この
サブゲームは、それまでのステージがすべてCCだったサブゲームSkとそ
れ以外のサブゲームSk'に分類できる。
サブゲームSkは実は全体ゲームGと同じ状況（それまでCCなのでSkの最
初の手はCCとなるから）なので、w≧1/4のとき（トリガー、トリガー）
はNash均衡である。一方、サブゲームSk'については、（トリガー、トリ
ガー）は「すべてDD」を指示する。「すべてDD」（AllD）の組み合せは
全体ゲームのNash均衡なので（トリガー、トリガー）はサブゲームSk'
のNash均衡である。
この考察は、任意のｋについて成り立つので、（トリガー、トリガー）
はw≧1/4のとき、すべてのサブゲームについてNash均衡であることがわ
かる。すなわち、w≧1/4のとき（トリガー、トリガー）はサブゲーム完
全均衡であるといえる。
以上のように、ゲームの継続確率が十分大きい時には（トリガー、ト
リガー）はサブゲーム完全均衡となる。これは、他のサブゲーム完全均
衡（たとえば、AllD,AllD）よりもパレート優位でかつ公平な結果をもた
らすので、実現する可能性が高いことが期待できる。つまり、無限繰り
返しＰＤゲームではCCの繰り返しが実現する場合があることが期待でき
る。
【輪読続き ３章３節後半】
３節前半ではマルコフモデルについて考えた。最適反応型学習モデル
では、戦略選択に揺らぎがある場合にはどの状態も互いに到達可能とな
るため、既約なマルコフ連鎖となる。したがって、十分長い時間ののち
には、初期値に依存しない定常分布になることが期待される。
一方、揺らぎのない場合は学習過程は非エルゴード的（初期値依存的）
になりうる。まず、強いNash均衡のあるゲームの場合、それの一つをｘ*
とすると、学習過程の吸収状態はｈ*＝（x*,x*‥‥,x*）の形の記憶列に
限られる。複数の戦略プロファイルを含む記憶列は、次の期には一つず
れた記憶列に遷移するので吸収状態では無いし、強いNash均衡ではない
戦略プロファイルｘが並ぶ記憶列に対する最適応手はｘだけではないの
で、そのような記憶列も吸収状態ではない。一方、記憶列ｈ*に対する最
適応手はｘ*しかないのでｈ*は吸収状態である。
このように、揺らぎのない学習モデルの吸収状態は、強いNash均衡が
繰り返される記憶列であるが、強いNash均衡が複数あるゲームの場合は
吸収状態も複数あることになる。この場合、初期状態によって、どの吸
収状態にいたりやすいかが変わってくる。すなわち、このような学習過
程は非エルゴード的（初期値依存的）である。
タイプライターゲーム
｜ Ｄ Ｑ
−−−−−−−−−−−−−
Ｄ ｜ ５,５ ０,０
Ｑ ｜ ０,０ ４,４ （表２）
を例にとって考えてみよう。以下では、記憶列の長さｍ＝４、サンプル
サイズｓ＝２の場合について考えることにする。
ｍ＝４なので、２人のプレーヤーの記憶列は例えば
ＤＱＱＤ
ＱＤＱＤ
のようになる。左端のDQは４期前の戦略プロファイル、次のQDは３期前
の戦略プロファイル・・を意味する。
この記憶列から２つの戦略が思い浮かべられて、それに対する最適応
手が取られると考える。例えば、ＤＱＱＤという記憶列からは、DQ、DQ、
DD、QQ、QD、QDという戦略の記憶が思い浮かべられる。それぞれに対す
る最適応手はＤ、Ｄ、Ｄ、Ｑ、Ｄ、Ｄなので、どの戦略も思い浮かべら
れる確率が等しいと仮定すると、ＤＱＱＤという記憶列の持ち主が次に
取る戦略は5/6の確率でＤ、1/6の確率でＣということになる。
記憶列ＱＤＱＤに対しても、同様なので、次の期に取られる戦略プロ
ファイルは、確率25/36でDD、確率5/36でQD、確率5/36でDQ、確率1/36
でQQとなる。したがって、
ＤＱＱＤ
ＱＤＱＤ
なる記憶列は次の期には、それぞれ確率25/36、5/36、5/36、1/36で
ＱＱＤＤ ＱＱＤＤ ＱＱＤＱ ＱＱＤＤ
ＤＱＤＱ ＤＱＤＱ ＤＱＤＤ ＤＱＤＤ
に遷移することになる。
可能な記憶列の数は、２の８乗で256通りある。上のような考察を繰り
返すと、これらの記憶列間の推移確率を求めることが理論的には可能で、
さらに推移確率行列の無限乗を考えれば、このマルコフ連鎖の定常分布
を求めることができるはずである。
このような計算を実際に行うことは困難であるが、先ほど考察したよ
うに、このマルコフ連鎖の吸収状態は強いNash均衡のみからなる記憶列
なので、十分に長い時間ののちには（実質、十数期のちには）
ＤＤＤＤ ＱＱＱＱ
ＤＤＤＤ ＱＱＱＱ
のいずれかの記憶列に至って安定するものと考えられる。
★ ところでＤＱＱＤに対して確率5/6でＤとは、DDとQQの利得の
差に比べて少しＤに有利すぎるような気がします。テキストでは
ｓ＝２の場合について述べてありますが、ｓが他の値の場合にＤ
が取られる確率を調べると次のようになります。
記憶列＼ｓ ｜ １ ２ ３ ４
−−−−−−−−−−−−−−−−−−−−−
Ｄ４Ｑ０ ｜ １ １ １ １
Ｄ３Ｑ１ ｜ 3/4 １ １ １
Ｄ２Ｑ２ ｜ 1/2 5/6 1/2 １
Ｄ１Ｑ３ ｜ 1/4 1/2 ０ ０
Ｄ０Ｑ４ ｜ ０ ０ ０ ０
つまり、ｓ＝２の場合に際立ってＤが有利なことが分かります。この
ように、モデルの細部が結果に大きな影響をおよぼすことがあるので、
モデルを考える時には、結果の頑健性についての考察が重要になります。
次回の研究会は、
２月１７日（土） １時から５時
慶応大三田キャンパス大学院棟５階３５６教室
で行います。
内容は
・入門編 無限繰り返しゲーム２ （籠谷会員）
・輪読 第３章４節 ノイズのあるモデル （大浦会員）
・希望者の発表
の予定です。
そのあとの予定。
２月２４日（土）の一橋大は会場が使えないことが
分かりましたので未定です。
では、みなさんまた来週。
庶務担当 大浦
ＨＰ http://qmss.t.u-tokyo.ac.jp/evogame/
メーリングリストの申し込み先
YQN02163@nifty.ne.jp（大浦）