Efficient issue-grouping approach for multiple interdependent issues negotiation between exaggerator agents

Katsuhide Fujita

doi:10.1016/j.dss.2013.05.016

2014-04-01

PRE

Katsuhide Fujita *

Takayuki Itō

Mark Klein

DOI：10.1016/j.dss.2013.05.016

原文链接

原文求助

摘要

En 中文

Many real-world negotiations involve multiple interdependent issues, which makes an agent's utility functions complex, with nonlinear shapes and multiple optima. Traditional negotiation mechanisms were designed for linear utilities, and do not fare well in nonlinear contexts. One of the main challenges in developing effective nonlinear negotiation protocols is scalability; it can be extremely difficult to find high-quality solutions 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 contract space into several largely independent sub-spaces. In this paper, we propose a method based on this concept. A mediator finds sub-contracts in each sub-space based on votes from the agents, and combines the sub-contracts to produce the final agreement. We demonstrate, experimentally, that our protocol allows high-optimality outcomes with greater scalability than previous efforts. We also demonstrate a method for addressing the potential problem of strategic non-truthful voting by the agents. (C) 2013 Elsevier B.V. All rights reserved.

Keyword:

Multi-issue negotiation

Nonlinear utility

Interdependency issues

Exaggerator agent

Multi-agent system