開環境での協力ゲームにおける新しい解概念の提案

点击翻译按钮获取中文摘要

本研究では,インターネット等め開環境での協力ゲームにおける新しい解概念を提案することを目的とする.具体的には,ネットワークでの匿名性を用いて,参加者が談合を行ったり,架空の名義を用いるといった不正行為を行うことが可能な場合でも,そのような不正行為の影響を受けない利益の配分方法を考案する.また,提案する解概念に関しては,解を求めるための計算のコストを考慮し,動的な変化に対応して迅速に解を求めることを可能とする.本年度は,昨年度に提案した匿名操作不可能シャプレイ値をマルチエージェントシステムのトップレベルの国際会議であるAAMAS2008にて発表した.さらにこの論文は学生優秀論文賞を獲得した.一方で,利己的なエージェント間で協調関係を結ぶことが可能な協力ゲームにおいて,社会的に望ましい協調関係(提携)を形作ること,すなわち提携構造の形成は,重要な研究分野である.提携構造形成問題(CSG, Coalition Structure Generation)では,エージェントの集合を,社会的余剰(効用の総和)が最大化されるように分割する.すなわち,事前に適切な提携の候補を表現した上で,不正行為の影響を受けない利益の配分方法を考える.しかし,協力ゲームでは,エージェントが形成する提携に対して,その効用を与える関数(特性関数)が存在するが,任意の特性関数の表記量は指数的に増加するため,多くのエージェントが存在する協力ゲームでは,現実的な時間で提携構造形成問題の解を発見することは困難である.そこで,特性関数の特徴的な構造を利用した簡略記述法であるMC-nets (Marginal Contribution networks)およびSCG (Synergy Coalition Group)を利用して,提携構造形成問題を従来よりはるかに高速に解くことができることを明らかにした.なお,この研究成果は12月にDuke大学のVincet Conitzer氏を招聘して進めた成果である.