Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929432162205696 |
|---|---|
| author | Taguelmimt, Redha Aknine, Samir Boukredera, Djamila Changder, Narayan Sandholm, Tuomas |
| author_facet | Taguelmimt, Redha Aknine, Samir Boukredera, Djamila Changder, Narayan Sandholm, Tuomas |
| contents | Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16092 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search Taguelmimt, Redha Aknine, Samir Boukredera, Djamila Changder, Narayan Sandholm, Tuomas Multiagent Systems Artificial Intelligence Computer Science and Game Theory I.2; F.2 Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions. |
| title | Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search |
| topic | Multiagent Systems Artificial Intelligence Computer Science and Game Theory I.2; F.2 |
| url | https://arxiv.org/abs/2407.16092 |