On the complexity of utility hypergraphs

Rafik Hadfi, Takayuki Ito

Research output: Chapter in Book/Report/Conference proceedingChapter (Book)Researchpeer-review

6 Citations (Scopus)


We provide a new representation for nonlinear utility spaces by adopting a modular decomposition of the issues and the constraints. This is based on the intuition that constraint-based utility spaces are nonlinear with respect to issues, but linear with respect to the constraints. The result is a mapping from a utility space into an issue-constraint hypergraph with the underling interdependencies. Exploring the utility space reduces then to a message passing mechanism along the hyperedges by means of utility propagation. The optimal contracts are efficiently found using a variation of the Max-Sum algorithm. We experimentally evaluate the model using parameterized random nonlinear utility spaces, showing that it can handle a large family of complex utility spaces using several exploration strategies. We also evaluate the complexity of the generated utility spaces using the entropy and establish an optimal search strategy allowing a better scaling of the model.

Original languageEnglish
Title of host publicationRecent Advances in Agent-based Complex Automated Negotiation
EditorsNaoki Fukuta, Takayuki Ito, Minjie Zhang, Katsuhide Fujita, Valentin Robu
Number of pages17
ISBN (Electronic)9783319303079
ISBN (Print)9783319303055
Publication statusPublished - 1 Jan 2016
Externally publishedYes
EventInternational Workshop on Agent-based Complex Automated Negotiation (ACAN 2014) - Paris, France
Duration: 5 May 20149 May 2014
Conference number: 7th

Publication series

NameStudies in Computational Intelligence
ISSN (Print)1860-949X


WorkshopInternational Workshop on Agent-based Complex Automated Negotiation (ACAN 2014)
Abbreviated titleACAN 2014


  • message passing
  • optimal contract
  • utility space
  • bidding process
  • modular decomposition

Cite this