On the complexity of utility hypergraphs

Rafik Hadfi; Takayuki Ito

doi:10.1007/978-3-319-30307-9_6

On the complexity of utility hypergraphs

Rafik Hadfi, Takayuki Ito

Research output: Chapter in Book/Report/Conference proceeding › Chapter (Book) › Research › peer-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 language	English
Title of host publication	Recent Advances in Agent-based Complex Automated Negotiation
Editors	Naoki Fukuta, Takayuki Ito, Minjie Zhang, Katsuhide Fujita, Valentin Robu
Publisher	Springer
Pages	89-105
Number of pages	17
Edition	1st
ISBN (Electronic)	9783319303079
ISBN (Print)	9783319303055
DOIs	https://doi.org/10.1007/978-3-319-30307-9_6
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	International Workshop on Agent-based Complex Automated Negotiation (ACAN 2014) - Paris, France Duration: 5 May 2014 → 9 May 2014 Conference number: 7th

Publication series

Name	Studies in Computational Intelligence
Volume	638
ISSN (Print)	1860-949X

Workshop

Workshop	International Workshop on Agent-based Complex Automated Negotiation (ACAN 2014)
Abbreviated title	ACAN 2014
Country/Territory	France
City	Paris
Period	5/05/14 → 9/05/14

Keywords

message passing
optimal contract
utility space
bidding process
modular decomposition

Access to Document

10.1007/978-3-319-30307-9_6

Cite this

@inbook{ce0043700eb24dd08ea0ba91e6f75d66,

title = "On the complexity of utility hypergraphs",

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.",

keywords = "message passing, optimal contract, utility space, bidding process, modular decomposition",

author = "Rafik Hadfi and Takayuki Ito",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/978-3-319-30307-9_6",

language = "English",

isbn = "9783319303055",

series = "Studies in Computational Intelligence",

publisher = "Springer",

pages = "89--105",

editor = "Naoki Fukuta and Takayuki Ito and Minjie Zhang and Katsuhide Fujita and Valentin Robu",

booktitle = "Recent Advances in Agent-based Complex Automated Negotiation",

edition = "1st",

note = "International Workshop on Agent-based Complex Automated Negotiation (ACAN 2014), ACAN 2014 ; Conference date: 05-05-2014 Through 09-05-2014",

}

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 edn, Studies in Computational Intelligence, vol. 638, Springer, pp. 89-105, International Workshop on Agent-based Complex Automated Negotiation (ACAN 2014), Paris, France, 5/05/14. https://doi.org/10.1007/978-3-319-30307-9_6

On the complexity of utility hypergraphs. / Hadfi, Rafik; Ito, Takayuki.

Recent Advances in Agent-based Complex Automated Negotiation. ed. / Naoki Fukuta; Takayuki Ito; Minjie Zhang; Katsuhide Fujita; Valentin Robu. 1st. ed. Springer, 2016. p. 89-105 (Studies in Computational Intelligence; Vol. 638).

Research output: Chapter in Book/Report/Conference proceeding › Chapter (Book) › Research › peer-review

TY - CHAP

T1 - On the complexity of utility hypergraphs

AU - Hadfi, Rafik

AU - Ito, Takayuki

N1 - Conference code: 7th

PY - 2016/1/1

Y1 - 2016/1/1

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

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

KW - message passing

KW - optimal contract

KW - utility space

KW - bidding process

KW - modular decomposition

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

U2 - 10.1007/978-3-319-30307-9_6

DO - 10.1007/978-3-319-30307-9_6

M3 - Chapter (Book)

AN - SCOPUS:84962286970

SN - 9783319303055

T3 - Studies in Computational Intelligence

SP - 89

EP - 105

BT - Recent Advances in Agent-based Complex Automated Negotiation

A2 - Fukuta, Naoki

A2 - Ito, Takayuki

A2 - Zhang, Minjie

A2 - Fujita, Katsuhide

A2 - Robu, Valentin

PB - Springer

T2 - International Workshop on Agent-based Complex Automated Negotiation (ACAN 2014)

Y2 - 5 May 2014 through 9 May 2014

ER -

On the complexity of utility hypergraphs

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Cite this