Good friends are hard to find!

International audienceWe focus on the problem of finding (the~size of) a~minimal winning coalition in a multi-player game. More precisely, we~prove that deciding whether there is a winning coalition of size at most~\(k\) is NP-complete, while deciding whether \(k\) is the optimal size is DP-complete. We~also study different variants of our original problem: the function problem, where the aim is to effectively compute the coalition; more succinct encoding of the game; and richer families of winning objectives