An Approach to Scalable Multi-issue Negotiation: Decomposing the Contract Space Based on Issue Interdependencies
An Approach to Scalable Multi-issue Negotiation: Decomposing the Contract Space Based on Issue Interdependencies
复制标题
DOI：
10.1111/j.1467-8640.2012.00462.x
复制
发表时间：
2010-08
期刊：
影响因子：
--
通讯作者：
K. Fujita;Takayuki Ito;M. Klein
中科院分区：
文献类型：
--
作者：
K. Fujita;Takayuki Ito;M. Klein
现实世界中的协商大多涉及多个相互依赖的问题，这使得主体的效用函数变得非线性。传统的谈判机制是为线性公用事业设计的，在非线性环境下表现不佳。开发有效的非线性协商协议的主要挑战之一是可扩展性；当存在许多问题时，由于计算上的困难，它们可能会产生过高的失败率。在保持高质量结果的同时减少计算成本的一种合理方法是将效用空间分解成几个基本上独立的子空间。在这篇文章中，我们提出了一种基于四种问题相互依赖的效用空间分解方法。与以前的努力相比，这种方法具有更好的结果和更大的可扩展性。我们还分析了问题相互依赖的类型如何影响解的最优性和失败率。
Most real-world negotiation involves multiple interdependent issues, which makes an agent's utility functions nonlinear. Traditional negotiation mechanisms, which were designed for linear utilities, do not fare well in nonlinear contexts. One of the main challenges in developing effective nonlinear negotiation protocols is scalability; they can produce excessively high failure rates, when there are many issues, due to computational intractability. One reasonable approach to reducing computational cost, while maintaining good quality outcomes, is to decompose the utility space into several largely independent sub-spaces. In this paper, we propose a method for decomposing a utility space based on four types of issue inter-dependencies. This method allows good outcomes with greater scalability than previous efforts. We also analyze how the types of issue interdependency influence the solution optimality and failure rate.