非線形効用関数をもつエージェントのためのオークションに基づく交渉プロトコル

摘要

複数の論点を含む交渉問題を扱う研究領域として，複数論点交渉問題（Multi-issue negotiation）が有望視されている．既存の研究では，論点の独立性が仮定されていたため，エージェントは，線形の効用関数から得られる各論点に関する効用の総和をとることで，解を得ることができた．実世界の問題においては，複数の論点が相互依存関係にあり，複雑な非線形の効用関数をとる場合が多く，既存手法の適用には限界がある．本論文では，より一般性の高い，非線形の効用関数を仮定した交渉問題に対して有用な，新たな交渉プロトコルを提案する．具体的には，エージェントによる，効用空間のサンプリングに基づく提案の生成手法，及びオークションメカニズムに基づく，社会的効用の最大化のための合意形成手法を提案する．実験的評価により，非線形の効用空間において，提案プロトコルが既存手法をしのぐ性能をもつことを示す．また，提案プロトコルを，誘因両立な性質をもつプロトコルとして理論的に拡張可能であることを示す．