Retrieving the Structure of Utility Graphs Used in Multi-Item Negotiation through Collaborative Filtering of Aggregate Buyer Preferences

Summary. Graphical utility models represent powerful formalisms for modeling complex agent decisions involving multiple issues [3]. In the context of negotiation, it has been shown [14] that using utility graphs enables agents to reach Pareto-efficient agreements with a limited number of negotiation steps, even for high-dimensional negotiations over bundles of items involving non-linear complementarity / substitutability dependencies. This chapter considerably extends the results of our previous work [14], by proposing a method for constructing the utility graphs of buyers automatically, based on previous negotiation data. Our method is based on techniques inspired from item-based collaborative filtering, widely used in online recommendation algorithms. Experimental results show that our approach is able to retrieve the structure of utility graphs online, with a relatively high degree of accuracy, even for complex non-linear settings and even if a relatively small amount of data about concluded negotiations is available. Therefore, this chapter establishes a formal link between preference modeling techniques used in automated negotiation and preference modeling techniques used in social filtering.