New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Competition between collective and individual dynamics

Edited by H. Eugene Stanley, Boston University, Boston, MA, and approved October 19, 2009 (received for review June 10, 2009)
Abstract
Linking microscopic and macroscopic behavior is at the heart of many natural and social sciences. This apparent similarity conceals essential differences across disciplines: Although physical particles are assumed to optimize the global energy, economic agents maximize their own utility. Here, we solve exactly a Schellinglike segregation model, which interpolates continuously between cooperative and individual dynamics. We show that increasing the degree of cooperativity induces a qualitative transition from a segregated phase of low utility toward a mixed phase of high utility. By introducing a simple function that links the individual and global levels, we pave the way to a rigorous approach of a wide class of systems, where dynamics are governed by individual strategies.
The intricate relations between the individual and collective levels are at the heart of many natural and social sciences. Different disciplines wonder how atoms combine to form solids (1, 2), neurons give rise to consciousness (3, 4), or individuals shape societies (5, 6). However, scientific fields assume distinct points of view for defining the “normal”, or “equilibrium”, aggregated state. Physics looks at the collective level, selecting the configurations that minimize the global free energy (2). In contrast, economic agents behave in a selfish way, and equilibrium is attained when no agent can increase its own satisfaction (7). Although similar at first sight, the two approaches lead to radically different outcomes.
In this paper, we illustrate the differences between collective and individual dynamics on an exactly solvable model similar to Schelling's segregation model (8). The model considers individual agents that prefer a mixed environment, with dynamics that lead to segregated or mixed patterns at the global level. A “tax” parameter monitors continuously the agents' degree of altruism or cooperativity, i.e., their consideration of the global welfare. At high degrees of cooperativity, the system is in a mixed phase of maximal utility. As the altruism parameter is decreased, a phase transition occurs, leading to segregation. In this phase, the agents' utilities remain low, in spite of continuous efforts to maximize their satisfaction. This paradoxical result of Schelling's segregation model (8) has generated an abundant literature. Many papers have simulated how the global state depends on specific individual utility functions, as reviewed by ref. 9. There have been attempts at solving Schelling's model analytically, in order to provide more general results (10, 11). However, these approaches are limited to specific utility functions. More recently, physicists have tried to use a statistical physics approach to understand the segregation transition (12 –14). The idea seems promising because statistical physics has successfully bridged the micro–macro gap for physical systems governed by collective dynamics. However, progress was slowed by lack of an appropriate framework allowing for individual dynamics (12). In this paper, we introduce a rigorous generalization of the physicist's free energy, which includes individual dynamics. By introducing a “link” state function that is maximized in the stationary state, we pave the way to analytical treatments of a much wider class of systems where dynamics are governed by individual strategies. Applied to the above Schellinglike segregation model, this approach offers a quantitative solution for very general utility functions.
Model
Our model represents in a schematic way the dynamics of residential moves in a city. For simplicity, we include one type of agent, but our results can readily be generalized to deal with agents of two “colors,” as in the original Schelling model (8) (see Discussion and SI Appendix). The city is divided into Q blocks (Q ≫ 1), each block containing H cells or flats (Fig. 1). We assume that each cell can contain at most one agent, so that the number n _{q} of agents in a given block q (q = 1,…,Q) satisfies n _{q} ≤ H, and we introduce the density of agents ρ_{q} = n _{q}/H. Each agent has the same utility function u(ρ_{q}), which describes the degree of satisfaction concerning the density of the block in which he is living. The collective utility is defined as the total utility of all the agents in the city: U(x) = H∑_{q}ρ_{q} u(ρ_{q}), where x ≡ {ρ_{q}} corresponds to the coarsegrained configuration of the city, i.e., the knowledge of the density of each block. For a given x, there is a large number of ways to arrange the agents in the different cells. This number of arrangements is quantified by its logarithm S(x), called the entropy of the configuration x.
The dynamical rule allowing the agents to move from one block to another is the following. At each time step, one picks up at random an agent and a vacant cell. Then the agent moves in that empty cell with probability where x and y are respectively the configurations before and after the move, and G is the gain associated to the proposed move. The positive parameter T is a “temperature” that introduces in a standard way (15) some noise on the decision process. It can be interpreted as the effect of features that are not explicitly included in the utility function but still affect the moving decision (urban facilities, friends, etc.). We write the gain G as where Δu is the variation of the agent's own utility upon moving and ΔU is the variation of the total utility of all agents. The parameter 0 ≤ α ≤ 1 weights the contribution of the other agents' utility variation in the calculation of the gain G, and it can thus be interpreted as a degree of cooperativity (or altruism). For α = 0, the probability to move only depends on the selfish interest of the chosen agent, which corresponds to the spirit of economic models such as Schelling's. When α = 1, the decision to move only depends on the collective utility change, as in physics models. An economical interpretation could be that individual moves are controlled by a central government, via a tax that internalizes all the externalities (more on this in Discussion). Varying α in a continuous way, one can interpolate between the two limiting behaviors of individual and collective dynamics.
Results
We wish to find the stationary probability distribution Π(x) of the microscopic configurations x. If the gain G can be written as G = ΔV ≡ V(y) − V(x), where V(x) is a function of the configuration x, then the dynamics satisfy the detailed balance (16), and the distribution Π(x) is given by with F(x) = V(x) + TS(x) and Z a normalization constant. The entropy has for large H the standard expression S(x) = H∑_{q} s(ρ_{q}), with We now need to find the function V(x), if it exists. Given the form in Eq. 2 of G, finding such a function V(x) amounts to finding a “link” function L(x), connecting the individual and collective levels, such that Δu = ΔL. The function V would thus be given by V(x) = (1 − α)L(x) + αU(x). By analogy to the entropy, we assume that L(x) can be written as a sum over the blocks, namely L(x) = H∑_{q}ℓ(ρ_{q}). Considering a move from a block at density ρ_{1} to a block at density ρ_{2}, ΔL reduces in the large H limit to ℓ′(ρ_{2}) − ℓ′(ρ_{1}), where ℓ′ is the derivative of ℓ. The condition Δu = ΔL then leads to the identification ℓ′(ρ) = u(ρ), from which the expression of ℓ(ρ) follows: As a result, the function F(x) can be expressed in the large H limit as F(x) = H∑_{q} f(ρ_{q}), with a block potential f(ρ) given by
The probability Π(x) is dominated by the configurations x = {ρ_{q}} that maximize the sum ∑_{q} f(ρ_{q}) under the constraint of a fixed ρ_{0} = Q ^{−1}∑_{q = 1} ^{Q} ρ_{q}. To perform this maximization procedure, we follow standard physics methods used in the study of phase transitions [like liquid–vapor coexistence (18)], which can be summarized as follows. If f(ρ) coincides with its concave hull at a given density ρ_{0}, then the state of the city is homogeneous, and all blocks have a density ρ_{0}. Otherwise, a phase separation occurs: Some blocks have a density ρ_{1} * < ρ_{0}, whereas the others have a density ρ_{2} * > ρ_{0} (see SI Appendix).
Interestingly, the potential F = (1 − α)L + αU + TS appears as a generalization of the notion of free energy introduced in physical systems. Mapping the global utility U onto the opposite of the energy of a physical system, it turns out that for α = 1, the maximization of the function U + TS is equivalent to the minimization of the free energy E − TS. For α < 1, the potential F takes into account individual moves through the link function L. Furthermore, the potential F can be calculated for arbitrary utility functions, allowing one to predict analytically the global town state. Such an achievement has thus far eluded individualistic, Schellingtype models, which had to be studied through numerical simulations (9).
To explicitly obtain the equilibrium configurations, one needs to know the specific form of the utility function. To illustrate the dramatic influence of the cooperativity parameter α, we use the asymmetrically peaked utility function (18), which indicates that agents prefer mixed blocks (Fig. 2). The overall town density is fixed at ρ_{0} = 1/2 to avoid the trivial utility frustration resulting from the impossibility to attain the optimal equilibrium (ρ_{q} = 1/2 for all blocks). We also consider for simplicity the limit T → 0 in order to avoid entropy effects. The qualitative behavior of the system is unchanged for ρ_{0} ≠ 1/2 or for low values of the temperature, as shown in the SI Appendix.
In the collective case (α = 1), the optimal state corresponds to the configuration that maximizes the global utility, which can be immediately guessed from Fig. 2, namely ρ_{q} = 1/2 for all q (Fig. 1 A). On the contrary, in the selfish case (α = 0, Fig. 1 B), maximization of the potential F(x) shows that the town settles in a segregated configuration where a fraction of the blocks are empty and the others have a density ρ_{s} > 1/2. Surprisingly, the city settles in this state of low utility in spite of agents' continuous efforts to maximize their own satisfaction. To understand this frustrated configuration, note that the collective equilibrium (ρ_{q} = 1/2 for all q) is now an unstable Nash equilibrium at T > 0. The instability can be understood by noting that at T > 0 there is a positive probability that an agent accepts a slight decrease of its utility and leaves a block with density ρ_{q} = 1/2. The agents remaining in its former block now have a lower utility and are more likely to leave to go to another ρ_{q} = 1/2 block. This departure creates an avalanche that empties the block as each move away further decreases the utility of the remaining agents. This avalanche stops when the stable (Nash) equilibrium, given by the maximum of the potential, is reached. This state corresponds to a spatially inhomogeneous repartition of agents in the city. To understand the transition between mixed and segregated configurations, it is instructive to calculate the values of both the overall utility and the potential for different values of m (at α = 0). For homogeneous towns, for all m, the normalized collective utility is given by U* = U/(ρ_{0} HQ) = u(ρ_{0} = 1/2) = 1 and the normalized link function equals L* = L/(ρ_{0} HQ) = ℓ(ρ_{0})/ρ_{0} = 1/2, where ℓ is given in Eq. 5. The values of L* and U* displayed in Table 1 show that the utility of the segregated equilibrium is lower but that its potential is higher, explaining its stability. Note that the gap between the link function values of the homogeneous and segregated configurations increases with m.
This increase helps one understand why the greater the m, the greater the value of tax parameter necessary to reach the homogeneous configuration. Indeed, the segregated states are separated from mixed states by a phase transition at the critical value α_{c} = 1/(3 − 2m), which increases with m (Fig. 3). This transition differs from standard equilibrium phase transitions known in physics, which are most often driven by the competition between energy and entropy. Here, the transition is driven by a competition between the collective and individual components of the agents' dynamics. The unsatisfactory global state of the city can be interpreted, from the economic point of view, as an effect of externalities: By moving to increase its utility, an agent may decrease other agents' utilities without taking this into account. From a standard interpretation in terms of Pigouvian tax (19), one expects that α = 1 is necessary to reach the optimal state because by definition this value internalizes all the externalities the agent causes to the others when moving. Our results show that the optimal state is maintained until much lower tax values are reached (for example, α_{c} = 1/3 at m = 0), a surprising result which deserves further analysis. Another interesting effect is observed for m > 2/3 (Fig. 3). Introducing a small tax has no effect on the overall satisfaction, the utility remaining constant until a threshold level is attained at α_{t} = (3m − 2)/(6 − 5m).
We focused up to now on the zero temperature limit. For low temperatures, the main qualitative conclusions are not modified, as the phase diagram is modified only for extremal values of ρ_{0} by entropic contributions. At higher temperatures, the city tends to become homogeneous as the effect of “noise” (i.e., of the features that are not described in the model) dominates over the utility associated with the densities of the blocks (see Fig. 4).
Discussion
In the limit α = 0, our model becomes similar to Schelling's segregation model (8), with two main differences: the existence of two types of agents of two colors and the definition of the agent's neighborhoods. We now show that these additional features do not introduce any essential effect.
Let us start by introducing two types of agents with different “colors” (such as red and green). Simple calculations (see SI Appendix) show that for two species that only care about the density of neighbors of their own color, the block potential Eq. 6 becomes with straightforward notations (for example, u _{R}(ρ_{R}) represents the utility of a red agent in a block with a density ρ_{R} of red agents). In the more general case of utility functions depending on both the density of similar and dissimilar neighbors, it is also possible to derive a block potential if the utility functions verify a symmetry constraint. This constraint is not very restrictive, in the sense that no qualitative feature of the model is lost when one restrains the study to utilities that verify it (see SI Appendix).
Finding the equilibrium configurations amounts to finding the set {ρ_{qR}, ρ_{qG}}, which maximizes the potential F(x) = ∑_{q} f(ρ_{qR}, ρ_{qG}) with the constraints ∑_{q}ρ_{qR} = Qρ_{0R} and ∑_{q}ρ_{qG} = Qρ_{0G}, where ρ_{0G} and ρ_{0R} represent, respectively, the overall concentration of green and red agents.
Because of the spatial constraints (the densities of red and green agents in each block q must verify ρ_{qR} + ρ_{qG} ≤ 1), the “two populations” model cannot formally be reduced to two independent “one population” models. However, the stationary states can still be easily computed. Let us focus once again on the T → 0 limit and suppose, for example, that ρ_{0R} = ρ_{0G} = ρ_{0}/2. The stationary state depends once again on the values of ρ_{0}, m, and α. For low values of α, it can be shown that the system settles in segregated states where each block contains only one kind of agent with a density ρ_{0} (see Fig. 5 A). For α ≥ α_{c}, the system settles in mixed states where the density of a group in a block is either 0 or 1/2 (see Fig. 5 B). The reader is referred to SI Appendix for more details.
We now turn to the difference in agents' neighborhoods. In Schelling's original model, agents' neighbors are defined as their eight nearest neighbors. Our model considers instead predefined blocks of common neighbors. First, it should be noted that there is no decisive argument in favor of either neighborhood definition in terms of the realism of the description of real social neighborhoods. Second, we note that introducing blocks allows for an analytical solution for arbitrary utility functions. This contrasts with the nearest neighbor case, where the best analytical approach solves only a modified model that abandons the individual point of view and is limited to a specific utility function (11). Finally, the simulations presented in Fig. 5 show that the transition from segregated to mixed states is not affected by the choice of the neighborhood's definition. We conclude that the block description is more adapted to this kind of simple modeling, which aims at showing stylized facts as segregation transitions.
Our simple model raises a number of interesting questions about collective or individual points of view. In the purely collective case (α = 1), the stationary state corresponds to the maximization of the average utility, in analogy to the minimization of energy in physics. In the opposite case (α = 0), the stationary state strongly differs from the simple collection of individual optima (20): The optimization strategy based on purely individual dynamics fails, illustrating the unexpected links between micromotives and macrobehavior (21). However, the emergent collective state can be efficiently captured by the maximization of the link function ℓ(ρ) given in Eq. 5, up to constraints in the overall town density. This function intimately connects the individual and global points of view. First, it depends only on the global town configuration (given by the ρ_{q}), allowing a relatively simple calculation of the equilibrium. At the same time, it can be interpreted as the sum of the individual marginal utilities gained by agents as they progressively fill the city after leaving a reservoir of zero utility. In the stationary state, a maximal value of the potential L is reached. Therefore, no agent can increase its utility by moving (because Δu = ΔL), consistent with the economists' definition of a Nash equilibrium.
Equilibrium statistical mechanics has developed powerful tools to link the microscopic and macroscopic levels. These tools are limited to physical systems, where dynamics are governed by a global quantity such as the total energy. By introducing a link function, analogous to state functions in thermodynamics or potential functions in game theory (22), we have extended the framework of statistical mechanics to a Schellinglike model. Such an approach paves the way to analytical treatments of a much wider class of systems, where dynamics are governed by individual strategies.
Acknowledgments
We acknowledge interesting discussions with Florence Goffette–Nagot.
Footnotes
 ^{1}To whom correspondence may be addressed. Email: pablo.jensen{at}enslyon.fr

Author contributions: S.G., E.B., and P.J. designed research; S.G., E.B., R.L., and P.J. performed research; and S.G., E.B., R.L., and P.J. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/cgi/content/full/0906263106/DCSupplemental.
References
 ↵
 Cotterill R
 ↵
 Goodstein D
 ↵
 Damasio AR
 ↵
 Changeux JP
 ↵
 Strahan W,
 Cadell T
 Smith A
 ↵
 Latour B
 ↵
 Mas–Colell A,
 Whinston MD,
 Green JR
 ↵
 Schelling TC
 ↵
 Clark W,
 Fossett M
 ↵
 ↵
 ↵
 Dall–Asta L,
 Castellano C,
 Marsili M
 ↵
 Vinkovic D,
 Kirman A
 ↵
 ↵
 Anderson SP,
 De Palma A,
 Thisse JF
 ↵

 Callen H
 ↵
 ↵
 ↵
 Kirman AP
 ↵
 Schelling TC
 ↵
Citation Manager Formats
More Articles of This Classification
Physical Sciences
Applied Physical Sciences
Social Sciences
Related Content
 No related articles found.