Todos os Eventos

"Dynamics and complexity of the Schelling’s segregation model"

Eric Goles

UAI, Santiago

Instituto de Sistemas Complejos, Valparaiso, Chil

Thomas Schelling won the Nobel prize in Economics, 2005, with Robert Aumann, “ for having enhanced our understanding of conflict and cooperation through game-theory analysis” . In 1969 Schelling published a seminal article called "Models of Segregation". In that paper he showed that a small preference for one's neighbors to be of the same color could lead to total segregation In mathematical terms, Schelling’ s segregation model consists in a lattice such that each site is in one of two states (say x = –1 or +1). A site at state x is “ unhappy” if there are more than a specific critical number of neighbors in the opposite state –x. The dynamics consists to exchange at random a couple of unhappy sites in opposte states. I will study this model for different Critical thresholds, dimensions and neigborhoods. I will prove that for some threshold the model is driven by an energy like spin glassses and from the computational complexity point of view I will classify the different dynamics accordingly if one may or not find shortcut algorithms to know if a specific site will or

will not change its state.