Diffusion d’information sur un graphe planaire

De Ensiwiki
Aller à : navigation, rechercher


Diffusion d’information sur un graphe planaire

Labo LIG / INRIA
Equipe MESCAL
Encadrants corinne.touati@inria.fr,yann.blanchi@bmoffice.fr

Thème général: Systèmes dynamiques, théorie des jeux

Compétences attendues: Bon niveau en algorithmique et programmation.

Contexte

Ce travail s’inscrit dans une collaboration avec un cabinet d’architecture. L’objet d’étude est celui de matériaux (gonflables) dont la forme évolue dynamiquement en fonction d’interactions diverses avec l’humain (interface multi-sensorielle). Dans le cadre des matériaux déformables, l’évolution peut être causée par des modifications pilotées de la pression à divers endroits (« cellules ») du matériau.

Sujet

Dans ce stage, nous nous intéressons à créer un simulateur de ce réseau de « cellules ». Le système est donc modélisé par un graphe d’interaction dont chaque noeud représente une « cellule ». Chaque cellule possède un état (typiquement un réel entre 0 et 1) et l’interaction humaine peut provoquer un changement de cet état. Dans l’application finale, l’état peut être la pression associée à la « cellule ».

Chaque «  cellule » peut être interprétée comme un joueur (au sens de la théorie des jeux) dont la stratégie dépend de celle des joueurs avec qui il interagit (ici, ses voisins dans le graphe d’interaction). Comme dans le cadre de la théorie des jeux révolutionnaire, on s’intéressera à la dynamique d’évolution des états des joueurs ainsi que leur convergence éventuelle (le système pouvant éventuellement converger vers un état stationnaire ou vers un cycle.

On s’appliquera également à développer un simulateur avec interface graphique, permettant de visualiser le graphe d’interactions, de simuler quelques interactions humaines élémentaires et de visualiser l’évolution dynamique des états des noeuds (par exemple en niveaux de gris).


Références

Quelques articles de théorie des jeux sur des graphes:

« Optimal design and defense of networks under link attacks », C Bravard, L Charroin, C Touati, Journal of Mathematical Economics num 68, pp 62-79, 2017

«  A simple rule for the evolution of cooperation on graphs », H. Ohtsuki, C. Hauert, E. Lieberman, M. Nowak, Nature, 502-505, 2006.