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