20 citations · 62 across the 23 of their papers we have counts for
19 papers · 1 filter
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.…
Stochastic Games with Limited Public Memory
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Abraham Neyman
We study the memory resources required for near-optimal play in two-player zero-sum stochastic games with the long-run average payoff. Although optimal strategies may not exist in…
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…
Games on Graphs: From Logic and Automata to Algorithms
Nathanaël Fijalkow, C. Aiswarya, Guy Avni +22
The objective of this book is to give a comprehensive presentation of the research field concerned with infinite duration games on graphs. Historically, these game models appeared…
One-Clock Priced Timed Games are PSPACE-hard
John Fearnley, Rasmus Ibsen-Jensen, Rahul Savani
The main result of this paper is that computing the value of a one-clock priced timed game (OCPTG) is PSPACE-hard. Along the way, we provide a family of OCPTGs that have an exponen…
All-Pay Bidding Games on Graphs
Guy Avni, Rasmus Ibsen-Jensen, Josef Tkadlec
In this paper we introduce and study {\em all-pay bidding games}, a class of two player, zero-sum games on graphs. The game proceeds as follows. We place a token on some vertex in…
Infinite-Duration Poorman-Bidding Games
Guy Avni, Thomas A. Henzinger, Rasmus Ibsen-Jensen
In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner or payoff of the game. Such games are central in fo…
The Big Match in Small Space
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Michal Koucký
In this paper we study how to play (stochastic) games optimally using little space. We focus on repeated games with absorbing states, a type of two-player, zero-sum concurrent mean…
Robust Draws in Balanced Knockout Tournaments
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Josef Tkadlec
Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decision-making and elections. The traditional computational question, that asks to compute…
Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives
Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen
We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of…
The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a…
Qualitative Analysis of Concurrent Mean-payoff Games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
We consider concurrent games played by two-players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the join…
The Complexity of Ergodic Mean-payoff Games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state graph. We focus on the important sub-class of ergodic games where all states are visited infini…
The complexity of interior point methods for solving discounted turn-based stochastic games
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen
We study the problem of solving discounted, two player, turn based, stochastic games (2TBSGs). Jurdzinski and Savani showed that 2TBSGs with deterministic transitions can be reduce…
Strategy complexity of finite-horizon Markov decision processes and simple stochastic games
Krishnendu Chatterjee, Rasmus Ibsen-Jensen
Markov decision processes (MDPs) and simple stochastic games (SSGs) provide a rich mathematical framework to study many important problems related to probabilistic systems. MDPs an…
A Faster Algorithm for Solving One-Clock Priced Timed Games
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced time…
Solving simple stochastic games with few coin toss positions
Rasmus Ibsen-Jensen, Peter Bro Miltersen
Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the numbe…
The complexity of solving reachability games using value and strategy iteration
Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
Two standard algorithms for approximately solving two-player zero-sum concurrent reachability games are value iteration and strategy iteration. We prove upper and lower bounds of 2…