Dynamics on Games: Simulation-Based Techniques and Applications to Routing - MOVE Modélisation et Vérification - LIS Laboratoire d'Informatique et Systèmes de Marseille (UMR 7020) Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Dynamics on Games: Simulation-Based Techniques and Applications to Routing

Thomas Brihaye
  • Fonction : Auteur
  • PersonId : 962991
Marion Hallet
  • Fonction : Auteur
  • PersonId : 1061247
Benjamin Monmege
Bruno Quoitin
  • Fonction : Auteur
  • PersonId : 981389

Résumé

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.
Fichier principal
Vignette du fichier
LIPIcs-FSTTCS-2019-35.pdf (502.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02414987 , version 1 (16-12-2019)

Identifiants

Citer

Thomas Brihaye, Gilles Geeraerts, Marion Hallet, Benjamin Monmege, Bruno Quoitin. Dynamics on Games: Simulation-Based Techniques and Applications to Routing. 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), Dec 2019, Bombay, India. ⟨10.4230/LIPIcs.FSTTCS.2019.35⟩. ⟨hal-02414987⟩
60 Consultations
73 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More