Negotiating with qualitative preferences: methods for generating bids effectively

Abstract

This thesis studies automated bilateral service negotiation in which a consumer and a producer agent negotiate on a particular service in a distributed environment. The key challenges of automated service negotiation that are addressed here are the automatic generation of the service o ers and the evaluation of the counter-o ers. The negotiating agents need to represent and reason about their user's preferences in order to negotiate e ectively on behalf of their users. Contrary to quantitative representations of preferences that are widely used in the literature, we advocate qualitative preference representations such as CP-nets. CP-nets enable users to represent their preferences in a compact and qualitative way but they almost always represent only a partial ordering. To cope with this limitation, this thesis develops a number of heuristics to be applied on CP-nets to estimate a total ordering of outcomes in terms of utilities from the partial ordering induced from a given CP-net. Consequently, the negotiating agent is able to employ existing utility-based negotiation strategies by means of estimated utilities. Our experimental results show that one can adopt e ective heuristics on CP-nets to negotiate with a high performance in a reasonable time. A negotiating agent also needs to understand its opponent's needs in order to generate accurate o ers leading to successful negotiations. However, in many negotiation settings the participant's preferences are private. Accordingly, this thesis develops a novel preference prediction algorithm to understand the opponent's preferences from bid exchanges during the negotiation. This algorithm is enhanced with the use of an ontology so that similar service o ers can be identi ed and treated similarly. Further, as the negotiation proceeds, the negotiating agent is able to revise its belief about the opponent's preferences. As a result, the agent generates well-targeted o ers that are more likely to be acceptable by the opponent. This results in successful negotiations in which the participants reach a consensus faster and detect failures early.