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