A collaborative filteringmethod for constructing utility graphs used in multi-issue negotiation 1

Graphical utility models represent powerful formalisms for modeling complex agent decisions involving multiple issues. in the context of negotiation, our previous work [3] has shown that using utility graphs enables agents to reach pareto-efficient agreements with a limited number of steps in high-dimensional negotiations involving non-linear dependencies. this paper considerably extends the results of [3], by proposing a method for constructing the utility graphs of buyers automatically, based on previous negotiation data. the proposed method is based on techniques inspired from item-based collaborative filtering, used in on-line recommendation algorithms. experimental results show that our approach is able to retrieve the structure of utility graphs on-line, with a relatively high degree of accuracy, even if a relatively small amount of data about concluded negotiations is available. furthermore, we provide a rigorous method for determining the cut-off number of edges for a wide category of random graphs.