InterJournal Complex Systems, 1821
Status: Accepted
Manuscript Number: [1821]
Submission Date: 2006
Reducing complexity of an agentís utility space for negotiating interdependent issues
Author(s): Koen Hindriks ,Catholijn Jonker ,Dmytro Tykhonov

Subject(s): CX.4



In software systems to support or simulate multi-issue negotiation the agentís preferences are modeled as a utility function. Relationships between issues and their utility are domain dependent and can have a complex non-linear character. As a result, the software systems face a computational complexity in their attempts to find an optimal solution in the complex utility space. The set of existing software support systems for negotiation can be divided in those that can and those that cannot handle dependencies between issues in the utility function. This paper proposes an approximation technique to simplify the agentís utility space in such way that the contribution of each issue is linearly separable from the contribution of the other issues in the agentís utility space. A set of natural assumptions about negotiation is proposed to improve the approximation result with respect to the negotiation outcome. The approximation technique is accompanied by a technique to measure the distance between the approximated and the real utility of bids to validate the choices of some key parameters. Furthermore, the linearization approximation procedure provides a utility function for which all existing utility-based software support systems are applicable, including the computationally much faster methods for dealing with independent issues. The method is illustrated in a case study.

Retrieve Manuscript
Submit referee report/comment

Public Comments: