エージェントのタイプに基づく制限付き提携構造形成問題

摘要

タイプ付き提携構造形成(Coalition Structure GenerationBased on Agents Types, CSGt) 問題とは，エージェントの能力（タイプ）を用いた特性関数の簡略表記法に基づく提携構造形成(Coalition Structure Generation, CSG) 問題 である．CSG 問題とは，あるエージェントの集合を社会的余剰が最大化されるように，いくつかの提携に分割する問題であり，代表的な応用例として，分散経路決定問題 や排水処理システム等が挙げられる．従来のCSG 問題では，提携の利得は特性関数により与えられることを仮定しているため，その表記量はエージェント数に対して指数関数的に増加する．CSGt問題では，多数のエージェントの中には類似した能力をもつものが複数存在し，その数はそれほど多くない，すなわち，類似した能力をもつエージェントが複数存在するような状況を考え，エージェントのタイプを用いて特性関数を簡略表記している．