[en] We focus on the problem of finding (the size of) a minimalwinning coalition in a multi-player game. 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.
Disciplines :
Electrical & electronics engineering
Author, co-author :
Brihaye, Thomas ; Université de Mons > Faculté des Sciences > Logique mathématique
