Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.351
URN: urn:nbn:de:0030-drops-48550
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4855/
Bouyer, Patricia ; Markey, Nicolas ; Stan, Daniel
Mixed Nash Equilibria in Concurrent Terminal-Reward Games
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{bouyer_et_al:LIPIcs:2014:4855,
author = {Patricia Bouyer and Nicolas Markey and Daniel Stan},
title = {{Mixed Nash Equilibria in Concurrent Terminal-Reward Games}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {351--363},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-77-4},
ISSN = {1868-8969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4855},
URN = {urn:nbn:de:0030-drops-48550},
doi = {10.4230/LIPIcs.FSTTCS.2014.351},
annote = {Keywords: concurrent games, randomized strategy, Nash equilibria, undecidability}
}
| Keywords: | concurrent games, randomized strategy, Nash equilibria, undecidability | |
| Seminar: | 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) | |
| Issue date: | 2014 | |
| Date of publication: | 12.12.2014 |
