18 citations · 100 across the 28 of their papers we have counts for
19 papers · 1 filter
Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs
Michal Ajdarów, James C. A. Main, Petr Novotný +1
Markov decision processes (MDPs) are a canonical model to reason about decision making within a stochastic environment. We study a fundamental class of infinite MDPs: one-counter M…
Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies
James C. A. Main, Mickael Randour
We consider multi-dimensional payoff functions in partially observable Markov decision processes. We study the structure of the set of expected payoff vectors of all strategies (po…
Games on Graphs: From Logic and Automata to Algorithms
Nathanaël Fijalkow, C. Aiswarya, Guy Avni +22
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared…
How to Play Optimally for Regular Objectives?
Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour +1
This paper studies two-player zero-sum games played on graphs and makes contributions toward the following question: given an objective, how much memory is required to play optimal…
Timed Games with Bounded Window Parity Objectives
James C. A. Main, Mickael Randour, Jeremy Sproston
The window mechanism, introduced by Chatterjee et al. for mean-payoff and total-payoff objectives in two-player turn-based games on graphs, refines long-term objectives with time b…
Half-Positional Objectives Recognized by Deterministic Büchi Automata
Patricia Bouyer, Antonio Casares, Mickael Randour +1
In two-player games on graphs, the simplest possible strategies are those that can be implemented without any memory. These are called positional strategies. In this paper, we char…
Different Strokes in Randomised Strategies: Revisiting Kuhn's Theorem under Finite-Memory Assumptions
James C. A. Main, Mickael Randour
Two-player (antagonistic) games on (possibly stochastic) graphs are a prevalent model in theoretical computer science, notably as a framework for reactive synthesis. Optimal strate…
Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs
Patricia Bouyer, Mickael Randour, Pierre Vandenhove
We consider zero-sum games on infinite graphs, with objectives specified as sets of infinite words over some alphabet of colors. A well-studied class of objectives is the one of $ω…
Time Flies When Looking out of the Window: Timed Games with Window Parity Objectives
James C. A. Main, Mickael Randour, Jeremy Sproston
The window mechanism was introduced by Chatterjee et al. to reinforce mean-payoff and total-payoff objectives with time bounds in two-player turn-based games on graphs. It has sinc…
Arena-Independent Finite-Memory Determinacy in Stochastic Games
Patricia Bouyer, Youssouf Oualhadj, Mickael Randour +1
We study stochastic zero-sum games on graphs, which are prevalent tools to model decision-making in presence of an antagonistic opponent in a random environment. In this setting, a…
Games Where You Can Play Optimally with Arena-Independent Finite Memory
Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj +2
For decades, two-player (antagonistic) games on graphs have been a framework of choice for many important problems in theoretical computer science. A notorious one is controller sy…
Energy mean-payoff games
Véronique Bruyère, Quentin Hautem, Mickael Randour +1
In this paper, we study one-player and two-player energy mean-payoff games. Energy mean-payoff games are games of infinite duration played on a finite graph with edges labeled by 2…
Extending finite-memory determinacy by Boolean combination of winning conditions
Stéphane Le Roux, Arno Pauly, Mickael Randour
We study finite-memory (FM) determinacy in games on finite graphs, a central question for applications in controller synthesis, as FM strategies correspond to implementable control…
Reconciling Rationality and Stochasticity: Rich Behavioral Models in Two-Player Games
Mickael Randour
Two traditional paradigms are often used to describe the behavior of agents in multi-agent complex systems. In the first one, agents are considered to be fully rational and systems…
Expectations or Guarantees? I Want It All! A crossroad between games and MDPs
Véronique Bruyère, Emmanuel Filiot, Mickael Randour +1
When reasoning about the strategic capabilities of an agent, it is important to consider the nature of its adversaries. In the particular context of controller synthesis for quanti…
Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games
Véronique Bruyère, Emmanuel Filiot, Mickael Randour +1
We extend the quantitative synthesis framework by going beyond the worst-case. On the one hand, classical analysis of two-player games involves an adversary (modeling the environme…
Looking at Mean-Payoff and Total-Payoff through Windows
Krishnendu Chatterjee, Laurent Doyen, Mickael Randour +1
We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional ga…
Automated synthesis of reliable and efficient systems through game theory: a case study
Mickael Randour
Reactive computer systems bear inherent complexity due to continuous interactions with their environment. While this environment often proves to be uncontrollable, we still want to…
Strategy Synthesis for Multi-dimensional Quantitative Objectives
Krishnendu Chatterjee, Mickael Randour, Jean-François Raskin
Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitat…