5 papers
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.…
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 objec…
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…
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…
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…