[4K1-OS-16a] AI における離散構造処理と制約充足(1)

[4K1-OS-16a-01] 確率的な提携構造形成問題における精度保証付き近似解法の提案

〇松村 昂輝¹、沖本 天太¹、平山 勝敏¹ (1. 神戸大学)

キーワード：協力ゲーム理論、提携構造形成問題

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