Modeling complex multi-issue negotiations using utility graphs

Valentin Robu*, D. J.A. Somefun, J. A. La Poutré

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

42 Citations (Scopus)


This paper presents an agent strategy for complex bilateral negotiations over many issues with inter-dependent valuations. We use ideas inspired by graph theory and probabilistic influence networks to derive efficient heuristics for negotiations about multiple issues. Experimental results show - under relatively weak assumptions with respect to the structure of the utility functions - that the developed approach leads to Pareto-efficient outcomes. Moreover, Pareto-efficiency can be reached with few negotiation steps, because we explicitly model and utilize the underlying graphical structure of complex utility functions. Consequently, our approach is applicable to domains where reaching an efficient outcome in a limited amount of time is important. Furthermore, unlike other solutions for high-dimensional negotiations, the proposed approach does not require a mediator.

Original languageEnglish
Number of pages8
Publication statusPublished - 1 Dec 2005
Externally publishedYes
Event4th International Conference on Autonomous Agents and Multi agent Systems, AAMAS 05 - Utrecht, Netherlands
Duration: 25 Jul 200529 Jul 2005


Conference4th International Conference on Autonomous Agents and Multi agent Systems, AAMAS 05


  • Decision theory
  • Game theory
  • Graphical models
  • Influence diagrams
  • Market-based methods
  • Negotiation
  • Utility graphs

Cite this