Search

• < Previous
• 1
• Next >

---

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 space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the&nbsp;[&hellip;]

---

A Recursive Approach to Solving Parity Games in Quasipolynomial Time

Karoliina Lehtinen ; Paweł Parys ; Sven Schewe ; Dominik Wojtczak.

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, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of&nbsp;[&hellip;]

---