Using utility graphs to search for Pareto-optimal outcomes in complex, interdependent issue negotiations
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918156959744000 |
|---|---|
| author | Robu, Valentin Klein, Mark |
| author_facet | Robu, Valentin Klein, Mark |
| contents | This paper studies how utility graphs decomposition algorithms can be used to effectively search for Pareto-efficient outcomes in complex automated negotiation. We propose a number of algorithms that can efficiently handle high-dimensional utility graphs, and test them on a variety of utility graph topologies, generated based on state of the art methods for analysing complex graphs. We show that we can achieve exponential speed-up, for many structures, even for very large utility graphs. To our knowledge, our approach can handle the largest utility spaces to date for complex interdependent negotiations, in terms of number of issues. Moreover, we examine the performance of our algorithms across two different types of elicitation queries from the literature: value and comparison queries, thus making a connection between automated negotiation and the preference elicitation literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10885 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Using utility graphs to search for Pareto-optimal outcomes in complex, interdependent issue negotiations Robu, Valentin Klein, Mark Multiagent Systems 05C90 I.2.11 This paper studies how utility graphs decomposition algorithms can be used to effectively search for Pareto-efficient outcomes in complex automated negotiation. We propose a number of algorithms that can efficiently handle high-dimensional utility graphs, and test them on a variety of utility graph topologies, generated based on state of the art methods for analysing complex graphs. We show that we can achieve exponential speed-up, for many structures, even for very large utility graphs. To our knowledge, our approach can handle the largest utility spaces to date for complex interdependent negotiations, in terms of number of issues. Moreover, we examine the performance of our algorithms across two different types of elicitation queries from the literature: value and comparison queries, thus making a connection between automated negotiation and the preference elicitation literature. |
| title | Using utility graphs to search for Pareto-optimal outcomes in complex, interdependent issue negotiations |
| topic | Multiagent Systems 05C90 I.2.11 |
| url | https://arxiv.org/abs/2509.10885 |