Modeling complex nonlinear utility spaces using utility hyper-graphs

Rafik Hadfi, Takayuki Ito

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

7 Citations (Scopus)


There has been an increasing interest in automated negotiation and particularly negotiations that involve interdependent issues, known to yield complex nonlinear utility spaces. However, none of the proposed models was able to tackle the scaling problem as it commonly arises in realistic consensus making situations. In this paper we address this point by proposing a compact representation that minimizes the search complexity in this type of utility spaces. Our representation allows a modular decomposition of the issues and the constraints by mapping the utility space into an issue-constraint hyper-graph with the underlying interdependencies. Exploring the utility space reduces then to a message passing mechanism along the hyper-edges by means of utility propagation. We experimentally evaluate the model using parameterized random nonlinear utility spaces, showing that our mechanism can handle a large family of complex utility spaces by finding the optimal contracts, outperforming previous sampling-based approaches.

Original languageEnglish
Title of host publicationModeling Decisions for Artificial Intelligence
Subtitle of host publication11th International Conference, MDAI 2014, Proceedings
Place of PublicationSwitzerland
Number of pages12
ISBN (Electronic)9783319120546
ISBN (Print)9783319120539
Publication statusPublished - 1 Jan 2014
Externally publishedYes
EventInternational Conference on Modelling Decisions for Artificial Intelligence 2014 - Tokyo , Japan
Duration: 29 Oct 201431 Oct 2014
Conference number: 11th (Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Modelling Decisions for Artificial Intelligence 2014
Abbreviated titleMDAI 2014
Internet address


  • Complexity
  • Constraint-based utility spaces
  • Hyper-Graph
  • Interdependence
  • Max-Sum
  • Multi-Agent systems
  • Multi-Issue Negotiation
  • Nonlinear Utility
  • Optimization methods in AI and decision modeling
  • Utility and decision theory
  • Utility Propagation

Cite this