20 citations · 41 across the 31 of their papers we have counts for
8 papers · 1 filter
Temporal Explorability Games
Pete Austin, Nicolas Mazzocchi, Sougata Bose +1
Temporal graphs extend ordinary graphs with discrete time that affects the availability of edges. We consider solving games played on temporal graphs where one player aims to explo…
The Power of Counting Steps in Quantitative Games
Sougata Bose, Rasmus Ibsen-Jensen, David Purser +2
We study deterministic games of infinite duration played on graphs and focus on the strategy complexity of quantitative objectives. Such games are known to admit optimal memoryless…
Bounded-Memory Strategies in Partial-Information Games
Sougata Bose, Rasmus Ibsen-Jensen, Patrick Totzke
We study the computational complexity of solving stochastic games with mean-payoff objectives. Instead of identifying special classes in which simple strategies are sufficient to p…
Strategy Complexity of Büchi and Transience Objectives in Concurrent Stochastic Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study 2-player stochastic games on countable graphs. Players Max and Min seek respectively to maximize and minimize the probability of satisfying the game objective. The Büchi o…
Strategy Complexity of Reachability in Countable Stochastic 2-Player Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study countably infinite stochastic 2-player games with reachability objectives. Our results provide a complete picture of the memory requirements of -optimal (resp…
Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
Richard Mayr, Sven Schewe, Patrick Totzke +1
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative -regular condition: The maximizer aims to avoid running out of ene…