25 citations · 66 across the 15 of their papers we have counts for
19 papers
Positional Determinacy with Colored Vertices: a 1-to-2-Player Lift
Raphaël Berthon, Stéphane Le Roux
Positional determinacy of vertex-colored parity games was proved in the 1990s, which directly implies positional determinacy of edge-colored parity games. In 2006, it was shown tha…
Sub-game optimal strategies in concurrent games with prefix-independent objectives
Benjamin Bordais, Patricia Bouyer, Stéphane Le Roux
We investigate concurrent two-player win/lose stochastic games on finite graphs with prefix-independent objectives. We characterize subgame optimal strategies and use this characte…
Playing (Almost-)Optimally in Concurrent Büchi and co-Büchi Games
Benjamin Bordais, Patricia Bouyer, Stéphane Le Roux
We study two-player concurrent stochastic games on finite graphs, with Büchi and co-Büchi objectives. The goal of the first player is to maximize the probability of satisfying the…
The Complexity of Graph-Based Reductions for Reachability in Markov Decision Processes
Stephane Le Roux, Guillermo A. Perez
We study the never-worse relation (NWR) for Markov decision processes with an infinite-horizon reachability objective. A state q is never worse than a state p if the maximal probab…
On the existence of weak subgame perfect equilibria
Véronique Bruyère, Stéphane Le Roux, Arno Pauly +1
We study multi-player turn-based games played on (potentially infinite) directed graphs. An outcome is assigned to every play of the game. Each player has a preference relation on…
A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract)
Stéphane Le Roux, Arno Pauly
We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and…
Minkowski games
Stéphane Le Roux, Arno Pauly, Jean-François Raskin
We introduce and study Minkowski games. These are two player games, where the players take turns to chose positions in based on some rules. Variants include boundedn…
Extending Finite Memory Determinacy to Multiplayer Games
Stéphane Le Roux, Arno Pauly
We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium…
Stable states of perturbed Markov chains
Volker Betz, Stephane Le Roux
Given an infinitesimal perturbation of a discrete-time finite Markov chain, we seek the states that are stable despite the perturbation, \textit{i.e.} the states whose weights in t…
Infinite subgame perfect equilibrium in the Hausdorff difference hierarchy
Stephane Le Roux
Subgame perfect equilibria are specific Nash equilibria in perfect information games in extensive form. They are important because they relate to the rationality of the players. Th…
Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed Markov chains
Volker Betz, Stéphane Le Roux
We consider a simple but important class of metastable discrete time Markov chains, which we call perturbed Markov chains. Basically, we assume that the transition matrices depend…
On terminating improvement in two-player games
Stephane Le Roux
A real-valued game has the finite improvement property (FIP), if starting from an arbitrary strategy profile and letting the players change strategies to increase their individual…
Weihrauch degrees of finding equilibria in sequential games
Stephane Le Roux, Arno Pauly
We consider the degrees of non-computability (Weihrauch degrees) of finding winning strategies (or more generally, Nash equilibria) in infinite sequential games with certain winnin…
Equilibria in multi-player multi-outcome infinite sequential games
Stéphane Le Roux, Arno Pauly
We investigate the existence of certain types of equilibria (Nash, -Nash, subgame perfect, -subgame perfect, Pareto-optimal) in multi-player multi-outcome…
A semi-potential for finite and infinite sequential games
Stéphane Le Roux, Arno Pauly
We consider a dynamical approach to game in extensive forms. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushki…
Infinite sequential Nash equilibrium
Stephane Le Roux
In game theory, the concept of Nash equilibrium reflects the collective stability of some individual strategies chosen by selfish agents. The concept pertains to different classes…
Finite choice, convex choice and finding roots
Stéphane Le Roux, Arno Pauly
We investigate choice principles in the Weihrauch lattice for finite sets on the one hand, and convex sets on the other hand. Increasing cardinality and increasing dimension both c…
Connected Choice and the Brouwer Fixed Point Theorem
Vasco Brattka, Stéphane Le Roux, Joseph S. Miller +1
We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed…
From winning strategy to Nash equilibrium
Stéphane Le Roux
Game theory is usually considered applied mathematics, but a few game-theoretic results, such as Borel determinacy, were developed by mathematicians for mathematics in a broad sens…