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
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00865345
Contributor : Ronan Pardo Soares <>
Submitted on : Monday, September 30, 2013 - 11:48:39 AM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Friday, April 7, 2017 - 4:22:43 AM

File

RR-8371.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

457

Files downloads

224