部分観測可能マルコフ決定過程を用いた私的観測付き繰返しゲームにおける均衡分析プログラム

• Item type: Journal(1)
• 公開日: 2012-11-15
• タイトル: 部分観測可能マルコフ決定過程を用いた私的観測付き繰返しゲームにおける均衡分析プログラム
• タイトル / 言語: en
• タイトル: Equilibrium Analysis Program of Repeated Games with Private Monitoring: A POMDP Approach
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：エージェントの理論とその応用] ゲーム理論，繰返しゲーム，部分観測可能マルコフ決定過程，有限状態機械
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州大学大学院システム情報科学府
• 著者所属: 九州大学大学院システム情報科学府
• 著者所属: 東京大学大学院経済学研究科
• 著者所属: UCLA経済学部
• 著者所属: 九州大学大学院システム情報科学府
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Faculty of Economics, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Economics, UCLA, Los Angeles
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者名: ジョヨンジュン; 岩崎, 敦; 神取, 道宏; 小原, 一郎; 横尾, 真
• 著者名(英): Yongjoon, Joe; Atsushi, Iwasaki; Michihiro, Kandori; Ichiro, Obara; Makoto, Yokoo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では不完全私的観測付き繰返しゲームの均衡を分析するプログラムを提案する．不完全私的観測付き繰返しゲームは，プレイヤが相手の行動についてノイズを含むシグナルを観測し，そのシグナルを他のプレイヤは観測できないという特徴を持つ．こうしたゲームは人工知能や経済の分野において様々な適用領域を持つため，大きく注目されている．しかし，このゲームにおける均衡を求めるには，非常に複雑な統計的推論が必要になるため，従来難しい未解決問題として知られていた．近年，均衡における振舞いを有限状態オートマトン（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）よりも効率的，つまり高い平均利得を実現することが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 53, 号 11, p. 2445-2456, 発行日 2012-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764