Modeling bilateral negotiations over multiple, interdependent issues using utility graphs

This paper presents an agent strategy for automated negotiation over a set of issues with interdependent valuations. First, we show how complex utility functions over a set of binary issues (or bundle of items) can be concisely represented using the formalism of utility graphs. Next, a heuristic is proposed for automated learning of an opponent's preference function, starting from a given (maximal) factorization of this function as a utility graph. The contribution of our approach is that it speeds up learning considerably compared to other techniques proposed in existing literature for this problem. An extended version of this paper is given in [1], while [2] provides a further extension of this work, in which collaborative filtering is used to learn the starting structure of such graphs.