複数論点交渉問題のための効用空間の絞込みに基づくマルチエージェント交渉手法

摘要

マルチエージェントシステムの研究分野において，複数の論点を含む交渉問題が注目を集めている．複数論点交渉問題に関する既存の研究は，個々の論点の独立性を仮定しており，問題設定が現実的ではなかった．筆者らは，複数の論点が依存関係をもつ，すなわちエージェントの効用が非線形の効用関数で表現される交渉問題に注目している．ここでは，複雑な効用空間に対して，エージェントに対して，過剰に詳細な選好情報の開示を要求することなく，効用の高い解を得ることが課題となる．本論文では，これらの課題を解決するための新たな交渉プロトコルを提案する．提案プロトコルでは，エージェントが合意に成功し，高い効用を得られる可能性を保ちながら，効用空間の絞込みを反復実行する．本プロトコルの初期のラウンドでは，エージェントは，効用空間の中で有望な部分空間を粗く表明する入札を行い，すべてのエージェントにとって有望な空間を把握し，次に，その空間のみを対象とする，より詳細な入札を行う．実験により，大規模な非線形効用空間に対して，提案プロトコルは最適解に近い解が得られることを示し，またエージェント数が大きくなった場合でも，現実的な計算量で解が得られることを示す．