Constructing the structure of utility graphs used in multi-item negotiation through collaborative filtering of aggregate buyer preferences

Negotiation represents a key form of interaction between providers and consumers in electronic markets. One of the main benefits of negotiation in e-commerce is that it enables greater customization to individual customer preferences, and it supports buyer decisions in settings which require agreements over complex contracts. Automating the negotiation process, through the use of intelligent agents which negotiate on behalf of their owners, enables electronic merchants to go beyond price competition by providing flexible contracts, tailored to the needs of individual buyers. Multi-issue (or multi-item) negotiation models are particularly useful for this task, since with multi-issue negotiations mutually beneficial ("win-win") contracts can be found [7, 9, 12, 13, 20]. In this chapter we consider the negotiation over the contents of a bundle of items (thus we use the term 'multi-item' negotiation), though, at a conceptual level, the setting is virtually identical to previous work on multi-issue negotiation involving only binary-valued issues (e.g. [13]). A bottleneck in most existing approaches to automated negotiation is that they only deal with linearly additive utility functions, and do not consider high-dimensional negotiations and in particular, the problem of inter-dependencies between evaluations for different items. This is a significant problem, since identifying and exploiting substitutability/ complementarity effects between different items can be crucial in reaching mutually profitable deals.