DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
Rechercher
(titres de publication, de périodique et noms de colloque inclus)
2008-06-01 - Article/Dans un journal avec peer-review - Anglais - 9 page(s)

Brihaye Thomas , Markey Nicolas, Ghannem Mohamed, Rieg Lionel, "Good Friends are Hard to Find!" in IEEE proceedings, 32-40

  • Codes CREF : Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Mathématiques effectives (S820)
Texte intégral :

Abstract(s) :

(Anglais) 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.

Identifiants :
  • DOI : 10.1109/TIME.2008.10