Digital Morphogenesis via Schelling segregation

Title: Digital Morphogenesis via Schelling segregation

Speaker: Georgios Barmpalias (SKLCS, Inst. of Software, CAS)

Time: 14:00, Thursday, 28 February, 2013

Venue: Lecture Room, 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Thomas Schelling, a nobel prize economist (mostly known for his game-theoretic arguments regarding nuclear proliferation) suggested a simple model for residential segregation in the late 1960s. The model is a number of individuals that have one of two colours, situated on a line (1D model) or a grid (2D model). The initial colouring is random, while during a series of steps individuals can move to different locations according to certain rules. An individual is considered “happy” if there are many individuals of the same color in its neighbourhood (and “unhappy” otherwise). Unhappy individuals are chosen randomly at each step and they move to a location where they can be happy. This amounts to a stochastic process which leads to a final configuration, starting from a random one. The challenge is to predict the form of the final configuration, given the initial parameters (size of neighbourhood and happiness requirement).

Despite a lot of attention that this model has received (it has been studied experimentally, e.g. via computer simulations) it has resisted a theoretical analysis, mainly because of the lack of stationary distributions of the associated stochastic processes. In a paper in STOC 2012, Brandt, Immorlica, Kamath and Kleinberg provided the first mathematical analysis for the 1D model, where the happiness requirement is “at least 50% of the same colour in the neighbourhood”. Their result is that in this case the expected length of the monochromatic blocks is polynomial in the radius of the neighbourhood. Recently, Elwes, Lewis and myself wrote a paper providing an analysis for every possible happiness percentage. These results reveal surprising phase transitions and concrete examples where increased tolerance (i.e. lower happiness requirement) leads to increased segregation. Along with the mathematical analysis, we produced computer simulations (images and animations) which clearly demonstrate the theoretical results.

In this talk I would like to review these recent developments and show you images and animations (produced with C++ and OpenGL graphics, see

attachment) that help understand the process and illustrate our mathematical results. I will also describe the methods that we used to get a full characterisation of the eventual behaviour of this stochastic process. I am also hoping to get some feedback from the people who work on similar topics, or even from colleagues that work in graphics (regarding the simulations).

This talk will be accessible to a general audience. In a later talk (not scheduled yet) I hope to get into the more technical aspect of this work.

Georgios Barmpalias is a CAS visiting young scientist at the State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of

Sciences. More information about him can be found at http://www.barmpalias.net .