A parameterized point of view on forming small coalitions

Foivos Fioravantes (1) , Harmender Gahlawat (2) , Nikolaos Melissinos (1)

1 CTU - Czech Technical University in Prague
2 G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production

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, even considering star-like structures (bounded \emph{vertex cover number}) cannot result in an algorithm with a better running time, under reasonable theoretical assumptions.

Mots clés: Coalition formation; Additive separable hedonic games; Parameterized complexity

Domaines: Complexité [cs.CC]; Mathématique discrète [cs.DM]

Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos. A parameterized point of view on forming small coalitions. 2024. ⟨hal-04562753⟩