42 citations · 185 across the 35 of their papers we have counts for
16 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.…
A Recursive Approach to Solving Parity Games in Quasipolynomial Time
Karoliina Lehtinen, Paweł Parys, Sven Schewe +1
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, whil…
Facility Reallocation on the Line
Bart de Keijzer, Dominik Wojtczak
We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by agents. The ai…
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…
Coordination Games on Weighted Directed Graphs
Krzysztof R. Apt, Sunil Simon, Dominik Wojtczak
We study strategic games on weighted directed graphs, in which the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy, au…
Improving the complexity of Parys' recursive algorithm
Karoliina Lehtinen, Sven Schewe, Dominik Wojtczak
Parys has recently proposed a quasi-polynomial version of Zielonka's recursive algorithm for solving parity games. In this brief note we suggest a variation of his algorithm that i…
On Strong Determinacy of Countable Stochastic Games
Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi +1
We study 2-player turn-based perfect-information stochastic games with countably infinite state space. The players aim at maximizing/minimizing the probability of a given event (i.…
Constrained Pure Nash Equilibria in Polymatrix Games
Sunil Simon, Dominik Wojtczak
We study the problem of checking for the existence of constrained pure Nash equilibria in a subclass of polymatrix games defined on weighted directed graphs. The payoff of a player…
Coordination Games on Directed Graphs
Krzysztof R. Apt, Sunil Simon, Dominik Wojtczak
We study natural strategic games on directed graphs, which capture the idea of coordination in the absence of globally common strategies. We show that these games do not need to ha…
Efficient Local Search in Coordination Games on Graphs
Sunil Simon, Dominik Wojtczak
We study strategic games on weighted directed graphs, where the payoff of a player is defined as the sum of the weights on the edges from players who chose the same strategy augmen…
Making the Best of Limited Memory in Multi-Player Discounted Sum Games
Anshul Gupta, Sven Schewe, Dominik Wojtczak
In this paper, we establish the existence of optimal bounded memory strategy profiles in multi-player discounted sum games. We introduce a non-deterministic approach to compute opt…
The Complexity of Nash Equilibria in Limit-Average Games
Michael Ummels, Dominik Wojtczak
We study the computational complexity of Nash equilibria in concurrent games with limit-average objectives. In particular, we prove that the existence of a Nash equilibrium in rand…
The Complexity of Nash Equilibria in Stochastic Multiplayer Games
Michael Ummels, Dominik Wojtczak
We analyse the computational complexity of finding Nash equilibria in turn-based stochastic multiplayer games with omega-regular objectives. We show that restricting the search spa…
Decision Problems for Nash Equilibria in Stochastic Games
Michael Ummels, Dominik Wojtczak
We analyse the computational complexity of finding Nash equilibria in stochastic multiplayer games with -regular objectives. While the existence of an equilibrium whose payoff f…
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…
The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
Michael Ummels, Dominik Wojtczak
We analyse the computational complexity of finding Nash equilibria in simple stochastic multiplayer games. We show that restricting the search space to equilibria whose payoffs fal…