Nicolas Markey

Résumé

In this paper, we extend the classical notion of strategies in turn-based finite games by allowing several moves to be selected. We define and study a quantitative measure for permissivity of such strategies by assigning penalties when blocking transitions. We prove that for reachability objectives, most permissive strategies exist, can be chosen memoryless, and can be computed in polynomial time, while it is in NP∩coNP for discounted and mean penalties.

@inproceedings{concur2009-BDMR,
  author =              {Bouyer, Patricia and Duflot, Marie and Markey,
                         Nicolas and Renault, Gabriel},
  title =               {Measuring Permissivity in Finite Games},
  editor =              {Bravetti, Mario and Zavattaro, Gianluigi},
  booktitle =           {{P}roceedings of the 20th {I}nternational
                         {C}onference on {C}oncurrency {T}heory
                         ({CONCUR}'09)},
  acronym =             {{CONCUR}'09},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {5710},
  pages =               {196-210},
  year =                {2009},
  month =               sep,
  doi =                 {10.1007/978-3-642-04081-8_14},
  abstract =            {In this paper, we extend the classical notion of
                         strategies in turn-based finite games by allowing
                         several moves to be selected. We~define and study a
                         quantitative measure for permissivity of such
                         strategies by assigning penalties when blocking
                         transitions. We~prove that for reachability
                         objectives, most permissive strategies exist, can be
                         chosen memoryless, and can be computed in polynomial
                         time, while it is in
                         \(\textsf{NP}\cap\textsf{coNP}\) for discounted and
                         mean penalties.},
}