Nicolas Markey

Abstract

We consider concurrent games played on graphs, in which each player has several qualitative (e.g. reachability or Büchi) objectives, and a preorder on these objectives (for instance the counting order, where the aim is to maximise the number of objectives that are fulfilled).

We study two fundamental problems in that setting: (1) the value problem, which aims at deciding the existence of a strategy that ensures a given payoff; (2) the Nash equilibrium problem, where we want to decide the existence of a Nash equilibrium (possibly with a condition on the payoffs). We characterise the exact complexities of these problems for several relevant preorders, and several kinds of objectives.

@inproceedings{fossacs2012-BBMU,
  author =              {Bouyer, Patricia and Brenguier, Romain and Markey,
                         Nicolas and Ummels, Michael},
  title =               {Concurrent games with ordered objectives},
  editor =              {Birkedal, Lars},
  booktitle =           {{P}roceedings of the 15th {I}nternational
                         {C}onference on {F}oundations of {S}oftware
                         {S}cience and {C}omputation {S}tructure
                         ({FoSSaCS}'12)},
  acronym =             {{FoSSaCS}'12},
  publisher =           {Springer-Verlag},
  series =              {Lecture Notes in Computer Science},
  volume =              {7213},
  pages =               {301-315},
  year =                {2012},
  month =               mar,
  doi =                 {10.1007/978-3-642-28729-9_20},
  abstract =            {We consider concurrent games played on graphs, in
                         which each player has several qualitative (e.g.
                         reachability or B{\"u}chi) objectives, and a
                         preorder on these objectives (for instance the
                         counting order, where the aim is to maximise the
                         number of objectives that are fulfilled).\par We
                         study two fundamental problems in that setting:
                         (1)~the \emph{value problem}, which aims at deciding
                         the existence of a strategy that ensures a given
                         payoff; (2)~the \emph{Nash equilibrium problem},
                         where we want to decide the existence of a Nash
                         equilibrium (possibly with a condition on the
                         payoffs). We characterise the exact complexities of
                         these problems for several relevant preorders, and
                         several kinds of objectives.},
}