Modeling complex nonlinear utility spaces using utility hyper-graphs

Rafik Hadfi, Takayuki Ito

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

4 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages14-25
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
https://link.springer.com/book/10.1007/978-3-319-12054-6 (Proceedings)

Publication series

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

Conference

ConferenceInternational Conference on Modelling Decisions for Artificial Intelligence 2014
Abbreviated titleMDAI 2014
CountryJapan
CityTokyo
Period29/10/1431/10/14
Internet address

Keywords

  • 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

Hadfi, R., & Ito, T. (2014). Modeling complex nonlinear utility spaces using utility hyper-graphs. In Modeling Decisions for Artificial Intelligence : 11th International Conference, MDAI 2014, Proceedings (pp. 14-25). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8825). Switzerland: Springer.
Hadfi, Rafik ; Ito, Takayuki. / Modeling complex nonlinear utility spaces using utility hyper-graphs. Modeling Decisions for Artificial Intelligence : 11th International Conference, MDAI 2014, Proceedings. Switzerland : Springer, 2014. pp. 14-25 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{300a8f4dbd8349c2a1cccb0514830d35,
title = "Modeling complex nonlinear utility spaces using utility hyper-graphs",
abstract = "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.",
keywords = "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",
author = "Rafik Hadfi and Takayuki Ito",
year = "2014",
month = "1",
day = "1",
language = "English",
isbn = "9783319120539",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "14--25",
booktitle = "Modeling Decisions for Artificial Intelligence",

}

Hadfi, R & Ito, T 2014, Modeling complex nonlinear utility spaces using utility hyper-graphs. in Modeling Decisions for Artificial Intelligence : 11th International Conference, MDAI 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8825, Springer, Switzerland, pp. 14-25, International Conference on Modelling Decisions for Artificial Intelligence 2014, Tokyo , Japan, 29/10/14.

Modeling complex nonlinear utility spaces using utility hyper-graphs. / Hadfi, Rafik; Ito, Takayuki.

Modeling Decisions for Artificial Intelligence : 11th International Conference, MDAI 2014, Proceedings. Switzerland : Springer, 2014. p. 14-25 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8825).

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

TY - GEN

T1 - Modeling complex nonlinear utility spaces using utility hyper-graphs

AU - Hadfi, Rafik

AU - Ito, Takayuki

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Complexity

KW - Constraint-based utility spaces

KW - Hyper-Graph

KW - Interdependence

KW - Max-Sum

KW - Multi-Agent systems

KW - Multi-Issue Negotiation

KW - Nonlinear Utility

KW - Optimization methods in AI and decision modeling

KW - Utility and decision theory

KW - Utility Propagation

UR - http://www.scopus.com/inward/record.url?scp=84911213063&partnerID=8YFLogxK

M3 - Conference Paper

AN - SCOPUS:84911213063

SN - 9783319120539

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 14

EP - 25

BT - Modeling Decisions for Artificial Intelligence

PB - Springer

CY - Switzerland

ER -

Hadfi R, Ito T. Modeling complex nonlinear utility spaces using utility hyper-graphs. In Modeling Decisions for Artificial Intelligence : 11th International Conference, MDAI 2014, Proceedings. Switzerland: Springer. 2014. p. 14-25. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).