Nicolas Markey

Abstract

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.

@inproceedings{time2008-BGMR,
  author =              {Brihaye, {\relax Th}omas and Ghannem, Mohamed and
                         Markey, Nicolas and Rieg, Lionel},
  title =               {Good friends are hard to find!},
  booktitle =           {{P}roceedings of the 15th {I}nternational
                         {S}ymposium on {T}emporal {R}epresentation and
                         {R}easoning ({TIME}'08)},
  acronym =             {{TIME}'08},
  publisher =           {IEEE Comp. Soc. Press},
  pages =               {32-40},
  year =                {2008},
  month =               jun,
  doi =                 {10.1109/TIME.2008.10},
  abstract =            {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.},
}