DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2014-07-15 - Colloque/Présentation - communication orale - Anglais - 27 page(s)

Bruyère Véronique , Meunier Noémie , Raskin Jean-François, "Secure Equilibria in Weighted Games" in CSL-LICS, Vienne, Autriche, 2014

  • Codes CREF : Logique mathématique (DI1170), Théorie des algorithmes (DI1164), Informatique mathématique (DI1160), Informatique générale (DI1162), Théorie de la décision et des jeux (DI1134)
  • Unités de recherche UMONS : Informatique théorique (S829)
  • Instituts UMONS : Institut de Recherche en Technologies de l’Information et Sciences de l’Informatique (InforTech), Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)

Abstract(s) :

(Anglais) We consider two-player non zero-sum infinite duration games played on weighted graphs. We extend the notion of secure equilibrium introduced by Chatterjee et al., from the Boolean setting to this quantitative setting. As for the Boolean setting, our notion of secure equilibrium refines the classical notion of Nash equilibrium. We prove that secure equilibria always exist in a large class of weighted games which includes common measures like sup, inf, lim sup, lim inf, mean-payoff, and discounted sum. Moreover we show that it is possible to synthesize such strategy profiles that are finite-memory and use few memory. Finally, we prove that the constrained existence problem for secure equilibria is decidable for sup, inf, lim sup, lim inf and mean-payoff measures. Our solutions rely on new results for zero-sum quantitative games with lexicographic objectives that are interesting on their own right.