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 language | English |
---|---|
Title of host publication | Modeling Decisions for Artificial Intelligence |
Subtitle of host publication | 11th International Conference, MDAI 2014, Proceedings |
Place of Publication | Switzerland |
Publisher | Springer |
Pages | 14-25 |
Number of pages | 12 |
ISBN (Electronic) | 9783319120546 |
ISBN (Print) | 9783319120539 |
Publication status | Published - 1 Jan 2014 |
Externally published | Yes |
Event | International Conference on Modelling Decisions for Artificial Intelligence 2014 - Tokyo , Japan Duration: 29 Oct 2014 → 31 Oct 2014 Conference number: 11th https://link.springer.com/book/10.1007/978-3-319-12054-6 (Proceedings) |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 8825 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Modelling Decisions for Artificial Intelligence 2014 |
---|---|
Abbreviated title | MDAI 2014 |
Country/Territory | Japan |
City | Tokyo |
Period | 29/10/14 → 31/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