[4K1-OS-16a] [Organized Session] OS-16

[4K1-OS-16a-01] Approximate Algorithm for Probabilistic Coalition Structure Generation with Quality Bound

〇Kouki Matsumura¹, Tenda Okimoto¹, Katsutoshi Hirayama¹ (1. Kobe University)

Keywords:cooperative game theory, coalition structure generation

提携構造形成 (Coalition Structure Generation, CSG)問題とは，協力ゲーム理論における基本的な枠組みの一つであり，与えられたエージェントの集合を社会的余剰が最大化されるように，いくつかの提携に分割する問題である．確率的な提携構造形成 (Probabilistic Coalition Structure Generation, PCSG)問題とは，各エージェントの（任意の）提携への参加の有無が確率により与えられているCSG問題である．本論文では，PCSG問題における，解精度を保証する高速な近似解法 (Approximate Algorithm based on Participation Rate, AAPR)を提案する．さらに，本解法によって得られる解の絶対誤差の上界を与える．