2026-07-22T13:16:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4855 2024-03-06T10:35:26Z ddc:004 open_access

Mixed Nash Equilibria in Concurrent Terminal-Reward Games Bouyer, Patricia Markey, Nicolas Stan, Daniel concurrent games randomized strategy Nash equilibria undecidability We study mixed-strategy Nash equilibria in multiplayer deterministic concurrent games played on graphs, with terminal-reward payoffs (that is, absorbing states with a value for each player). We show undecidability of the existence of a constrained Nash equilibrium (the constraint requiring that one player should have maximal payoff), with only three players and 0/1-rewards (i.e., reachability objectives). This has to be compared with the undecidability result by Ummels and Wojtczak for turn-based games which requires 14 players and general rewards. Our proof has various interesting consequences: (i) the undecidability of the existence of a Nash equilibrium with a constraint on the social welfare; (ii) the undecidability of the existence of an (unconstrained) Nash equilibrium in concurrent games with terminal-reward payoffs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Patricia Bouyer and Nicolas Markey and Daniel Stan 2014 Is Part Of LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2014.351 urn:nbn:de:0030-drops-48550 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.351 eng https://creativecommons.org/licenses/by/3.0/legalcode