Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : During the last decades, many combinatorial games involving two persons playing on a (directed) graph have received a lot of attention. Some examples of such games are the Angel problem, the Cops and Robbers, the Surveillance game, the Eternal Dominating Set and Eternal Set Cover. One of the main questions in these games is to decide if a given player has a winning strategy. That is, if it can always win regardless of behaviour of the other player. This question is often NP-hard. In the Cops and Robbers game and for the Surveillance game this question is PSPACE-complete [Mamino 2012, Fomin et al. 2012]. In this paper, we propose a fractional relaxation of these games. That is, we present a framework, based on linear programming techniques, that can be used to model any of the aforementioned games and some of its variants. As far as we know, it is the first time that such combinatorial games have been studied in this way and perspectives are promising. We also propose an algorithm that decides whether the first player can win the game in at most t turns. Moreover, under a weak assumption which is valid for all the aforementioned games, the fractional game gives us a lower bound for the integral game. For the Surveillance game and the Angel problem we show that there is, with high probability, a winning strategy which is in a O(log n) factor of the correspondent fractional parameter against a surfer or angel that follows a particular behavior. On the other hand, we prove that our framework cannot be used to approximate the classical Cops and Robber game.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Ronan Pardo Soares Connect in order to contact the contributor
Submitted on : Monday, September 30, 2013 - 11:48:39 AM
Last modification on : Wednesday, October 26, 2022 - 8:16:24 AM
Long-term archiving on: : Friday, April 7, 2017 - 4:22:43 AM


Files produced by the author(s)


  • HAL Id : hal-00865345, version 2



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⟩



Record views


Files downloads