Eliminating issue dependencies in complex negotiation domains

Koen Hindriks, Catholijn Jonker, Dmytro Tykhonov*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

In multi-issue negotiations, issues may be negotiated independently or not. In the latter case, the utility associated with one issue depends on the value of another. Searching for good bids in a utility space based on multiple, dependent issues is in general intractable. Furthermore, existing negotiation strategies have proven to be efficient for negotiation in domains with independent issues cannot be used in case of dependencies between issues. To deal with this increased complexity, one can introduce a mediator in the negotiation setting, increase the power of computers exponentially, or approximate the utility space. Given the number of high quality and tractable algorithms that exist for independent issue sets, in this paper an approach that approximates the complex utility space by eliminating the dependencies is proposed. The approximated spaces can be used by existing negotiation algorithms that proved their worth in domains without issues dependencies. The approach exploits knowledge of experienced negotiators that determines for a domain and a set of negotiating parties the expected outcome range. The more specialised the knowledge of the negotiator, the more narrow the expected outcome range, and the more precise our approximation. Using the approximated space instead of the original without any further safeguards would be risky; what seems a good deal in the approximated space might be a bad deal in the original space. To mitigate this risk we introduce a safety procedures that interfere both in the approximation phase and in the bidding phase. The first safety procedure tunes the parameters of the approximation procedure to control the outcome deviation. We show how these parameters can be used to balance computational cost and accuracy of negotiation outcome. Based on experimental results specific values for the parameters are determined that, in general, provide a good balance between computational costs and accuracy. The second safeguard consists of a bid search wrapper algorithm that ensures that during the bidding no mistakes are made that are related to the use of the approximated space. Our approach is based on the assumption that the typical structure of general negotiation spaces is "near linear", making it worth to do the approximation and checking its accuracy.

Original languageEnglish
Pages (from-to)477-501
Number of pages25
JournalMultiagent and Grid Systems
Volume6
Issue number5-6
DOIs
Publication statusPublished - 1 Jan 2010
Externally publishedYes

Keywords

  • Issues dependencies
  • Multi-issue negotiation
  • Non-linear utility spaces
  • Utility spaces approximation

Fingerprint

Dive into the research topics of 'Eliminating issue dependencies in complex negotiation domains'. Together they form a unique fingerprint.

Cite this