[4N2-J-7] エージェント: 社会的マルチエージェント

[4N2-J-7-04] 協力グラフゲームにおける提携構造形成問題

〇渡部 恵海¹、越村 三幸¹、櫻井 祐子²、横尾 真^1,3 (1. 九州大学大学院システム情報科学府、2. 産業技術総合研究所人工知能研究センター、3. 理化学研究所革新知能統合研究センターAIP)

キーワード：ゲーム理論、協力ゲーム、提携構造形成問題

協力ゲーム理論は，複数の自律的エージェントによる提携行が可能な場合のエージェントの振る舞いに関する理論である[中山08]．一般に，協力ゲームは，特性関数と呼ばれる関数でゲームが表現される．特性関数とは，エージェントの任意の部分集合(提携) を入力として，提携値を出力する関数である．本研究では，特性関数が重み付き無向グラフで表現される，協力グラフゲームにおける，提携構造形成問題を考える．任意の特性関数を表するためには，エージェント数をn とするとO(2n) の表記量が必要になる．そのため，文献[Deng 94] で，特性関数を簡潔に表現する，協力グラフゲームが提案されて以降，このゲームに関する研究が数多く存在するが，計算複雑性に関する議論が主流であり，実際に最適化問題として定式化し，計算機実験を行っている研究は存在しない．本論文では，協力グラフゲームにおける提携構造形成問題を整数計画問題として定式化するとともに，MaxSAT 符号化を行う．計算機実験では，整数計画問題を商用ソルバーを用いて解いた場合とMaxSAT 符号化によってMaxSATソルバーで解いた場合の比較実験を行う．