Nicolas Markey

Abstract

We study pure-strategy Nash equilibria in multiplayer concurrent games, for a variety of omega-regular objectives. For simple objectives (e.g. reachability, Büchi objectives), we transform the problem of deciding the existence of a Nash equilibrium in a given concurrent game into that of deciding the existence of a winning strategy in a turn-based two-player game (with a refined objective). We use that transformation to design algorithms for computing Nash equilibria, which in most cases have optimal worst-case complexity. For automata-defined objectives, we extend the above algorithms using a simulation relation which allows us to consider the product of the game with the automata defining the objectives. Building on previous algorithms for simple qualitative objectives, we define and study a semi-quantitative framework, where all players have several boolean objectives equipped with a preorder; a player may for instance want to satisfy all her objectives, or to maximise the number of objectives that she achieves. In most cases, we prove that the algorithms we obtain match the complexity of the problem they address.

@article{lmcs11(2)-BBMU,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas and Ummels, Michael},
  title =               {Pure {N}ash Equilibria in Concurrent Games},
  journal =             {Logical Methods in Computer Science},
  volume =              {11},
  number =              {2:9},
  year =                {2015},
  month =               jun,
  doi =                 {10.2168/LMCS-11(2:9)2015},
  abstract =            {We study pure-strategy Nash equilibria in
                         multiplayer concurrent games, for a variety of
                         omega-regular objectives. For simple objectives
                         (e.g. reachability, B{\"u}chi objectives), we
                         transform the problem of deciding the existence of a
                         Nash equilibrium in a given concurrent game into
                         that of deciding the existence of a winning strategy
                         in a turn-based two-player game (with a refined
                         objective). We use that transformation to design
                         algorithms for computing Nash equilibria, which in
                         most cases have optimal worst-case complexity. For
                         automata-defined objectives, we extend the above
                         algorithms using a simulation relation which allows
                         us to consider the product of the game with the
                         automata defining the objectives. Building on
                         previous algorithms for simple qualitative
                         objectives, we define and study a semi-quantitative
                         framework, where all players have several boolean
                         objectives equipped with a preorder; a player may
                         for instance want to satisfy all her objectives, or
                         to maximise the number of objectives that she
                         achieves. In most cases, we prove that the
                         algorithms we obtain match the complexity of the
                         problem they address.},
}