Eliminating issue dependencies in complex negotiation domains

Issue title: Advances in Agent-mediated Automated Negotiations

Guest editors: Minjie Zhangx and Takayuki Itoy

Article type: Research Article

Authors: Hindriks, Koen | Jonker, Catholijn | Tykhonov, Dmytro^{; *}

Affiliations: Man-Machine Interaction, Faculty of EEMCS, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands | [x] University of Wollongong, Wollongong, NSW 2522, Australia | [y] Nagoya Institute of Technology, Gokiso, Showa, Nagoya 466-8555, Japan

Correspondence: [*] Corresponding author. Tel.: +31 15 278 3737; Fax: +31 15 2787141; E-mail: [email protected]

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.

Keywords: Multi-issue negotiation, issues dependencies, non-linear utility spaces, utility spaces approximation

DOI: 10.3233/MGS-2010-0162

Journal: Multiagent and Grid Systems , vol. 6, no. 5-6, pp. 477-501, 2010