分割決定木を用いた分割関数ゲームの提携構造形成アルゴリズム

査 澳龍  越村 三幸  櫻井 祐子  横尾 真  

誌名
電子情報通信学会論文誌 D   Vol.J102-D   No.4   pp.313-323
発行日: 2019/04/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2018JDP7037
論文種別: 論文
専門分野: 情報ネットワーク
キーワード: 
マルチエージェントシステム,  協力ゲーム,  提携構造形成問題,  MaxSAT,  

本文: PDF(952.2KB)>>
論文を購入




あらまし: 
提携構造形成問題は協力ゲーム理論の問題の一つで,エージェント集合を社会的利得が最大となるよう分割する問題である.本論文で扱う分割関数ゲームでは,分割で得られる個々のチーム(提携)の利得はそのチームのメンバだけでは決まらず,他チームのメンバ構成の影響も受ける.また提携の利得は必ずしも正であるとは限らず,負の利得もあり得る.分割決定木は分割関数ゲームの簡潔記述法の一つである.本論文では,分割決定木で記述された問題の二つの解法を提案する.一つは深さ優先分枝限定法に基づくアルゴリズムで,もう一つはMaxSAT問題に帰着させる手法である.ランダムに生成した数千のインスタンスによる計算機実験を行い,利得が正のみの問題に対しては前者が優れ,負の利得もある問題に対しては後者が優れていることが分かった.