Attention : je reçois plusieurs demandes de stages par jour, et je me vois donc dans l'obligation de faire une sélection en amont : inutile de me contacter si vous n'avez pas eu une moyenne >14/20 l'an passé, et des notes similaires pour votre premier semestre de master 2.
En 1971, dans le Journal of Mathematical Sociology, il publie "Dynamic Models of Segregation." Il s'agit d'un article fameux qui traite de la dynamique du partage de l'espace entre les « races ». Il présente en fait un modèle mathétique fort simple, mais non trivial à analyser : il s'agit de variantes d'automate cellulaire (cf. jeu de la vie de Conway), de modèle d'interaction proies/prédateurs, de modèles de chaînes de Markov, etc.
Il existe de très nombreuses études expérimentales sur ce modèle. Ce stage a pour but d'enfin établir des résultats rigoureux, en s'appuyant sur la théorie des automates, couplée aux séries génératrices.
On considère une grille n x m, avec des case coloriée initialement en noir ou blanc. Chaque case de la grille évolue en fonction de la couleur de ses voisins, puis on peut faire une certaine permutation.
En jouant sur les paramètres, on obtient donc des variantes du modèle initial de Schelling.
On étudiera dans ce stage, initialement par le biais d'expérimentations, la stabilité de ces modèles (sur diverses familles de configurations initiales). On tentera ensuite de prouver mathématiquement certaines des observations faites (distribution stationnaire des chaînes de Markov associées, etc). On regardera la pertinence ici de notion de type équilibre de Nash et optimum de Pareto. On fera le point sur les approches multi-agents existantes.
On réfléchira aussi sur la décidabilité des questions suivantes :
Majorité : après un temps infini, noir est-il majoritaire ?
Eden : étant donné telle configuration, est-elle accessible ?
Périodicité : l'évolution devient-elle périodique ?
On essayera aussi de trouver de larges classes de modèles/configurations initiales pour lesquelles on peut répondre aux questions suivantes :
Durée de vie : combien d'étapes avant le régime périodique ?
Quelle est le ratio de cases blanches ?
Quelle est la longueur de la période ?
Quelle est le taux de migration (le déplacement total) ?
Quels algorithmes peut-on utiliser
pour ces questions de décidabilité et de quantification ?
Quand peut-on faire mieux que de simplement simuler
toute l'histoire d'une configuration ?
Peut-on analyser (à la façon de Knuth dans The Art of Computer
Programming), la complexité de ces algorithmes (et donc éventuellement
les améliorer) ?
Références :
T. Schelling
Jeu de la vie
Proie
Chaîne de Markov
Modèle de Schelling
approche muli-agents
Kedama
Comparaison de trois implémentations du
modèle de Schelling (Daudé & Langlois) [.pdf]
La
ségrégation spatiale selon Schelling : la perversité est
ailleurs [.pdf]
The Dynamics of Schelling-Type Segregation Models and a Nonlinear
Graph Laplacian Variational Problem [.pdf]
Computing
the Complexity for Schelling Segregation Models [.pdf]