2 citations · 2 across the 4 of their papers we have counts for
9 papers
Linear Extensions of Rotor-Routing in Directed Graphs: Reachability Problems
David Auger, Pierre Coucheney, Kossi Roland Etse
We develop a unified framework for rotor-routing that extends the classical model to a broad class of multigraphs equipped with Generalized Rotor Mechanisms (GRM). This perspective…
Generalized ARRIVAL Problem for Rotor Walks in Path Multigraphs
David Auger, Pierre Coucheney, Loric Duhazé +1
Rotor walks are cellular automata that determine deterministic traversals of particles in a directed multigraph using simple local rules, yet they can generate complex behaviors. F…
Nonatomic Non-Cooperative Neighbourhood Balancing Games
David Auger, Johanne Cohen, Antoine Lobstein
We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resource…
Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs
David Auger, Pierre Coucheney, Loric Duhaze
A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal…
A Generic Strategy Improvement Method for Simple Stochastic Games
D. Auger, X. Badin de Montjoye, Y. Strozecki
We present a generic strategy iteration algorithm (GSIA) to find an optimal strategy of a simple stochastic game (SSG). We prove the correctness of GSIA, and derive a general compl…
Solving Simple Stochastic Games with few Random Nodes faster using Bland's Rule
David Auger, Pierre Coucheney, Yann Strozecki
The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm which works in expected time. We first give a simpler iterative var…
Finding Optimal Strategies of Almost Acyclic Simple Stochatic Games
David Auger, Pierre COUCHENEY, Yann Strozecki
The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the few problems in wh…
Multiple Tree for Partially Observable Monte-Carlo Tree Search
David Auger
We propose an algorithm for computing approximate Nash equilibria of partially observable games using Monte-Carlo tree search based on recent bandit methods. We obtain experimental…
Watching Systems in graphs: an extension of Identifying Codes
David Auger, Irène Charon, Olivier Hudry +1
We introduce the notion of watching systems in graphs, which is a generalization of that of identifying codes. We give some basic properties of watching systems, an upper bound on…