Publications

2010

• J. Olschewski and M. Ummels. The Complexity of Finding Reset Words in Finite Automata. In Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010, vol. 6281 of LNCS, pp. 568–579. Springer, 2010.                                 
  Abstract   BibTeX

  We study several problems related to finding reset words in deterministic finite automata. In particular, we establish that the problem of deciding whether a shortest reset word has length k is complete for the complexity class DP. This result answers a question posed by Volkov. For the search problems of finding a shortest reset word and the length of a shortest reset word, we establish membership in the complexity classes FP^NP and FP^NP[log], respectively. Moreover, we show that both these problems are hard for FP^NP[log]. Finally, we observe that computing a reset word of a given length is FNP-complete.

  @inproceedings{OU10,
       author = {J{\"o}rg Olschewski and Michael Ummels},
       booktitle = {{Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010}},
       pages = {568--579},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{The Complexity of Finding Reset Words in Finite Automata}},
       url = {http://www.logic.rwth-aachen.de/~ummels/mfcs10.pdf},
       volume = {6281},
       year = {2010},
  }
  

• M. Ummels. Stochastic Multiplayer Games: Theory and Algorithms. PhD thesis, RWTH Aachen University, 2010.                                 
  Abstract   BibTeX

  Stochastic games provide a versatile model for reactive systems that are affected by random events. This dissertation advances the algorithmic thery of stochastic games to incorporate multiple players, whose objectives are not ecessarily conflicting. The basis of this work is a comprehensive complexity-theoretic analysis of the standard game-theoretic solution concepts in the context of stochastic games over a finite state space. One main result is that the constrained existence of a Nash equilibrium becomes undecidable in this setting. This impossibility result is accompanied by several positive results, including efficient algorithms for natural special cases.

  @phdthesis{Ummels10,
       author = {Michael Ummels},
       school = {{RWTH} Aachen University},
       title = {{Stochastic Multiplayer Games: Theory and Algorithms}},
       url = {http://www.logic.rwth-aachen.de/~ummels/diss.pdf},
       year = {2010},
  }
  

2009

• W. Thomas, K. Bollue, D. Gueckel, G. Quiros, M. Slaats, and M. Ummels. DFG Research Training Group “Algorithmic Synthesis of Reactive and Discrete-Continuous Systems (AlgoSyn)”. it – Information Technology, vol. 51(4), 2009.                                 
  Abstract   BibTeX

  While methods of software validation and verification are by now well established, the approach of automatic synthesis of software (and hardware) is as yet only developed in quite rudimentary form. Algorithmic program synthesis is possible in restricted scenarios, in particular in reactive multi-agent systems with low data complexity and in control systems. Central issues are the establishment of system models that support algorithmic solutions, the combination of discrete and continuous parameters (in hybrid systems), and the exploration of applications. The aim of the Research Training Group AlgoSyn is to unify the expertise from computer science, mathematics, and four engineering disciplines (processor architectures, automatic control, process control engineering, train traffic systems), in order to push forward the desired integration of methods.

  @article{TBGQSU09,
       author = {Wolfgang Thomas and Kai Bollue and Dominique Gueckel and Gustavo Quiros and Michaela Slaats and Michael Ummels},
       journal = {it -- Information Technology},
       number = {4},
       title = {{DFG} Research Training Group ``Algorithmic Synthesis of Reactive and Discrete-Continuous Systems ({AlgoSyn})''},
       url = {http://www.atypon-link.com/OLD/doi/pdf/10.1524/itit.2009.0545},
       volume = {51},
       year = {2009},
  }
  

• M. Ummels and D. Wojtczak. Decision Problems for Nash Equilibria in Stochastic Games. In Proceedings of the 18th Annual Conference of the European Association for Computer Science Logic, CSL '09 (E. Grädel and R. Kahle, Eds.), vol. 5771 of LNCS, pp. 515–530. Springer, 2009.                                 
  Abstract   BibTeX

  We analyse the computational complexity of finding Nash equilibria in stochastic multiplayer games with $\omega$-regular objectives. While the existence of an equilibrium whose payoff falls into a certain interval may be undecidable, we single out several decidable restrictions of the problem. First, restricting the search space to stationary, or pure stationary, equilibria results in problems that are typically contained in PSPACE and NP, respectively. Second, we show that the existence of an equilibrium with a binary payoff (i.e. an equilibrium where each player either wins or loses with probability 1) is decidable. We also establish that the existence of a Nash equilibrium with a certain binary payoff entails the existence of an equilibrium with the same payoff in pure, finite-state strategies.

  @inproceedings{UW09a,
       author = {Michael Ummels and Dominik Wojtczak},
       booktitle = {{Proceedings of the 18th Annual Conference of the European Association for Computer Science Logic, CSL~'09}},
       editor = {Erich Gr{\"a}del and Reinhard Kahle},
       pages = {515--530},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {Decision Problems for {N}ash Equilibria in Stochastic Games},
       url = {http://www.logic.rwth-aachen.de/~ummels/csl09.pdf},
       volume = {5771},
       year = {2009},
  }
  

• M. Ummels and D. Wojtczak. The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 (S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. Nikoletseas, and W. Thomas, Eds.), vol. 5556 of LNCS, pp. 297–308. Springer, 2009.                                 
  Abstract   BibTeX

  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 fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game G, does there exist a pure-strategy Nash equilibrium of G where player 0 wins with probability 1. Moreover, this problem remains undecidable if it is restricted to strategies with (unbounded) finite memory. However, if mixed strategies are allowed, decidability remains an open problem. One way to obtain a provably decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSPACE respectively.

  @inproceedings{UW09,
       author = {Michael Ummels and Dominik Wojtczak},
       booktitle = {{Proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP~2009}},
       editor = {Susanne Albers and Alberto Marchetti-Spaccamela and Yossi Matias and Sotiris Nikoletseas and Wolfgang Thomas},
       pages = {297--308},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {The Complexity of {N}ash Equilibria in Simple Stochastic Multiplayer Games},
       url = {http://www.logic.rwth-aachen.de/~ummels/icalp09.pdf},
       volume = {5556},
       year = {2009},
  }
  

2008

• E. Grädel and M. Ummels. Solution Concepts and Algorithms for Infinite Multiplayer Games. In New Perspectives on Games and Interaction (K. Apt and R. van Rooij, Eds.), vol. 4 of Texts in Logic and Games, pp. 151–178. Amsterdam University Press, 2008.                                 
  Abstract   BibTeX

  We survey and discuss several solution concepts for infinite turn-based multiplayer games with qualitative (i.e. win-lose) objectives of the players. These games generalise in a natural way the common model of games in verification which are two-player, zero-sum games with $\omega$-regular winning conditions. The generalisation is in two directions: our games may have more than two players, and the objectives of the players need not be completely antagonistic. The notion of a Nash equilibrium is the classical solution concept in game theory. However, for games that extend over time, in particular for games of infinite duration, Nash equilibria are not always satisfactory as a notion of rational behaviour. We therefore discuss variants of Nash equilibria such as subgame perfect equilibria and secure equilibria. We present criteria for the existence of Nash equilibria and subgame perfect equilibria in the case of arbitrary many players and for the existence of secure equilibria in the two-player case. In the second part of this paper, we turn to algorithmic questions: For each of the solution concepts that we discuss, we present algorithms that decide the existence of a solution with certain requirements in a game with parity winning conditions. Since arbitrary $\omega$-regular winning conditions can be reduced to parity conditions, our algorithms are also applicable to games with arbitrary $\omega$-regular winning conditions.

  @inproceedings{GU08,
       author = {Erich Gr{\"a}del and Michael Ummels},
       booktitle = {{New Perspectives on Games and Interaction}},
       editor = {Krzysztof Apt and Robert van Rooij},
       pages = {151--178},
       publisher = {Amsterdam University Press},
       series = {{Texts in Logic and Games}},
       title = {{Solution Concepts and Algorithms for Infinite Multiplayer Games}},
       url = {http://www.logic.rwth-aachen.de/~ummels/knaw07.pdf},
       volume = {4},
       year = {2008},
  }
  

• M. Ummels. The Complexity of Nash Equilibria in Infinite Multiplayer Games. In Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2008 (R. Amadio, Ed.), vol. 4962 of LNCS, pp. 20–34. Springer, 2008.                                 
  Abstract   BibTeX

  We study the complexity of Nash equilibria in infinite (turn-based, qualitative) multiplayer games. Chatterjee et al. showed the existence of a Nash equilibrium in any such game with $\omega$-regular winning conditions, and they devised an algorithm for computing one. We argue that in applications it is often insufficient to compute just some Nash equilibrium. Instead, we enrich the problem by allowing to put (qualitative) constraints on the payoff of the desired equilibrium. Our main result is that the resulting decision problem is NP-complete for games with co-Büchi, parity or Streett winning conditions but fixed-parameter tractable for many natural restricted classes of games with parity winning conditions. For games with Büchi winning conditions we show that the problem is, in fact, decidable in polynomial time. We also analyse the complexity of strategies realising a Nash equilibrium. In particular, we show that pure finite-state strategies as opposed to arbitrary mixed strategies suffice to realise any Nash equilibrium of a game with $\omega$-regular winning conditions with a qualitative constraint on the payoff.

  @inproceedings{Ummels08,
       author = {Michael Ummels},
       booktitle = {{Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures, FOSSACS~2008}},
       editor = {Roberto Amadio},
       pages = {20--34},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {The Complexity of {N}ash Equilibria in Infinite Multiplayer Games},
       url = {http://www.logic.rwth-aachen.de/~ummels/fossacs08.pdf},
       volume = {4962},
       year = {2008},
  }
  

2006

• M. Ummels. Rational Behaviour and Strategy Construction in Infinite Multiplayer Games. In Proceedings of the 26th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006 (S. Arun-Kumar and N. Garg, Eds.), vol. 4337 of LNCS, pp. 212–223. Springer, 2006.                                 
  Abstract   BibTeX

  We study infinite games played by arbitrarily many players on a directed graph. Equilibrium states capture rational behaviour in these games. Instead of the well-known notion of a Nash equilibrium, we focus on the notion of a subgame perfect equilibrium. We argue that the latter one is more appropriate for the kind of games we study, and we show the existence of a subgame perfect equilibrium in any infinite game with $\omega$-regular winning conditions. As, in general, equilibria are not unique, it is appealing to compute one with a maximal payoff. This problem corresponds naturally to the problem of deciding given a game and two payoff vectors whether the game has an equilibrium with a payoff in between the given thresholds. We show that this problem is decidable for games with $\omega$-regular winning conditions played on a finite graph and analyse its complexity. Moreover, we establish that any subgame perfect equilibrium of a game with $\omega$-regular winning conditions played on a finite graph can be implemented by finite-state strategies. Finally, we consider logical definability. We state that if we fix the number of players together with an $\omega$-regular winning condition for each of them and two payoff vectors the property that a game has a subgame perfect equilibrium with a payoff in between the given thresholds is definable in the modal $\mu$-calculus.

  @inproceedings{Ummels06,
       author = {Michael Ummels},
       booktitle = {{Proceedings of the 26th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2006}},
       editor = {S. Arun-Kumar and Naveen Garg},
       pages = {212--223},
       publisher = {{Springer}},
       series = {{LNCS}},
       title = {{Rational Behaviour and Strategy Construction in Infinite Multiplayer Games}},
       url = {http://www.logic.rwth-aachen.de/~ummels/fsttcs06.pdf},
       volume = {4337},
       year = {2006},
  }
  

2005

• M. Ummels. Rational Behaviour and Strategy Construction in Infinite Multiplayer Games. Diploma thesis, RWTH Aachen, 2005.             
  BibTeX

  @misc{Ummels05,
       author = {Michael Ummels},
       howpublished = {{Diploma thesis, RWTH Aachen}},
       title = {{Rational Behaviour and Strategy Construction in Infinite Multiplayer Games}},
       url = {http://www.logic.rwth-aachen.de/~ummels/diplom.pdf},
       year = {2005},
  }