著者

ジョヨンジュン 岩崎 敦 神取 道宏 小原 一郎 横尾 真

出版者

情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.53, no.11, pp.2445-2456, 2012-11-15

---

本論文では不完全私的観測付き繰返しゲームの均衡を分析するプログラムを提案する.不完全私的観測付き繰返しゲームは,プレイヤが相手の行動についてノイズを含むシグナルを観測し,そのシグナルを他のプレイヤは観測できないという特徴を持つ.こうしたゲームは人工知能や経済の分野において様々な適用領域を持つため,大きく注目されている.しかし,このゲームにおける均衡を求めるには,非常に複雑な統計的推論が必要になるため,従来難しい未解決問題として知られていた.近年,均衡における振舞いを有限状態オートマトン(finite state automaton,FSA)で記述し,部分観測可能マルコフ決定過程(partially observable Markov decision process,POMDP)の理論を用いることで,あるFSAが均衡を構成するかどうかを明らかにできることが示された.しかし,その具体的な実装方法や実際の問題へ適用するためのプログラムは提供されていない.そこで本論文ではまず,標準的なPOMDPソルバのラッパとなるプログラムを開発する.このプログラムでは私的観測付き繰返しゲームの記述とFSAを入力として,そのFSAが対称的均衡を構成するかどうかを自動的に確認できる.さらに,このプログラムを繰返し囚人のジレンマに適用し,k-期相互処罰(k-MP)と呼ぶ新しいFSAのクラスを発見した.k-MPにおけるプレイヤは,初めに協力し相手の裏切りを観測するとそれ以降自分も裏切るが,続けてk回裏切りを観測すると元に戻り協力する.このプログラムを用いて状態数3以下のFSAを全探索した結果,繰返しゲームにおける観測構造パラメータのいくらかの範囲で,2-MPが他の純粋戦略均衡より優れており,従来よく知られている均衡である無限期罰則のトリガ戦略(grim-trigger)よりも効率的,つまり高い平均利得を実現することが分かった.The present paper investigates repeated games with imperfect private monitoring, where each player privately receives a noisy observation (signal) of the opponent's action. Such games have been paid considerable attention in the AI and economics literature. Since players do not share common information in such a game, characterizing players' optimal behavior is substantially complex. As a result, identifying pure strategy equilibria in this class has been known as a hard open problem. Recently, Kandori and Obara (2010) showed that the theory of partially observable Markov decision processes (POMDP) can be applied to identify a class of equilibria where the equilibrium behavior can be described by a finite state automaton (FSA). However, they did not provide a practical method or a program to apply their general idea to actual problems. We first develop a program that acts as a wrapper of a standard POMDP solver, which takes a description of a repeated game with private monitoring and an FSA as inputs, and automatically checks whether the FSA constitutes a symmetric equilibrium. We apply our program to repeated Prisoner's dilemma and find a novel class of FSA, which we call k-period mutual punishment (k-MP). The k-MP starts with cooperation and defects after observing a defection. It restores cooperation after observing defections k-times in a row. Our program enables us to exhaustively search for all FSAs with at most three states, and we found that 2-MP beats all the other pure strategy equilibria with at most three states for some range of parameter values and it is more efficient in an equilibrium than the grim-trigger.