見間違え付き繰り返しゲームにおける協力的均衡とダイナミクス
電気通信大学 *西野上和真 NISHINOUE Kazuma
05000493 電気通信大学 岩崎敦 IWASAKI Atsushi
1. はじめに
本稿では，見間違えのある繰り返しゲームにおける 戦略のダイナミクスを突然変異付きレプリケータダイ ナミクスを用いて分析する．見間違えのある(不完全私 的観測付き)繰り返しゲームは，プレイヤが相手の行動 についてノイズを含むシグナルを観測し，そのシグナル を他のプレイヤは観測できないという特徴をもつ．従来 有効であると言われていたしっぺ返し戦略(Tit-for-tat, TFT)は協力関係を維持できない．一方で，文献[1]は協 力関係に戻りやすい1期相互処罰戦略(1-period mutual punishment, 1MP)という戦略が均衡となることを発見 している．しかし，ある戦略がもっとも高い利得を実現 する均衡だからといって，その戦略がダイナミクスの帰 結で生き残るとは限らない．そこで，本稿では均衡戦略 とダイナミクス[2]の帰結で生き残る戦略の関係性を吟 味し，1期片側処罰戦略(1-period unilateral punishment, 1UP)が協力的なダイナミクスを実現するための触媒の 役割を果たすことを明らかにした．
2. モデル
本章では文献[1]に基づいて，2人対称私的観測付き 無限回繰り返しゲームをモデル化する．ここでプレイ ヤi ∈ {1,2}は成分ゲームを無限期間t = 0,1,2, . . .に 渡って繰り返す．各期においてプレイヤiは有限集合A から行動aiを選択し，その行動の組をa=(a1,a2)∈A2 とする．次に，プレイヤiはaに関する私的なシグナ ルωi∈Ωを観測する．wをシグナルの組(ω1, ω2)∈Ω2 とする．また，プレイヤがaを選択したときwが生起 する同時確率をo(w | a)とし，この同時確率を与える 分布のことをシグナル分布と呼ぶ．成分ゲームは無限 回繰り返し行われるので，プレイヤiの割引利得和は割 引因子δ∈(0,1)により∑∞
t=1δtgi(at)となる．gi(·)は表 1に示す囚人のジレンマの利得表に従う．
次にプレイヤ2の行動に関するプレイヤ1のノイズ を含む観測をプレイヤ1の私的シグナルとし，ω∈ {g,b} (good,bad)とする．正しい観測ではプレイヤ2がCを 選択した際のプレイヤ1の私的シグナルはg，Dを選 択した際の私的シグナルはbとなる．プレイヤ2につ いても同様である．シグナル分布o(w | a)を両プレイ ヤが正しいシグナルを観測する確率はp，片方のプレ
イヤが間違ったシグナルを観測する確率はそれぞれq と仮定する．また，1−p−2qの確率で両方のプレイヤ が間違ったシグナルを観測する．例として,プレイヤが (C,C)を選んだ後のシグナル分布を表2に示す．この 観測構造はほぼ完全観測(Nearly-Perfect,またはAction Misperception)と呼ばれる．本稿ではAMと略記する．
表1:囚人のジレンマ(g>0，l>0，および|g−l|<1) a2=C a2=D
a1=C 1,1 −l,1+g a1=D 1+g,−l 0,0
表2: (C,C)のときのシグナル分布(AM) w2=g w2 =b
w1=g p q
w1=b q 1−p−2q
プレイヤの戦略は，そのプレイヤの過去の行動と受 け取ったシグナルから現在の行動への写像で表現され る．FSAは繰り返しゲームの戦略を簡略に表記する方 法であり，本稿では，状態数2以下の非同相な26個の FSAを戦略として用いる．ここでは，状態RでCを，
状態PでDを選ぶとする．例えば，受け取ったシグナ ルによらずに必ずDを選ぶAllD，bを観測するまでは 状態Rにいるが，一度でもbを観測した後は状態Pに 遷移しDを選び続けるGRIMがある．また，他の重要 な戦略に1MPと1UPがある．1MPは状態Rから開始 し，gを観測している間は遷移せずに同じ状態に留まる が，bを観測したら異なる状態へと遷移する戦略であ る．一方で，1UPは状態Rから開始しbを観測した直 後のみDを選び，それ以外ではCを選ぶ戦略である．
（突然変異付き）レプリケータダイナミクスは，あ る戦略の集団において，“人口”の利得に応じて各戦略 が増減するダイナミクスである[3]．ここで，戦略の集 団→−xの中で戦略jが占める割合をxjとし，→−xに対して 戦略 jが得る利得を fj(→−x)とする．また，∑n
j=1qi j =1 を満たすようなqi jを戦略iの子孫が戦略 jに突然変異 する確率とする．このレプリケータ方程式は
˙ xi=
∑n
j=1
xjfjqji−xiϕ, i=1, ...,n
1-F-9
日本オペレーションズ・リサーチ学会2019年 秋季研究発表会
と な る ．こ こ で ϕ(·) を 全 て の 戦 略 の 利 得 の 平 均
∑
jxjfj(→−x)，fj(·)を∑
mxjajm とする．ただし，ajm は 戦略mを取るプレイヤと対戦する戦略 jをとるプレイ ヤの割引利得和である．
3. 26 戦略のダイナミクスと均衡
図1に，利得パラメータg,lに対して，ダイナミクス の収束時にどの戦略がもっとも多い人口を獲得するかを 示す．g,lを0.05ずつ[0.05,3.00]の範囲で変化させる一 方で，割引因子δ=0.9およびシグナル分布をp=0.95, q =0.01に固定する．戦略の初期人口は一様に分布し ているとし，突然変異が起きる確率を∑
i,jqi j =0.01と する．また，戦略iが異なる戦略 jに突然変異する確率 も一様とし，それぞれ0.01/(26−1)=0.0004となる．
図1:p=0.95,q=0.01の最大人口戦略
図 1において，gとlが十分大きいときはAllDが，
十分小さいときは1MPが生き残る．その中間領域では 基本的にGRIMが生き残りやすいが，g >lの範囲で TFTが生き残ることがある．TFTが生き残る領域の周 辺では，TFT, GRIM, 1UPの3つの戦略が特定の人口 比で共存することが観察された．このときlが小さい ほど，1UPのGRIMへの支配力が大きくなる，つまり GRIMから1UPへ逸脱したときの利得が大きくなるの で，GRIMは生き残るのを妨げられた．その結果，ど んな相手にも大きな損失がないTFTが生き残るように なった．
次に，1MPはg ≤0.75 (図1の点線の左側)のとき，
（プレイヤの利得の和に関して）最適な均衡を構成し，
その1人あたりの利得は9.45となる．しかし，利得6.93 しか実現しない均衡であるGRIMの方が生き残る領域 が大きい．
ここでTFT, GRIM, 1UPの3戦略が共存した場合と 同様，1UPが重要な役割を果たすことを述べる．まず GRIMが生き残る領域からg=0.5,l=1.0を考え，相 手がGRIMをプレイすると仮定する．このときGRIM
をプレイして得られる利得は6.93, 1MPをプレイして 得られる利得は5.54になるので，GRIMから1MPに 逸脱するインセンティブは存在しない．また，1UPを プレイして得られる利得は5.48であり，やはりGRIM から逸脱するインセンティブは存在しない．この傾向 は図2aからも観察される．これらの3戦略しか存在し ない場合，どの戦略の分布から始めてもGRIMの人口 が最も多くなる．さらに26戦略のダイナミクスでも，
早い段階でこれら3つ以外の戦略がほとんどなくなり，
GRIMに収束することを確認した．
次にgを0.5に固定したまま，lを0.1に下げた場合を 考える．相手がGRIMをプレイするとき，GRIMは6.99, 1MPは6.86, 1UPは6.85の利得を与える．相手が1UP をプレイするとき，GRIMは9.19, 1MPは9.59, 1UPは 9.42の利得を与える．利得表上では1UPはGRIMを支 配している訳ではないが，相手が一定の確率でこれら 3つの戦略をプレイするとき，自分は1UPや1MPを プレイする方が期待利得が高くなる．実際，図2bでは GRIMに収束することはなくなり，3つの戦略が共存す るようになる．これは裏切られたときの損失lが小さく なることで，相手を絶対に許さないGRIMより，裏切 られて少しばかり損をしても将来の協力を見越して協 力に戻る1UPや1MPが生き残るようになったと考え られる．
(a)g=0.5,l=1.0 (b)g=0.5,l=0.1 図2: GRIM-1MP-1UP間のダイナミクス
参考文献
[1] ジョヨンジュン,岩崎敦,神取道宏,小原一郎,横尾 真.部分観測可能マルコフ決定過程を用いた私的観 測付き繰り返しゲームにおける均衡分析プログラ ム.情報処理学会論文誌, pp. 1234–1246, 2012.
[2] Drew Fudenberg Lorens A. Imhof and Martin A.
Nowak. Evolutionary cycles of cooperation and de- fection. in Proceedings of the National Academy of Sciences, Vol. 102, No. 31, pp. 10797–10800, 2005.
[3] Karl Sigmund. The Calculus of Selfishness. Princeton University Press, 2010.
