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 | 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
Cite this
}
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 proceeding › Conference Paper › Research › peer-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 -