協力ゲームにおける特性関数のエージェントのタイプに基づく簡略表記法

摘要

協力ゲーム理論は，利己的に行動するエージェント間で拘束力のある合意が可能な場合のエージェントの振舞いに関する理論である．従来の協力ゲームの研究では，提携の利得は特性関数と呼ばれるブラックボックスの関数により与えられることを仮定していたため，その表記量と解概念に関する諸問題の計算量がエージェント数に関して指数的に増加していた．ごく最近，Shrotらにより，エージェントのタイプという概念が導入された．タイプはエージェントの限界貢献度の遠いを表し，エージェントの数は多くても，タイプの数は少ない場合が多い．タイプの数が制限されている場合，解概念に関する諸問題の計算量ほ多項式となる．しかしながら，Shrotらは，特性関数は従来手法で表記されていることを前提に，その状況で，同じタイプのエージェントを識別していた．これに対し，本論文では，エージェントのタイプが与えられていると仮定し．そのタイプを陽に用いて特性関数を記述する方法を提案する．提案手法を用いた場合，その表記量はエージェント数に関する多項式となる．更に，解概念に関する諸問題及び提携構造形成問題の計算量が多項式となることを示す．