Fractional Combinatorial Two-Player Games

Frédéric Giroire 1 Nicolas Nisse 1 Stéphane Pérennes 1 Ronan Pardo Soares 2, 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : Durant les dernières décennies, de nombreux jeux combinatoires impliquant deux personnes jouant sur un graphe ont reçu beaucoup d'attention. Quelques exemples de ces jeux sont le problème de l'ange et du démon, les Gendarmes et Voleurs, le jeu de surveillance, l'ensemble dominant éternel et la couverture éternele. L'une des principales questions dans ces jeux est de décider si un joueur a une stratégie gagnante. Il s'agit de savoir si un joueur peut toujours gagner quelle que soit la strategie de l'autre joueur. Cette question correspond généralement à un problème NP-dificile. Dans le jeux des Gendarmes et Voleurs et dans le jeu de surveillance, cette question est PSPACE-complet [Mamino 2012 Fomin et al. 2012]. Dans cet article, nous proposons une relaxation fractionnaire de ces jeux. Autrement dit, nous présentons un cadre, basé sur des techniques de programmation linéaire, qui peut être utilisé pour modéliser ces jeux et certaines de leurs variantes. Pour autant que nous sachions, c'est la premiere fois que ces jeux sont étudiés de cette façon et les perspectives sont prometteuses. Nous proposons également un algorithme qui décide si le premier joueur a une strategie gagnante en au plus t tours. De plus, nous montrons que le jeu fractionnaire donne une borne inférieure pour le jeu entier si le jeu satisfait une propriété simple qui est satisfaite par chacun des jeux mentionnés ci-dessus.
Type de document :
Rapport
[Research Report] RR-8371, INRIA. 2013
Liste complète des métadonnées


https://hal.inria.fr/hal-00865345
Contributeur : Ronan Pardo Soares <>
Soumis le : lundi 30 septembre 2013 - 11:48:39
Dernière modification le : vendredi 16 septembre 2016 - 15:19:47
Document(s) archivé(s) le : vendredi 7 avril 2017 - 04:22:43

Fichier

RR-8371.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00865345, version 2

Collections

Citation

Frédéric Giroire, Nicolas Nisse, Stéphane Pérennes, Ronan Pardo Soares. Fractional Combinatorial Two-Player Games. [Research Report] RR-8371, INRIA. 2013. <hal-00865345v2>

Partager

Métriques

Consultations de
la notice

365

Téléchargements du document

159