On the complexity of utility hypergraphs

Rafik Hadfi, Takayuki Ito

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

6 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages89-105
Number of pages17
Edition1st
ISBN (Electronic)9783319303079
ISBN (Print)9783319303055
DOIs
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
Volume638
ISSN (Print)1860-949X

Workshop

WorkshopInternational Workshop on Agent-based Complex Automated Negotiation (ACAN 2014)
Abbreviated titleACAN 2014
CountryFrance
CityParis
Period5/05/149/05/14

Keywords

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

Cite this

Hadfi, R., & Ito, T. (2016). On the complexity of utility hypergraphs. In N. Fukuta, T. Ito, M. Zhang, K. Fujita, & V. Robu (Eds.), Recent Advances in Agent-based Complex Automated Negotiation (1st ed., pp. 89-105). (Studies in Computational Intelligence; Vol. 638). Springer. https://doi.org/10.1007/978-3-319-30307-9_6