From the 1 of 9 linked papers with an AI index.
9 papers
Generalised Reachability Games
Sougata Bose, Nathanael Fijalkow, Daniel Hausmann +4
The paper investigates two-player turn-based games on graphs where a player must visit multiple target sets (generalised reachability), analyzing the computational complexity, para…
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.…
Resolving Nondeterminism by Chance
Soumyajit Paul, David Purser, Sven Schewe +3
History-deterministic automata are those in which nondeterministic choices can be correctly resolved stepwise: there is a strategy to select a continuation of a run given the next…
The Complexity of Games with Randomised Control
Sarvin Bahmani, Rasmus Ibsen-Jensen, Soumyajit Paul +5
We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly.…
Good-for-MDP State Reduction for Stochastic LTL Planning
Christoph Weinhuber, Giuseppe De Giacomo, Yong Li +2
We study stochastic planning problems in Markov Decision Processes (MDPs) with goals specified in Linear Temporal Logic (LTL). The state-of-the-art approach transforms LTL formulas…
Generalised Reachability Games Revisited
Sougata Bose, Daniel Hausmann, Soumyajit Paul +2
Classic reachability games on graphs are zero-sum games, where the goal of one player, Eve, is to visit a vertex from a given target set, and that of other player, Adam, is to prev…