Nicolas Markey

Résumé

We study nondeterministic strategies in parity games with the aim of computing a most permissive winning strategy. Following earlier work, we measure permissiveness in terms of the average number/weight of transitions blocked by a strategy. Using a translation into mean-payoff parity games, we prove that deciding (the permissiveness of) a most permissive winning strategy is in NP∩coNP. Along the way, we provide a new study of mean-payoff parity games. In particular, we give a new algorithm for solving these games, which beats all previously known algorithms for this problem.

@inproceedings{atva2011-BMOU,
  author =              {Bouyer, Patricia and Markey, Nicolas and Olschewski,
                         J{\"o}rg and Ummels, Michael},
  title =               {Measuring Permissiveness in Parity Games:
                         Mean-Payoff Parity Games Revisited},
  editor =              {Bultan, Tevfik and Hsiung, Pao-Ann},
  booktitle =           {{P}roceedings of the 9th {I}nternational {S}ymposium
                         on {A}utomated {T}echnology for {V}erification and
                         {A}nalysis ({ATVA}'11)},
  acronym =             {{ATVA}'11},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {6996},
  pages =               {135-149},
  year =                {2011},
  month =               oct,
  doi =                 {10.1007/978-3-642-24372-1_11},
  abstract =            {We study nondeterministic strategies in parity games
                         with the aim of computing a most permissive winning
                         strategy. Following earlier work, we measure
                         permissiveness in terms of the average
                         number{\slash}weight of transitions blocked by a
                         strategy. Using a translation into mean-payoff
                         parity games, we prove that deciding (the
                         permissiveness~of) a~most permissive winning
                         strategy is in \(\textsf{NP}\cap\textsf{coNP}\).
                         Along the way, we~provide a new study of mean-payoff
                         parity games. In particular, we give a new algorithm
                         for solving these games, which beats all previously
                         known algorithms for this problem.},
}