Nicolas Markey

Abstract

We study the problem of the existence (and computation) of Nash equilibria in multi-player concurrent games with Büchi-definable objectives. First, when the objectives are Büchi conditions on the game, we prove that the existence problem can be solved in polynomial time. In a second part, we extend our technique to objectives defined by deterministic Büchi automata, and prove that the problem then becomes EXPTIME-complete. We prove PSPACE-completeness for the case where the Büchi automata are 1-weak.

@inproceedings{fsttcs2011-BBMU,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas and Ummels, Michael},
  title =               {{N}ash Equilibria in Concurrent Games with
                         {B}{\"u}chi Objectives},
  editor =              {Chakraborty, Supratik and Kumar, Amit},
  booktitle =           {{P}roceedings of the 31st {C}onference on
                         {F}oundations of {S}oftware {T}echnology and
                         {T}heoretical {C}omputer {S}cience ({FSTTCS}'11)},
  acronym =             {{FSTTCS}'11},
  publisher =           {Leibniz-Zentrum f{\"u}r Informatik},
  series =              {Leibniz International Proceedings in Informatics},
  volume =              {13},
  pages =               {375-386},
  year =                {2011},
  month =               dec,
  doi =                 {10.4230/LIPIcs.FSTTCS.2011.375},
  abstract =            {We study the problem of the existence (and
                         computation) of Nash equilibria in multi-player
                         concurrent games with B{\"u}chi-definable
                         objectives. First, when the objectives are B{\"u}chi
                         conditions on the game, we prove that the existence
                         problem can be solved in polynomial time. In a
                         second part, we extend our technique to objectives
                         defined by deterministic B{\"u}chi automata, and
                         prove that the problem then becomes
                         EXPTIME-complete. We prove PSPACE-completeness for
                         the case where the B{\"u}chi automata are 1-weak.},
}