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

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2019-12-11 - Colloque/Article dans les actes avec comité de lecture - Anglais - 14 page(s)

Brihaye Thomas , Geeraerts Gilles, Hallet Marion , Monmege Benjamin, Quoitin Bruno , "Dynamics on Games: Simulation-Based Techniques and Applications to Routing" in Foundations of Software Technology and Theoretical Computer Science

  • Codes CREF : Théorie de la décision et des jeux (DI1134)
  • Unités de recherche UMONS : Mathématiques effectives (S820), Réseaux et Télécommunications (S802)
  • Instituts UMONS : Institut de Recherche sur les Systèmes Complexes (Complexys)
  • Centres UMONS : Modélisation mathématique et informatique (CREMMI)

Abstract(s) :

(Anglais) We consider multi-player games played on graphs, in which the players aim at fulfilling their own (not necessarily antagonistic) objectives. In the spirit of evolutionary game theory, we suppose that the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome w.r.t. the current strategy profile). This generates a dynamics in the game which may eventually stabilise to an equilibrium. The objective of the present paper is twofold. First, we aim at drawing a general framework to reason about the termination of such dynamics. In particular, we identify preorders on games (inspired from the classical notion of simulation between transitions systems, and from the notion of graph minor) which preserve termination of dynamics. Second, we show the applicability of the previously developed framework to interdomain routing problems.