Publikationen

Noch nicht erschienen

• 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. 5 of Texts in Logic and Games. Amsterdam University Press. To appear.                                 
  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ädel and Michael Ummels},
       title = {Solution Concepts and Algorithms for Infinite Multiplayer Games},
       booktitle = {New Perspectives on Games and Interaction},
       editor = {Krzysztof Apt and Robert van Rooij},
       series = {Texts in Logic and Games},
       volume = {5},
       publisher = {Amsterdam University Press},
       url = {http://www.logic.rwth-aachen.de/~ummels/knaw07.pdf},
       note = {To appear},
  }
  

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-Verlag, 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},
       title = {The Complexity of Nash Equilibria in Infinite Multiplayer Games},
       booktitle = {Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2008},
       editor = {Roberto Amadio},
       publisher = {Springer-Verlag},
       series = {LNCS},
       volume = {4962},
       pages = {20–34},
       year = {2008},
       url = {http://www.logic.rwth-aachen.de/~ummels/fossacs08.pdf},
  }
  

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

2005

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

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