Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909626117652480 |
|---|---|
| author | Fioravantes, Foivos Gahlawat, Harmender Melissinos, Nikolaos |
| author_facet | Fioravantes, Foivos Gahlawat, Harmender Melissinos, Nikolaos |
| contents | Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied \textsc{Coalition Formation} problem. Here, we study a version of this problem where each team must additionally be of bounded size.
We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice.
Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded \emph{treewidth}) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded \emph{vertex cover number}). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22384 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size Fioravantes, Foivos Gahlawat, Harmender Melissinos, Nikolaos Data Structures and Algorithms Artificial Intelligence Imagine we want to split a group of agents into teams in the most \emph{efficient} way, considering that each agent has their own preferences about their teammates. This scenario is modeled by the extensively studied \textsc{Coalition Formation} problem. Here, we study a version of this problem where each team must additionally be of bounded size. We conduct a systematic algorithmic study, providing several intractability results as well as multiple exact algorithms that scale well as the input grows (FPT), which could prove useful in practice. Our main contribution is an algorithm that deals efficiently with tree-like structures (bounded \emph{treewidth}) for ``small'' teams. We complement this result by proving that our algorithm is asymptotically optimal. Particularly, there can be no algorithm that vastly outperforms the one we present, under reasonable theoretical assumptions, even when considering star-like structures (bounded \emph{vertex cover number}). |
| title | Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size |
| topic | Data Structures and Algorithms Artificial Intelligence |
| url | https://arxiv.org/abs/2505.22384 |