7 papers · 1 filter
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…