Stochastic Equilibria under Imprecise Deviations in Terminal-Reward Concurrent Games

Patricia Bouyer
(LSV, CNRS & ENS Cachan, Université Paris-Saclay, France)
Nicolas Markey
(LSV, CNRS & ENS Cachan, Université Paris-Saclay, France)
Daniel Stan
(LSV, CNRS & ENS Cachan, Université Paris-Saclay, France)

We study the existence of mixed-strategy equilibria in concurrent games played on graphs. While existence is guaranteed with safety objectives for each player, Nash equilibria need not exist when players are given arbitrary terminal-reward objectives, and their existence is undecidable with qualitative reachability objectives (and only three players). However, these results rely on the fact that the players can enforce infinite plays while trying to improve their payoffs. In this paper, we introduce a relaxed notion of equilibria, where deviations are imprecise. We prove that contrary to Nash equilibria, such (stationary) equilibria always exist, and we develop a PSPACE algorithm to compute one.

In Domenico Cantone and Giorgio Delzanno: Proceedings of the Seventh International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2016), Catania, Italy, 14-16 September 2016, Electronic Proceedings in Theoretical Computer Science 226, pp. 61–75.
Published: 13th September 2016.

ArXived at: http://dx.doi.org/10.4204/EPTCS.226.5 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org