138 citations · 262 across the 11 of their papers we have counts for
8 papers · 1 filter
Qualitative Multi-Objective Reachability for Ordered Branching MDPs
Kousha Etessami, Emanuel Martinov
We study qualitative multi-objective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently context-free MDPs, building on prior results fo…
Reachability for Branching Concurrent Stochastic Games
Kousha Etessami, Emanuel Martinov, Alistair Stewart +1
We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperf…
The complexity of approximating a trembling hand perfect equilibrium of a multi-player game in strategic form
Kousha Etessami, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen +1
We consider the task of computing an approximation of a trembling hand perfect equilibrium for an n-player game in strategic form, n >= 3. We show that this task is complete for th…
The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game of perfect recall
Kousha Etessami
We study the complexity of computing or approximating refinements of Nash equilibrium for a given finite n-player extensive form game of perfect recall (EFGPR), where n >= 3. Our r…
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
Tomáš Brázdil, Václav Brožek, Kousha Etessami +1
One-counter MDPs (OC-MDPs) and one-counter simple stochastic games (OC-SSGs) are 1-player, and 2-player turn-based zero-sum, stochastic games played on the transition graph of clas…
One-Counter Stochastic Games
Tomáš Brázdil, Václav Brožek, Kousha Etessami
We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stocha…
One-Counter Markov Decision Processes
Tomáš Brázdil, Václav Brožek, Kousha Etessami +2
We study the computational complexity of central analysis problems for One-Counter Markov Decision Processes (OC-MDPs), a class of finitely-presented, countable-state MDPs. OC-MDPs…
Recursive Concurrent Stochastic Games
Kousha Etessami, Mihalis Yannakakis
We study Recursive Concurrent Stochastic Games (RCSGs), extending our recent analysis of recursive simple stochastic games to a concurrent setting where the two players choose move…