Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
This addresses coalition formation with size constraints, offering practical algorithms for scenarios like team formation, but it is incremental as it builds on existing coalition formation models.
The paper tackles the problem of forming coalitions with bounded team sizes, providing exact algorithms that scale well for tree-like structures and proving intractability results, including an asymptotically optimal algorithm for small teams.
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}).