2016/09/12 by Patricia Bouyer, Nicolas Markey, Daniel Stan · 4 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Best response #Combinatorics #Computer science #Decidability #Discrete mathematics #Epsilon-equilibrium #Game Theory and Applications #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge #Mathematical economics #Mathematical optimization #Mathematics #Nash equilibrium #Reachability #Terminal (telecommunication) #Undecidable problem #cs.GT
paper · pdf · doi:10.4204/eptcs.226.5
published in Electronic Proceedings in Theoretical Computer Science 226, 61-75 (Open Publishing Association) · In Proceedings GandALF 2016, arXiv:1609.03648
openalex publication_date 2016/09/12 · arxiv created 2016/09/14 · arxiv updated 2016/09/15 · openalex created_date 2016/09/23 · openalex updated_date 2026/08/05
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.