Good friends are hard to find!

Thomas Brihaye (1) , Mohamed Ghannem , Nicolas Markey (2) , Lionel Rieg (3)

1 Institut de Mathématiques [Mons]
2 LSV - Laboratoire Spécification et Vérification [Cachan]
3 LIP - Laboratoire de l'Informatique du Parallélisme

We 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.

Domaines: Logique en informatique [cs.LO]

Thomas Brihaye, Mohamed Ghannem, Nicolas Markey, Lionel Rieg. Good friends are hard to find!. Proceedings of the 15th International Symposium on Temporal Representation and Reasoning (TIME'08), 2008, Montréal, Canada. pp.32-40, ⟨10.1109/TIME.2008.10⟩. ⟨hal-01194596⟩