8 papers
Perturbation equivalence in labelled Markov chains
Syyeda Zainab Fatmi, Stefan Kiefer, James C. A. Main +1
Behavioural equivalences, such as language equivalence and probabilistic bisimilarity, are fundamental techniques for reducing the size of probabilistic models. However, these equi…
Simple Nash Equilibria for Qualitative Multiplayer Games
Mona Alluwaym, James C. A. Main, Sven Schewe
We investigate memory requirements for Nash and subgame-perfect equilibria in turn-based deterministic games with -regular objectives. We prove that memoryless randomised (i.e.,…
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…
Arena-Independent Memory Bounds for Nash Equilibria in Reachability Games
James C. A. Main
We study the memory requirements of Nash equilibria in turn-based multiplayer games on possibly infinite graphs with reachability, safety, shortest-path, Büchi and co-Büchi objecti…
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…
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…
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…