Nicolas Markey

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.

@inproceedings{fsttcs2014-BMS,
  author =              {Bouyer, Patricia and Markey, Nicolas and Stan,
                         Daniel},
  title =               {Mixed {N}ash Equilibria in Concurrent Games},
  editor =              {Raman, Venkatesh and Suresh, S. P.},
  booktitle =           {{P}roceedings of the 34th {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'14)},
  acronym =             {{FSTTCS}'14},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {29},
  pages =               {351-363},
  year =                {2014},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2014.351},
  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.},
}