Nicolas Markey

Abstract

We study two-player timed games where the objectives of the two players are not opposite. We focus on the standard notion of Nash equilibrium and propose a series of transformations that builds two finite turn-based games out of a timed game, with a precise correspondence between Nash equilibria in the original and in final games. This provides us with an algorithm to compute Nash equilibria in two-player timed games for large classes of properties.

@inproceedings{formats2010-BBM,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas},
  title =               {Computing Equilibria in Two-Player Timed Games
                         {\textit{via}}~Turn-Based Finite Games},
  editor =              {Chatterjee, Krishnendu and Henzinger, Thomas A.},
  booktitle =           {{P}roceedings of the 8th {I}nternational
                         {C}onferences on {F}ormal {M}odelling and {A}nalysis
                         of {T}imed {S}ystems ({FORMATS}'10)},
  acronym =             {{FORMATS}'10},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6246},
  pages =               {62-76},
  year =                {2010},
  month =               sep,
  doi =                 {10.1007/978-3-642-15297-9_7},
  abstract =            {We study two-player timed games where the objectives
                         of the two players are not opposite. We focus on the
                         standard notion of Nash equilibrium and propose a
                         series of transformations that builds two finite
                         turn-based games out of a timed game, with a precise
                         correspondence between Nash equilibria in the
                         original and in final games. This provides us with
                         an algorithm to compute Nash equilibria in
                         two-player timed games for large classes of
                         properties.},
}