Résumé | We consider concurrent games played on graphs, and we want to decide the existence of a Nash equilibrium (possibly with a condition on the payoffs). We propose a general transformation from multiplayer games to zero-sum game and use it to characterise the exact complexity of the Nash equilibrium problem for classical objectives.
We also extend the study to a more quantitative setting in which each player has several 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).
This is joint work with Patricia Bouyer, Nicolas Markey and Michael Ummels. |