Jean-Philippe Bouchaud

Eric Fleury

Jean-François Pinton

Bruno

Eric Bertin

Guillaume Beslon

Florence Goffette-Nagot

Sara Franceschelli

Céline Ro- Bardet

Dominique Boullier

Tommaso Venturini

Paul Girard

Jean-Baptiste Rouquier

John Mc Breen

Remi Lemoy

Christine Représente

Au moment où j'écris ces lignes, je prends conscience de ce que représentent les trois dernières années écoulées: un ensemble de rencontres, de discussions, de lectures, de recherches... toutes plus enrichissantes et stimulantes les unes que les autres. C'est donc tout naturellement que je tiens à adresser ici mes remerciements à tous ceux qui ont pu m'accompagner à un moment ou un autre au cours de ma thèse.

Tout d'abord un immense merci à Pablo pour m'avoir introduit dans le monde des systèmes complexes, pour sa confiance, ses encouragements et ses conseils tout au long de ces années.

Introduction

This thesis explores the problems raised by the aggregation of entities into a global, collective level. This is certainly an old problem in many fields of science. Already in the 5 th century before Christ, Leucippus of Miletus started the atomic tradition, which argued that differences in atomic shape and size determined the various properties of matter. At the Renaissance, thinkers started to think about the articulation between individuals and a global entity called society thanks to quantitative data. In the 19 th century, Thomas Buckle published the History of Civilization in England which aimed at showing that, while individual destinies seem erratic and unpredictable, statistical laws do govern the course of human progress in a fixed and regular way. Maxwell was influenced by his reading of this very well-known work when he founded statistical physics by abandoning a Newtonian view of deterministic atoms to seek explanations in terms of statistics. This allowed him to explain quantitatively how the macroscopic characteristics of gases depend on its atoms' behaviours.

More generally, fundamental science has striven to reduce the diversity of the world to some stable building blocks such as atoms and genes. To be fruitful, this reductionist approach must be complemented by the reverse step of obtaining the properties of the whole (materials, organisms) by combining the microscopic entities, a notoriously difficult task [START_REF] Hayden | Life is complicated[END_REF][START_REF] Chouard | Beneath the surface[END_REF][START_REF] Anderson | More is Different[END_REF]Grauwin et al., 2009a;[START_REF] Gannon | Too complex to comprehend?[END_REF]. Therefore, linking the microscopic and macroscopic behavior is at the heart of many natural and social sciences. However, this apparent similarity conceals essential differences across disciplines: while physical particles are assumed to optimize the global energy, economic agents maximize their own utility. In sociology, the very distinction of two levels (individuals and social groups) is put into question, as humans cannot properly be defined without taking into account the social groups they need to live in (e.g. language, an essential part of the individual which is acquired through society).

More specifically, our scope here is to address the aggregation problem in social systems, using tools derived from statistical physics, and more generally quantitative tools. This problem has received new impetus recently, mainly from to the avalanche of digital data on social systems. These cover many different fields [START_REF] Lazer | Computational social science[END_REF]: stock markets, demographics, geographical tracking of individual mobility, social networking, scientometrics. . . The amount and quality of these data open the possibility of a profound renewal of quantitative sociology [START_REF] Latour | Tarde's idea of quantification[END_REF].

The increase of computing power has also brought the possibility of modelling complex socio-economic systems in a new way. Agent-based models simulate virtual societies in which simple rules are used to characterize the actions and interactions of large amount of agents. Simulations have shown that unexpected collective behaviors may emerge from these simple rules [START_REF] Schelling | Models of Segregation[END_REF]. In economics, they have allowed to go beyond the simplistic assumptions of, for example, perfectly rational agents, which are necessary to obtain analytical theories [START_REF] Grauwin | Dynamic models of residential segregation: brief review, analytical resolution and study of the introduction of coordination[END_REF] but can lead to unrealistic predictions [START_REF] Bouchaud | Economics needs a scientific revolution[END_REF].

The situation seems ripe for tighter connections between social and natural scientists.

As most social scientists lack the training needed to handle, visualize and model massive amount of data, they could benefit from collaborations with mathematicians, computer scientists or physicists, who are more familiar with that kind of tools. However, for these collaborations to be fruitful, mutual knowledge and respect are essential. From our "modelling" side, one has to be cautious to understand and respect the specificity of social systems, without trying to export our preferred models in a "wild way" (what Bernard Walliser called "brute transfer analogies" [START_REF] Walliser | les fonctions des modèles économiques available at[END_REF]).

In the following, we present three examples of our "respectful" approach to the modelling of social systems. These three parts of the thesis can be read independently.

Individual dynamics and Schelling's segregation model

The first part of this thesis focuses on a paradigmatic model of the emergence of puzzling macroscopic behaviour from simple individual rules, Schelling's segregation model [START_REF] Schelling | Models of Segregation[END_REF][START_REF] Schelling | Micromotives and Macrobehavior[END_REF]. As soon as 1969, Thomas C. Schelling proposed a model aiming at formalizing the aggregate consequences of individual preferences regarding the social environment. In his 1971's Dynamic Models of Segregation paper, he simulates the evolution of the spatial repartition of two types of agents living in a virtual city. The agents have preferences over the composition of their neighborhood and are given the opportunity to move in order to satisfy their preferences, or utilities. Schelling shows that even "mildly" segregative individual preferences lead to high levels of segregation, even if this global outcome does not correspond to a residential configuration maximizing the collective utility. In other words, the global pattern is not a linear extrapolation of the individual preferences.

Schelling's 1971 paper is widely known thanks to this apparently paradoxical effect: a mild preference for one's neighbors to be of the same color leads to total segregation, even if total segregation does not maximize collective utility. Later research showed that even a peaked utility function, that is, a function achieving its maximum for a 50%-50% environment, can lead to a fully segregated equilibrium as soon as this function is asymmetric -even in a city where the two groups are equally proportioned (Zhang, 2004b;[START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Barr | Segregation and strategic neighborhood interaction[END_REF]). Schelling's results are also robust to different definitions of individual's environment [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Fagiolo | Segregation in networks[END_REF]. Recently, Zhang (2004aZhang ( ,b, 2010) ) developed analytical solutions to different versions of Schelling's model. Basically, the paradox arises from a lack of coordination among agents, which generate externalities preventing the system to reach the social optimum. Our work on Schelling's model builds on this literature.

The two first chapters focus on economics' aspects of Schelling's model. Chapter one examines the effects of introducing coordination in the moving decisions. This coordination is achieved in two different ways. We first impose different levels of taxes proportional to the externality generated by each move of the agents. We then investigate the effect of the introduction of a local coordination by vote of co-proprietors, who are defined as the closest neighbors of each agent. In both cases, we show that even a small amount of coordination can significantly reduce segregation.

Chapter two proposes an analytical resolution of Schelling segregation model for a wide range of utility functions. Using evolutionary game theory, we provide existence conditions for a potential function, which characterizes the global configuration of the city and is maximized in the stationary state. We use this potential function to analyze the outcome of the model for three utility functions corresponding to different degrees of preference for mixed neighborhoods. The main results are :

• We show that linear utility functions are the only case for which the potential function is proportional to collective utility, the latter being hence maximized in stationary configurations.

• Schelling's original utility function is shown to drive segregation at the expense of collective utility.

• If agents have a strict preference for mixed neighborhoods but still prefer being in the majority versus in the minority, the model converges to perfectly segregated configurations, which clearly diverge from the social optimum.

Departing from earlier literature, these conclusions are based on analytical results.

Our model being based on bounded neighborhoods rather than continuous ones (as in Schelling's original model), we discuss the differences between the bounded and continuous definition of neighborhoods and show that, in the continuous neighborhood case, a potential function exists if and only if the utility functions are linear. As a by-product, our analysis builds a bridge between Schelling's model and the Duncan and Duncan segregation index. The collaboration with an economist (Florence Goffette-Nagot) has lead to two papers submitted to economics' journals. One is almost accepted in a prestigious journal (J of Public Economics), showing the relevance of our approach for that community, while the other is also submitted to a very good journal (J of Economic Behavior and Organization).

Chapter 3 switches to a physicist's point of view on Schelling model. We focus on a simplified version of the model, with agents of a single color and vacant sites, which still retains the essential feature of the original model, namely the paradox of macroscopic segregation for microscopic "tolerant" individuals. By generalizing the concept of free energy in order to include dynamics driven by individual optimization, we are able to solve exactly the model for arbitrary utility functions. Specifically, we introduce a parameter 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 towards a mixed phase of high utility. This work has been published in PNAS in 2009.

In the last chapter, we present our "linking" approach in a more general way. We show how our approach could pave the way to analytical treatments of a wide range of socio-economic models. As a first example, we derive an analytic solution for a congestion model. This chapter has been accepted for publication in Advances in Complex Systems (2011).

Maps of Science

The second part of this thesis addresses the question of emergence of macroscopic features out of interactions between individuals from a different perspective. Instead of simulating simple models, it uses data from real social systems and explores the question of aggregation of these data into insightful (social) groups. Specifically, we use the huge existing databases on scientific literature (mainly Web of Science) to investigate the existence and evolution of paradigms or scientific institutions.

Chapter 5 tackles the question of the existence and coherence of a hypothetical field, that of "complex systems science". Picking up again the reductionist theme, it is interesting to note that the science of complex systems tries to obtain the properties of the whole by combining the microscopic entities, albeit from a different perspective. It adds the idea that "universal principles" could exist, which would allow for the prediction of the organization of the whole regardless of the nature of the microscopic entities.

Ludwig Von Bertalanffy wrote already in 1968: "It seems legitimate to ask for a theory, not of systems of a more or less special kind, but of universal principles applying to systems in general" (Von Bertallanffy, 1976). This dream of universality is still active: "[Complex networks science] suggests that nature has some universal organizational principles that might finally allow us to formulate a general theory of complex systems" [START_REF] Solé | quoted in the New York Times[END_REF]. Have such universal principles been discovered? Could they link disciplines such as sociology, biology, physics and computer science, which are very different in both methodology and objects of inquiry (SantaFe, 2010)? Or does the "complexity" field have too high a "mouth to brain ratio" (Scientific American, 1995)?

Thanks to a large database (141 098 records) of relevant articles published between 2000 and 2008, we empirically study the "complex systems" field and its claims to find universal principles applying to systems in general. The study of references shared by the papers allows us to obtain a global point of view on the structure of this highly interdisciplinary field. We show that its overall coherence does not arise from a universal theory but instead from computational techniques and fruitful adaptations of the idea of self-organization to specific systems. We also find that communication between different disciplines goes through specific "trading zones", ie sub-communities that create an interface around specific tools (a DNA microchip) or concepts (a network). We have also gathered an exhaustive database of French natural science articles (around 65 000 published in 2000 and 80 000 in 2010) to investigate the place of complex systems science within the whole landscape of science. These maps suggest that there exists (yet?) no conceptual kernel for "complexity science", some unified set of theories or concepts that could give the field enough coherence to be a subfield identifiable by shared references (and therefore by bibliographic coupling). Certainly, Self-Organization, Self-Organized Criticality or Complex Networks do constitute such coherent subfields. However, despite some claims, these subfields seem to have only weak links to the rest of the complex systems "galaxy" shown above, which prevents the formation of a coherent "complex systems science". This work is currently submitted to Plos One.

In chapter 6, we develop a set of routines that allows to draw, in a few hours, different maps of the research carried out in a scientific institution. Our toolkit uses OpenSource elements to analyze bibliometric data gathered from the Web Of Science.

We take the example of our institution, ENS de Lyon, to show how different maps, using co-occurrence (of authors, keywords, institutions...) and bibliographic coupling can be built. These maps may become a valuable tool for institutions' directors, as they offer different views on the institution at a global scale. This work is submitted to Scientometrics.

In these two studies, we use an old but quite forgotten approach to measure the relations between articles, i.e. bibliographic coupling [START_REF] Kessler | Bibliographic coupling between scientific papers[END_REF]. The idea is that papers sharing references are closer than papers with no common reference. By grouping similar papers with standard techniques (such as modularity optimization [START_REF] Girvan | Finding and evaluating community structure in networks[END_REF])), we define scientific communities or subdisciplines in a "natural" way, which is in any case largely independent of administrative or institutional structures such as disciplines or laboratories. This has the decisive advantage of allowing for a "fresh" look at science in action or research frontiers. For example, we identify a large community working on complex networks that has received no institutional support (in France at least) or recognition in terms of "subject categories" from Web of Science and would therefore be invisible had we interrogated the database through these categories. We also identify several distinct communities working on nanostructures in France (labelled as nanoindentation, nanowires, quantum dots . . . ) in 2010, which questions the use of a single discipline from an institutional point of view. In short, using large databases should not prevent scientists from inquiring about the interpretation of these data : the categories used to extract the data or the meaning of the aggregations used to examine it.

Emergence of Institutions in Social Systems

The meaning of aggregations in the social space is the central question of the last part of the thesis. Various sociological theories try to apprehend social phenomena under different points of view. According to the holistic paradigm, mainly based on Emile Durkheim's ideas, individuals are embedded into social structures and institutions that constrain them, shape their actions and emotions. On the contrary, in the atomic (or individualistic) paradigm, individuals should be considered as the central ontological elements in social systems. Constant interactions between the "social atoms" construct society, ie structures, institutions, norms, which are supposed to serve the interests of the individuals. Both the holistic and the atomistic approaches are based on a strong assumption: there is a clear dichotomy between two "levels", namely individuals and society. This distinction is common to many fields and is often summarized by the notion that "the whole is greater than the sum of its parts".

Chapter 7 questions this fundamental distinction. For more than a year, we have been collaborating with a team of sociologists from the MediaLab at Sciences Po. The scope is to use the social theory developed by Gabriel Tarde at the end of the 19th century to imagine different ways of conceptualizing the articulation between "wholes" and "parts". One hypothesis is that the distinction between two levels is an artefact originating in the difficulty of navigating through huge amounts of data. This hinders the possibility to visualizing (and therefore conceptualizing) the evolution of social phenomena without making a distinction between the individual and the aggregated levels.

Using scientometrics data, we first explore alternative ways of visualizing wholes and parts. We have also been working in collaboration with the MediaLab sociologists in order to attempt to formalize Tarde's ideas in a model which would lead to a simulation algorithm. We started by defining the features requested by sociologists for the algorithm to be faithful to Tarde's intuitions. The main point was to obtain "wholes" through the simplification of complex individuals. We then developed a first prototype which fulfilled several of these demands but raised many more questions. While this process was positive because it uncovered several fuzzy features in Tarde's social theory, it also turned out that the scope of the model was too ambitious for the time scale of this thesis. Chapter 8 then presents the current state of ongoing work on another -more standard -approach into emergence of social structures. We still focus on a question raised by our colleagues sociologists, namely the existence of lasting structures from non lasting entities. But we use the standard (and safer!) physicist approach : start with simple individuals and build groups with interesting features. Specifically, our model is based on Deffuant's opinion model [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF] with an adaptive network similar to what can be found in [START_REF] Kozma | Consensus formation on adaptive networks[END_REF]. While these papers focus on the stationary properties of the model -the final, stable states reached at the end of the simulations -we chose to build a model to investigate the dynamical properties of social structures which would always be changing. For this, we have added three features.

First, noise, which allows to recover the intuitive fact that convergence of opinions cannot be strictly limited to persons already sharing similar opinions. Second, we add the possibility for agents to "die", to investigate whether the groups obtained lasted longer than the typical agent lifetime. Third, we introduce heterogeneity in opinion space by adding the "age" of the agent as a characteristic influencing the exchange of opinions.

While the outcomes of the model are not yet fully explored, we already found interesting group dynamics. All along the runs, new groups may emerge, groups may disappear by merging with other groups or by death of all their agents, some groups may last for hundreds of agents' lifetimes. . . These investigations echo the famous study by Georg Simmel of "the persistence of social groups" [START_REF] Simmel | The Persistence of Social Groups[END_REF]: "it is meaningful to speak of group identity, despite shifting membership and low institutionalization, if there is some membership continuity in contiguous stages [...] The change, the disappearance and entrance of persons, affects in two contiguous moments a number relatively small compared with the number of those who remain constant. The departure of the older and the entrance of the younger elements proceed so gradually and continuously that the group seems as much like a unified self as an organic body in spite of the change of its atoms".

Despite this tempting parallel, we do not think that this kind of simplistic model should aim at being realistic by inclusion of additional ingredients. Rather, our discussions with Sciences Po's sociologists open another direction. We speculate that these models can help them enriching their conceptualizations of the structuration phenomenon. This could arise from a detailed examination of the structurations that happen in this virtual society and their tentative interpretation using the usual sociological theories. Does this confrontation help them in any way in renewing their conceptual repertoire? Do we observe group evolutions that are unexpected and difficult to explain?

The future of this stimulating and demanding collaboration will tell! [START_REF] Schelling | Models of Segregation[END_REF][START_REF] Schelling | Micromotives and Macrobehavior[END_REF]. In his 1971's Dynamic Models of Segregation paper, Schelling showed that if the preferences considered are such that an environment of more than 50% of owngroup agents is highly preferred to a less than 50% of own-group environment, then the equilibrium configuration exhibits high levels of segregation. Schelling's 1971 paper is widely known thanks to this apparently paradoxical effect: a mild preference for one's neighbors to be of the same color leads to total segregation, even if total segregation does not maximize collective utility. Later research showed that even a peaked utility function, that is, a function achieving its maximum for a 50%-50% environment, can lead to a fully segregated equilibrium as soon as this function is asymmetric -even in a city where the two groups are equally proportioned (Zhang, 2004b;[START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Barr | Segregation and strategic neighborhood interaction[END_REF]. Later literature showed that Schelling's results are also robust to different definitions of individual's environment [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Fagiolo | Segregation in networks[END_REF]. A physical analogue of Schelling model [START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF] was proposed. Zhang (2004aZhang ( ,b, 2010) ) develop analytical solutions to different versions of Schelling's model. Grauwin et al. (2009a[START_REF] Grauwin | Dynamic models of residential segregation: an analytical solution[END_REF] generalize this type of solution and propose an analytical treatment that allows to calculate the global segregation pattern starting from a broad range of individual utility functions.

In Schelling-type models, an assumed condition for integration to occur is that agents have a preference for mixed environments. But that condition is often not a sufficient one, because mixed configurations are unstable with respect to fluctuations, whereas segregated configurations are very stable. The stability of the city configurations and the gaps between the agents' micro-motives and the emergent macro-behavior have been recognized as the results of a coordination problem (Zhang, 2004a(Zhang, ,b, 2010)). It is indeed the existence of locational externalities, that is, the fact that moving agents do not take into account their impact on their neighbors' utilities, that moves the city to highly segregated configurations, even if individuals' preferences favor a mixed environment.

This is particularly the case when the agents' preferences are given by the asymmetrically peaked utility function, the system ending in highly segregated configurations whereas the agent's main preference is for mixed neighborhoods (Zhang, 2004b;[START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF]Grauwin et al., 2009b,a). Externalities produced by agents' mobility are also encountered in economic geography (see [START_REF] Charlot | Agglomeration and welfare: The core-periphery model in the light of Bentham, Kaldor, and Rawls[END_REF] and little is known about the means allowing to fight them.

A way to reach the welfare maximizing configuration in Schelling model could be a mechanism internalizing the externalities generated by the agents' selfish moves. To do so, a classical idea in economics is to impose a taxation equal to the generated externality. Such a policy implemented by a central authority is known to lead to social optimum, where the collective utility reaches its highest possible value. Recently, some papers have proposed to add some corrective mechanisms in the original Schelling model to reinforce the integrated configurations. [START_REF] Dokumaci | Schelling Redux: An Evolutionary Dynamic Model of Residential Segregation[END_REF] propose to tax the agents proportionally to the density of population in their neighborhood. The tax level depends on the ethnic origin of the agents, as might be the case under various form of affirmative action. [START_REF] Barr | Segregation and strategic neighborhood interaction[END_REF] introduces additional social interactions into Schelling's model by coupling it with a Prisoner's Dilemma played with neighbors. In both cases however, the effect of the added mechanism could be reformulated in terms of a redefinition of the agents' utility function.

The present chapter, based mainly on simulations, examines the effects of introducing coordination in the moving decisions, and shows that even a small amount of coordination can break segregation. We first verify that introducing a Pigouvian tax leads to the social optimum in a dynamic model of segregation with an asymetrically peaked utility function (section 3). We also investigate the impact of different levels of taxes and we show that a tax equal to only one fifth of the generated externalities is sufficient in certain cases to reduce consequently the gap between the equilibrium and the social optimum, created by the agents' selfish behavior. To the best of our knowledge, this work has never been done in the context of Schelling segregation models. However, these tax policies are not easy to implement in practice since they require from the central authority a perfect knowledge of the city at the local scale. Such information is rarely perfectly nor freely available. Hence, the policies implemented by central authorities correspond generally to mechanisms that differ from the Pigouvian tax. Therefore, we propose in section 4 a tax based on the share of similar neighbors' in agents' neighborhoods. Finally, we investigate in section 5 the effect of the introduction of a local coordination by vote of co-proprietors. That completely new coordination mechanism has the advantage of remaining in the spirit of Schelling's model, adding only individual decisions based on the same utility as the moving agent, without any need of a central authority. Before developing models with some coordination, we present in section 2 the standard Schelling model which we will use as a benchmark.

1.2 A standard model

Basic setup

The city and neighborhood definition

Our artificial city is a two-dimensional N xN square lattice with periodic boundary conditions, ie a torus containing N 2 cells. Each cell corresponds to a dwelling unit, all of equal quality. We suppose that a certain characteristic divides the population of this city in two groups of households that we will refer to as red and green agents. Each location may thus be occupied by a red agent, a green agent, or may be vacant. We denote by N V the number of vacant cells, and by N R and N G the number of respectively red and green agents. All these numbers are kept fixed over a simulation. The parameter N thus controls the size of the city, the parameter v = N V /N 2 its vacancy rate, and the

fraction n R = N R /(N R + N G ) its composition.
We define a state x of the city as a N 2 -vector, each element of this vector labeling a cell of the N xN lattice. Each state x thus represents a specific configuration of the city. We note X the set of all possible configurations, the demographic parameters (N , v, n R ) being fixed.

Since [START_REF] Schelling | Models of Segregation[END_REF] Note that since some locations remain empty, the size H of the neighborhood of an agent can also be interpreted as the maximum number of neighbors an agent can have.

The global characteristics of our model remain qualitatively independent of any specific definition of neighborhood, provided its size H is relatively small compared to the size N 2 of the city, in order to maintain the "local" property of neighborhood.

In all the simulations presented in this chapter, the demographic parameters of the city are fixed. The size of the city is set to N 2 = 400, a good compromise between the necessity to take a large value of N to avoid small city effects 1 and the convenience to take a small value of N to achieve short computation times. The number of agents of each group is fixed to N R = N G = 180 and the vacancy rate is fixed to v = 10%. As usually assumed, we use continuous neighborhoods, that is, the neighbors of an agent are the agents living on the H nearest cells surrounding him. Unless otherwise stated, the neighborhood size is fixed to H = 8.

Agent's utility function

Each agent computes his own level of satisfaction via a utility function which depends only on his neighborhood composition. Let us consider an agent whose neighborhood is composed of R red agents, G green agents and V vacant cells. Since R + G + V = H, one needs two independent parameters to describe the composition of the neighborhood of the agent. In all generality, we can thus write the utility of an agent for example as a

1 Such as those emphasized by [START_REF] Singh | Schelling's Segregation Model: Parameters, Scaling and Aggregation[END_REF].

function of R and G or as a function of the fraction s of the agent's similar neighbors and V . Most models of the literature assume for simplification that agents of a same group share the same utility function. Hence, one only needs a utility function u R to describe the preference of the red agents and a utility function u G to describe the preference of the green agents.

It is easy to understand that a utility function can be defined up to an additive constant depending on a reference situation but also up to a multiplicative constant depending on the measure scale. A common choice in the literature is to take these constants such that a zero utility level denotes a complete dissatisfaction of the agent and a utility of one denote complete satisfaction. We will stick to that use in the following.

We will suppose that all the agents share the same "asymmetrically peaked utility function" u m (s), where s is the fraction of one's similar neighbors and 0 ≤ m ≤ 1; u m is defined by:

u(s) = 2s for s ≤ 0.5 2 -m -2(1 -m)s for s > 0.5 (1.1)
Figure 1.2: In our simulations, the agents all share the same utility function um(s). We explore the change in behavior of the agents according to the value of parameter m. Except for m = 1, the agents always have a strict preference for perfectly mixed neighborhood. Except for m = 0, their utility function presents an asymmetry: they prefer all-similar neighborhoods to all-dissimilar neighborhoods.

By varying the value of the parameter m, we will then be able to explore the responses of our system to a whole family of utility functions. Our choice of working only with the asymmetrically peaked utility function is driven by the fact for m > 0, the asymmetry in favour of the all-similar neighborhood in these utility functions leads to segregation patterns at the city scale at the cost of a low collective utility (see [START_REF] Grauwin | Dynamic models of residential segregation: brief review, analytical resolution and study of the introduction of coordination[END_REF][START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Barr | Segregation and strategic neighborhood interaction[END_REF]. This family of utility functions is thus the perfect candidate for testing whether the introduction of any type of coordination might allow to break segregative patterns and lead to more integrated patterns in which the collective utility would be higher.

Aggregate measures

In order to characterize a configuration at the global (city) scale, we need to introduce aggregate measures. Let s k , k ∈ {1, ..N R + N G } be the fraction of agent k's similar neighbors. In order to characterize the global level of segregation, we introduce for each configuration x the average fraction of same-type neighbors, or similarity:

s(x) = 1 N R + N G k s k (1.2)
Similarity is a well-known measure of segregation that was already used by [START_REF] Schelling | Dynamic models of segregation[END_REF]. However, the knowledge of s(x) may not be sufficient to determine if the level of segregation of a given configuration is significantly high or low compared to a random configuration with the same demographic parameters: a similarity of 0.8 would point out a high degree of segregation in a city with equally proportioned groups (n R = 0.5) but would be insignificant in a city with disproportioned groups (n R = 0.9). To avoid this kind of problem, we define in the spirit of [START_REF] Carrington | On measuring segregation in samples with small units[END_REF] the normalized index of similarity s * : X → [-1, 1] by

s * (x) =            s(x) -srandom 1 -srandom if s(x) ≥ srandom s(x) -srandom srandom if s(x) < srandom (1.3)
where srandom is the expected value of the similarity index s implied by a random allocation of the agents in the city. This value depends on the size N , vacancy rate v and composition n R of the city and on the size H of a neighborhood. However, in the cases studied below, i.e. for n R = 0.5, v > 0, H ≥ 1, N 1, the value of srandom is indistinguishable from 0.5. We also introduce notations in order to characterize the level of collective utility:

U (x) = k u k (1.4) U * (x) = 1 N R + N G U (x) (1.5)
where u k is the utility of agent k, U (x) denote the collective utility of a configuration x and U * (x) its normalized value.

The logit dynamic rule

As explained before, in standard Schelling-type models, agents move only to satisfy their own interest. In our simulations, we consider that the dynamics follows a logit behavioral rule: at each iteration, an agent and a vacant cell are randomly chosen and the probability that this picked agent moves in that vacant cell is written as:

P r{move; W C} = 1 1 + e -∆u/T (1.6)
where WC stands for "Without Coordination" and with T > 0 a fixed parameter and ∆u the change in utility if the agent was to move to the chosen cell. At the first iteration, an initial configuration is randomly chosen.

The scalar T can be interpreted as a measure of the level of noise in an agent's decision. Clearly, the probability for an agent to take a utility-decreasing move drops down as T → 0 and the described rule thus converges to the non-strict best-response rule. For any finite T > 0, the agents choose non-best replies with a non-zero probability, but actions that yield smaller payoffs are chosen with smaller probability.

This kind of perturbed best-response dynamics has been developed in e.g. [START_REF] Anderson | Discrete Choice Theory of Product Differentiation[END_REF] or [START_REF] Young | Individual Strategy and Social Structure: An Evolutionary Theory of Institutions[END_REF]. Taken as a behavioral rule, the underlying logit choice function in Eq. 1.6 is rooted in the psychology literature (Thurston, 1928). From the microeconomic point of view, it can be given a justification in terms of a random-utility model where the random part in the utility function can be interpreted as a way to take into account criteria other than the neighborhood composition such as the quality of the housing, the proximity to one's workplace or any other idiosyncratic amenity. As shown in section 1.4, the logit dynamic rule has the advantage to grasp more aspects of reality (taking into account idiosyncratic amenities) and to lead the system to stationary results which are independent of the initial configuration. This is why we prefer that kind of dynamics to a more standard "best response" dynamic rule.

Beside bringing some degree of realism through the introduction of randomness in the agents' behavior, the logit rule also provides a strong analytical framework to Schelling's model (see Grauwin et al., 2009a,b).

Obviously, it implies that the probability that the state at the t th iteration x t is equal to a given state x only depends on the state at the previous iteration x t-1 :

Pr(x t = x|x t-1 , . . . , x 1 , x 0 ) = Pr(x t = x|x t-1 ) (1.7)
The dynamic rule thus yields a finite Markov process.

It is then easy to figure out that the Markov chain describing our system is irreducible (since T > 0 each imaginable move has a non-zero probability to happen and it is thus possible to get to any state from any state), aperiodic (given any state x and any integer k, there is a non-zero probability that we return to state x in a multiple of k iterations)

and recurrent (given that we start in state x, the probability that we will never return to x is 0). These three properties ensure that the probability to observe any state x after t iterations starting from a state y converges toward a fixed limit independent of the starting state y as t → ∞.

In other words, for each set of parameters and dynamic rule, there exists a stationary distribution

Π : x ∈ X → Π(x) ∈ [0, 1] , x∈X Π(x) = 1 (1.8)
which gives the probability with which each state x will be observed in the long run.

Clearly, for T → ∞, the randomness introduced in the dynamical rule prevails and the stationary distribution is just a constant. Similarly, for any finite T > 0, our dynamical system (the city) is evolving toward an attractor composed of a subset A of X. It follows that any measure M performed on the states space X -such as the global utility U -will in the long run fluctuate around a mean value

M ∞ = x∈A Π(x)M(x).
These mean values may depend on the amplitude of the noise T , but the amplitude of the fluctuations decreases as T → 0. These intuitions are confirmed later.

Simulations: influence of parameters m and T

We introduce the parameter τ as the average number of moves per agent. Considering the demographic parameters used in our simulations, an increment of 1 in τ corresponds to (1 -v)N 2 = 360 performed moves. In the simulations presented below, we use τ as a chronological reference.3

We present on Vriend , 2007). This makes mixed neighborhoods unstable and segregated configurations very stable. In particular, once the city is divided into homogeneous areas, a red (green) agent will have no incentive to go from the red (green) area to the green (red) one, because his utility would then drop from m to 0. be written (the sums being taken on all the possible discrete values of s):

U * = s p(s)u(s) = U * m=0 + m s≥0.5 (2s -1)p(s) (1.9)
This form explains the linear dependency to m of the stationary mean collective utility observed on Fig. 1.6 for high values of T . Indeed, there are two parts in U * when T is large and the distribution of agents almost random: because the distribution does not differ from the distribution when m = 0, agents have the same "baseline" utility; however, those who have more than half of same-type neighbors have a higher utility level than in the m = 0 case, and the gap is linearly increasing in m.

For low values of T (roughly T ≤ 0.1), the dynamics is governed mainly by the deterministic part of the logit rule, i.e, the agents' preferences. For m < 0.3, the preference for a mixed neighborhood of the agent prevails: locally mixed configurations are observed and the segregation index is low. The dispersion in the distribution of neighborhoods' composition induces a level of mean utility around 0.75, which is just a bit better than what is obtained with a random allocation of agents (see Fig. 1.6).

For m ≥ 0.3, the asymmetry in the agents' utility function induces a higher stability of highly segregated states to which the system converges. These segregated states are particularly harmful in terms of welfare for m comprised between 0.3 and 0.8. For this range of value of m, preferences for majority status are high enough for segregation to appear, but not high enough for agents to benefit from the stationary segregated configurations. Therefore, the final outcome is always worse from a welfare point of view than it is in a random distribution of the agents. This observation clearly points out the deficiency with respect to social welfare of the location mechanism, which generates locational externalities. 1.3 A partial coordination by a Pigouvian tax

Basic setup

The idea of introducing a partial coordination is to make the moving agents take into account the whole or a fraction of the externality generated by their move on all the affected agents, ie her past and potentially new neighbors. A mechanism of this kind can results from the intervention of a benevolent planner who taxes negative externalities and rewards positive externalities. To that aim, we introduce a tax which is paid when the move occurs, and does not affect the utility received in the location itself. The amount of the tax is proportional to the externality produced by the move. In our reference case (without coordination), an agent decides to move according solely to the benefit ∆u she would achieve if she was to move. As a consequence from that move, she would generate an externality that amounts to ∆U -∆u. The tax to be paid by this CHAPTER 1. SCHELLING'S MODEL WITH LOCAL COORDINATION 35 agent when moving is therefore:

τ = α(∆U -∆u) (1.10)
where 0 ≤ α ≤ 1 is a parameter controlling the tax level, the limit case α = 0 corresponding to the without coordination case and the limit case α = 1 corresponding to a 'Global Coordination' case where only the collective utility is taken into account.

Dynamic rule

The probability that a move happens depends then on the differential of utility enjoyed by the agent in the initial location and destination and the tax she has to pay, as follows:

P r{move; P T } = 1 1 + e -[∆u+α(∆U -∆u)]/T (1.11)
where PT stands for "Pigouvian tax".

From an analytical point of view, these changes clearly do not affect the main property of the Markov chain theory: there exists one unique stationary distribution and hence the independence of the final configurations on the initial ones is still valid. For α = 1, the probability to move involves only the global function U . The stationary distribution can therefore be written as (see Grauwin et al., 2009a):

Π P T,α=1 (x) = e U (x)/T z∈X e U (z)/T
(1.12)

It is then easy to figure out that the configurations obtained in the limit T → 0 are those which maximize the collective utility.

For other values of α, it is possible to find an analytical expression of the stationary distribution in the context of bounded neighborhoods (see Grauwin et al., 2009a[START_REF] Grauwin | Dynamic models of residential segregation: an analytical solution[END_REF].

For continuous neighborhoods, an analytical approach is no longer possible. The reason can be stated quite simply: in the bounded neighborhood case, the information used to calculate the utility difference achieved by the moving agent (the initial and final neighborhood compositions) allows to calculate the difference in collective utility produced by the move. This is because the agent's initial neighbors share the same neighborhood as her, and their utility difference can therefore be calculated, the same being true for the final neighbors. Instead, in the continuous neighborhood case, the global utility difference depends on the neighbors of the neighbors of the moving agent. Indeed, the utility difference felt by the neighbors of the moving agent depends on their own neighbors, most of which are not neighbors of the moving agent. Lacking the analytical approach, one needs to turn to simulations in order to investigate the effects of the introduction of partial coordination.

Simulations

We present on Figs. 1.7 and 1.8 snapshots of typical stationary configurations along with the corresponding values of s * and U * for different values of α and m, with T = 0.1.

As previously stated, the case α = 0 corresponds exactly to the without-coordination case that we already commented on in the previous section. With α = 1, adding coordination to the m = 0 case shifts the random configuration to an ordered one:

enhancing the utility level is possible only by achieving s = 0.5 in every location. In this case, even if a tax does not affect the value of the similarity index, it allows to enhance welfare by clustering vacancies, thus diminishing the number of agents that do not have s = 0.5 exactly. Obviously, for high values of m, due to the form of the agents' utility function, a high utility level is obtained whatever the tax level. Still, the similarity index is lower when coordination is introduced: changing α from 0.5 to 0.8 and then to 1 decreases s * . For intermediate values of m, that have been identified as situations where equilibrium leads to harmful segregation in the without-coordination case, increasing α breaks segregation patterns.

Economic theory predicts that optimality (here a collective utility of 1) is obtained if a tax equal to the generated externalities is implemented. For α = 1, this is what would be obtained in the limit T = 0. Here, the collective utility is slightly inferior to 1 because of the finite value of the noise (T = 0.1). 4 More interesting, our simulations

show that a low level of taxation is able to significantly increase welfare: Fig. 1.8 shows that even a tax equal to one fifth of the generated externalities is enough to change the segregation level and to increase utility for 0.4 ≤ m ≤ 0.7.

An explanation for this result relies on an informal comparison of individual's and her neighbors' utility variations. From the segregation viewpoint, harmful individual moves are those in which an agent changes neighborhood to follow her taste for majority, for instance leaving a 40%-60% neighborhood for a 60%-40% neighborhood. The utility gain allowed by these moves are rather low. Still, those moves drive neighborhoods out of mixed situations and create avalanches of further moves that will end in segregated states. When their neighborhood composition changes by one individual, the variation of utility of each affected agent is of the order of 2/H for agents in minority and 2(1-m)/H for agents in majority in their neighborhood. As the utility gain for the agent is low compared to the externality affecting the other agents, internalizing even only a part of the externality with a tax on moves can be enough to hinder those individual moves that yield a small utility gain for the agent while increasing segregation trends and creating avalanches of segregating moves. In other words, the tax brakes the cumulative effects engendered by individual moves.

A local coordination by a feasible tax 1.4.1 Basic setup

A Pigouvian tax such as the one presented in the previous section supposes that the virtual central government has a precise knowledge of the neighborhood composition of each moving agent in order to tax all the moves, which is a rather utopian assumption.

We propose in this section a new variation of the Schelling model incorporating a differ- ent tax rule, based on more realistic assumptions regarding the government intervention ability.

We define the local district of an agent as the H g nearest cells surrounding him. We then introduce s Hg i , the fraction of similar agents present in the local district of agent i. The size H g ≥ H of the district takes into account in a stylized way the central government's lack of precision in the knowledge of the agents' locations. It is also the scale on which the central government can act to limit unwanted phenomena such as segregation. We propose here a simple tax definition, which aims at preventing the emergence or maintenance of a dominant group in each district. The central government imposes a tax on an agent i, which is defined as:

r i (s Hg i , θ) = θ|s Hg i -0.5| if s Hg i > 0.5 0 otherwise (1.13)
where θ is a fixed parameter controlling the tax level. Note that the tax does not penalize agents which are in the minority group inside their own district. The tax is payed by every agent belonging to the majority in the district. The utility of an agent is then redefined as:

ûm (s i , s Hg i , θ) = u m (s i ) -r i (s Hg i , θ) (1.14)
this new definition taking into account the penalty imposed by the tax.

Dynamic rule

As in the WC reference case, an agent decides to move according solely to the benefit in utility he would achieve if he was to move. The only difference here is that her utility incorporates the tax imposed by our virtual central government. We thus write the probability that a move happens as:

P r{move; F T } = 1 1 + e -∆û/T (1.15)
where FT stands for "feasible tax".

From an analytical point of view, the properties of the WC model resulting from the Markov chain theory remain unchanged: there exists one unique stationary distribution and the final configurations do not depend on the initial ones.

Taking θ = 0 cancels the tax mechanism and the FT rule comes back to the WC rule. For θ > 0, we expect that a rise in θ implies a rise in the probability of having non-segregated configurations in the stationary states.

As to the influence of the size H g of the districts, two limits can be looked upon: • For H g = H, the fraction s Hg i of similar agent in agent i's district can be identified with the fraction s i of similar neighbors. It is straightforward to notice that an agent utility û can thus be rewritten as:

ûm (s i , s Hg i , θ) = u m (s i ) -r i (s i , θ) = 2s i -0 if s i ≤ 0.5 2 -m -2(1 -m)s i -θ|s i -0.5| if s i > 0.5 = 2s i if s i ≤ 0.5 2 -(m -θ/2) -2(1 -(m -θ/2))s i if s i > 0.5 = u m-θ/2 (s i ) (1.16)
Hence our tax mechanism can be interpreted in this case as a direct control by the central government of the asymmetric parameter m in the agents' utility function.

According to the results obtained by simulation in the WC case (see Fig. 1.6), the asymmetric parameter must be inferior to m c 0.3 in order to avoid segregation.

The equivalence stated in Eq 1.16 thus allows us to predict that the minimal tax level necessary to break segregated patterns is:

θ c (m) = 2(m -m c ) 2m -0.6 (1.17)
• For H g = N 2 , the district corresponds to the whole city, in which we supposed that the two groups shared the same number of agents. Hence, for all the agents s Hg = 0.5 and r = 0. The tax mechanism has no effect and the outcomes are the same as in the WC reference case.

Simulations

We present on Fig. 1.9 some typical snapshots of stationary configurations obtained by simulating our feasible tax mechanism, while the different panels on Fig. 1.10 present the values of s * , U * and the mean tax paid by the agents. As previously stated, the WC case, which we take as reference, corresponds both to the θ = 0 case or the H g = N 2 = 400 case. Putting aside for the moment the H g = 8 case, we observe on Fig. 1.10 that for a fixed value of m and starting with H g = 400, decreasing H g leads almost always to a decrease in the segregation index, a decrease in the mean tax and an increase in the mean utility of the agents. The raise in utility compared with the WC case is particularly strong for intermediate values of m.

We thus show that the chosen tax, even if it differs from the Pigouvian tax, is able to lessen the segregation mechanism. This tax is governed by two parameters. θ determines the impact of the deviation from having a majority status in the neighborhood; the higher theta, the stronger the incentive to form mixed neighborhood, which explains the impacts found in the simulations. The impact of m seen in the simulations is straightforward: it determines the strength of the preference for the majority status and therefore the segregation level; it also impacts the average tax, as having a strong preference for the majority status leads agents to move to segregated neighborhoods, even if they have to pay the tax. More interesting, the simulation results show the effect of the local neighborhood size, that is, the consequence of the government lack of precision regarding the measure of segregation and give some hints as to the sufficient values of H g to avoid segregation. The smallest H g , the less segregation there will be.

However, even with H g = 44, that is five times larger than the neighborhood considered by the agents, the utility level enjoyed by the agents for intermediate values of m is improved compared to the WC case.

The snapshots of the final configurations displayed on Fig. 1.9 give more details as to the city patterns. They show clearly that the tax mechanism produces organized patterns which are more regular for larger values of m and higher values of θ. The typical width of these patterns increases with H g . These patterns ensure that most of the agents have an equal or higher number of agents of the other group than agents of their own group, inside their district (ie s Hg ≤ 1/2). In the meantime, the segregation index is always positive, meaning that on average an agent still has more similar neighbors than dissimilar ones.

In the H g = H = 8 case, no clear pattern is visible on Fig. 1.9, but s * < 0, that is, an agent has on average more dislike neighbors than similar ones. The case H g = H is special because there is a direct competition between the 'standard effect' of Schelling We introduce local coordination by taking into account the potential change of utility of the co-proprietors of the vacant cell considered by the potential mover. In the following, we will denote by C this set of agents. It seems more logical to introduce local coordination through the potentially new co-proprietors (who have you take an admission exam) than through the current co-proprietors (that you can quit on your free will). For mathematical convenience, we will suppose that the probability that the move happens can be computed as the product of the probability that the potential mover would like to move and the probability that the agents of C accept him: the two events are independent. We propose here one dynamic rule to counterbalance the wish of the potential mover by the opinion of his potentially new co-proprietors. Other mechanisms can of course be imagined. The 'local' nature of the implied coordination comes from the fact that only a fraction of the agents who might be affected by the potential move are consulted: they don't include previous neighbors and not all the new ones.

Dynamic rule

The simplest local coordination rule is that the potential mover needs the majority of the co-proprietors to endorse his moving in. Let ∆u i be the variation of utility of the co-proprietor i ∈ C if the move was to take place. We write the probability that the co-proprietor i votes 'for' the move:

P r{i, 'for'} = 1 1 + e -∆u i /T 2 (1.18)
The logit form of this acceptance probability can be justified in the same way as the logit for the moving agent. The parameter T 2 > 0 can then be interpreted as the amplitude of a noise that represents in a stylized way the preferences of the co-proprietors over any characteristics of the potential mover other than and not correlated to the group he belongs to (marital status, number of children, profession, religion, friendship, etc...). Since it is related to other factors, the noise affecting the co-proprietors is different from the noise affecting a moving agent. We moreover argue that since a coproprietor deciding whether to accept or not a new neighbor is qualitatively subject to less characteristics other than the group membership (ie to less noise) than a moving agent, it is realistic to suppose T 2 ≤ T .

The move takes place with a probability:

P r{move; LC} = 1 1 + e -∆u/T Y 1 1 + e -∆u i /T 2 i∈C (1.19)
where Y = 1, 1/2 or 0 if respectively more than half, exactly half or less than half of the co-proprietors vote 'for' the move, and where LC stands for "Local Coordination".

From an analytical point of view, the introduction of the vote of the co-proprietors does not change the main property of our system: it can always be described as a Markov chain, and since T 2 > 0, every move still has a non-zero probability to happen. This ensures the existence of one unique stationary distribution and hence the independence of the stationary states with regards to the initial starting state.

Simulations

We first present on Fig. 1.12 a typical evolution of the city in the case where the agents move according to the local coordination rule by consulting before each move h = 4 out of H = 8 of their potentially new co-proprietors. We limit our investigations by fixing the noise level T to 0.1. The level of noise attached to the co-proprietors is fixed to T 2 = 0.1 in order to be comparable to the chosen value of T and the parameter m of the utility function is fixed to 0.5. Starting from a highly segregated configuration, we observe the disaggregation of the two large homogeneous areas into a much less segregated configuration presenting more local patterns of segregation. This first simulation hence shows that the introduction of a bit of local coordination can be sufficient to break undesired segregated patterns and therefore, a fortiori, to prevent segregation to appear starting from a mixed configuration.

The explanation of why local coordination works is quite simple. It corrects the default of the WC mechanism by rendering highly segregated configurations less stable than before since if a red agent goes by mistake into the green area, he will, compared to the WC case, encourage a second red agent to join him by his vote. Hence the formation of nuclei is encouraged by local coordination. A second kind of mechanism to get out of segregated patterns is the advance of the frontier zone. On the opposite, the locally mixed patterns are more stable. Indeed, once an integrated pattern is reached, the co-proprietors tend to prevent the moves which would increase local segregation. For T 2 ≥ 10 -2 , the results are comparable to the previous ones: even if the size of the co-property is relatively less important, the LC mechanism still allows to break the segregated patterns and lead to locally mixed and ordered patterns. The size H of an agent's neighborhood being greater than previously, the typical size of these ordered patterns is also greater.

For T 2 = 10 -3 however, one can observe that U * is lower than in the T 2 = 10 -2 case (Fig 1 .13), and that the normalized similarity s * is negative for m ≤ 0.9, meaning that the agents have on average less similar neighbors than dissimilar ones. The correspond- ing snapshots of the stationary configurations on Fig 1 .15 show that the system ends in stripe-like globally ordered states. This result can be understood through the notion of externalities and lack of coordination. Indeed, when h/H 1, we can separate the voting co-proprietors whose neighborhood is close to the vacant cell envisaged by the moving agent and the neighbors living on a further ring. The respective neighborhoods of these two kind of neighbors are not spatially correlated, which means that the interest of these two kind of neighbors are clearly different. There are hence three kind of agents at play: the moving one, the inner ring of new neighbors (to which the voting agents belong) and all the other affected agents (the outer ring of new neighbors and the former neighbors). For finite values of T and T 2 → 0, the interest of the second group is in fact the sole taken into account in the LC mechanism. The interest of the potential movers is therefore practically not taken into account and some utility maximizing moves become impossible.

Conclusion

Schelling's model is characterized by the paradoxical result that, while the dynamics is governed by agents moving to improve their own utility, their moves lead to highly segregated configurations in which most of the agents are far from being fully satisfied.

Actually, as already argued by Zhang (2004b) and [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF], individual preferences for integrated environments may lead to segregated configurations because location choice by an agent affects her neighbors' utility. As stated by Zhang (2004b): The black curve corresponds to 'Without Coordination' simulations that have been performed using the same parameters.

"although nobody likes complete segregation, the residential pattern is very stable. Only moving across the color line by a considerable number of agents could disturb the segregation equilibrium, but nobody has incentive to do so because it causes a loss of [individual] utility. [...] Segregation is stable not because people like it, but because any individual who wants to change the situation unilaterally will have to go across the color line, which may not be the desirable thing to do from the individual's perspective. The failure of the system to escape complete segregation is similar to the phenomenon of "coordination failure" studied by economists in many other contexts. It is the agents' inability to move simultaneously that make them stuck in a situation nobody likes..."

We presented extended versions of Schelling-type models incorporating different kinds of coordination between the agents and examined stationary configurations based on simulations. We showed in a first mechanism that introducing partial coordination through a tax on the externality generated by individual moves is sufficient to break the gap between the agents' micro-motives and the emergent macro-behavior and therefore to break undesired segregative patterns. Moreover, we showed that it is not necessary for the tax to be equal to the externality to reduce segregation significantly. A tax equivalent to one fifth of the externality might well be sufficient. In a second mechanism, we assumed that the government is able to tax agents based on their majority status in the neighborhood. This again is a mechanism that allows to decrease segregation.

In a third mechanism, we introduced local coordination through a voting mechanism which involves only individual decisions and, unlike the tax mechanisms, does not require the intervention of a benevolent central authority. This model, remaining in the "individual decision" spirit of Schelling model, is shown to be sufficient to reach stationary configurations with a significantly higher collective utility than the no-coordination case. We hope that such an individualistic based coordination model can be seen as a valuable alternative to the coordination models presented in the literature, mostly based on affirmative action policies [START_REF] Dokumaci | Schelling Redux: An Evolutionary Dynamic Model of Residential Segregation[END_REF]. We also hope that these The theoretical relationship between individual preferences and aggregate configurations has however not been fully explored to date.

An early contribution was provided by Schelling, who proposed a model aiming at formalizing the aggregate consequences of individual preferences regarding the social environment [START_REF] Schelling | Models of Segregation[END_REF][START_REF] Schelling | Dynamic models of segregation[END_REF][START_REF] Schelling | Micromotives and Macrobehavior[END_REF]. The two basic ingredients of Schelling's "Dy-namic models of segregation" (1971) are an individual utility function that determines entirely the level of satisfaction enjoyed by an agent in a location and a dynamical rule that drives agents' location changes and therefore the evolution of the city configuration. Using an inductive approach, Schelling showed that if the preferences considered are such that an environment of more than 50% of own-group agents is highly preferred to a less than 50% of own-group environment, then the equilibrium configuration exhibits high levels of segregation, although there is no preference for segregation per se. Schelling 1971 paper is widely known thanks to this apparently paradoxical effect: mild individual preferences for own-group neighbors lead to a complete segregation at the global scale. However, a moment of reflection suffices to understand that, given the highly asymmetrical utility function used in this model, it could hardly lead to an integrated environment. Yet, later research showed that even a peaked utility function, that is, a function achieving its maximum for a perfectly mixed environment, can lead to a fully segregated equilibrium as soon as this function is asymmetric (Zhang, 2004b;[START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Barr | Segregation and strategic neighborhood interaction[END_REF].

Criticizing the realism of the interpretation of the emergence of segregation patterns as the result of a coordination problem (Zhang, 2004a,b); a physical analogue of Schelling's model [START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF]; the robustness of Schelling's results with respect to different definitions of individual utilities and/or environment [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF][START_REF] Fagiolo | Segregation in networks[END_REF]; the impact of heterogeneous agents and public policies (O'Sullivan, 2009); the exploration of tipping behaviors [START_REF] Zhang | Tipping and residential segregation: a unified Schelling model[END_REF]. 1 Most of this work relies on agent-based simulations.

Attempts to solve Schelling model analytically include [START_REF] Dokumaci | Schelling Redux: An Evolutionary Dynamic Model of Residential Segregation[END_REF]; [START_REF] Mobius | The Formation of Ghettos as a Local Interaction Phenomenon[END_REF]; [START_REF] Pollicott | The Dynamics of Schelling-type segregation models and a nonlinear graph laplacian variational problem[END_REF]; [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF]Zhang (2004aZhang ( ,b, 2010)). Zhang (2004aZhang ( ,b, 2010)) Furthermore, these three contributions only cover two specific utility functions.

In the present chapter, we build on Zhang (2004aZhang ( ,b, 2010)). We place We use this potential function to characterize the segregation level of the stationary configurations of the model for different utility functions, representing different degrees of preference for mixed environments. We examine successively (i) linear utility functions, with a continuous preference for segregated environments, (ii) Schelling's original utility function in which there is a mild preference for a mixed environment and (iii) asymmetrically peaked utility functions, according to which agents clearly exhibit a preference for a mixed environment. We show that there is no divergence between individual moves and social welfare with increasing linear utility functions, although segregation prevails in stationary configurations. We also show that even with the strongest preference for mixed environments -in the asymmetrically peaked utility function case -the model yields segregated stationary configurations. This case is also the one in which the divergence between the stationary segregation level and the optimal segregation level is the highest. These results complement those obtained by Zhang (2004b[START_REF] Zhang | Tipping and residential segregation: a unified Schelling model[END_REF] based on more restrictive hypotheses. Compared to this previous work, our analysis presents the advantage of remaining in Schelling's spirit by including vacant cells. While the condition on the utility functions for a potential function to exist with vacant cells restrict somewhat the range of utility functions that can be considered, all utility functions are valid in the limit case with no vacant cells.

In summary, our work provides a very general solution to Schelling's model with bounded neighborhoods, that encompasses previous work on this model and that paves the way to the analysis of many structures of preferences, for instance those based on empirical findings concerning racial preferences. In addition, a few simulation results are shown for illustrative purpose.

This chapter is organized as follows. The model features are presented in section 2.2. Section 2.3 defines the potential function concept and states our main result. The potential function is then used in section 2.4 to study the stationary configurations obtained for three different utility functions. In one of these cases, we are able to build a connection with a commonly used segregation measure. In section 2.5, we demonstrate the supplementary result that a potential function exists with continuous neighborhoods if and only if the utility functions are linear and discuss the differences between the bounded and continuous neighborhood cases. We also draw a parallel with general concepts of coalitional games, consider preferences of the agents for local amenities and analyse a case where a taxation is introduced against segregative behaviors.

A general dynamic model of segregation 2.2.1 The city and the agents

Our artificial city is a two-dimensional N xN square lattice with periodic boundary conditions, ie a torus containing N 2 cells. Each cell corresponds to a dwelling unit, all of equal quality. We suppose that a certain characteristic divides the population of this city into two groups of households that we will refer to as red and green agents. Each location may thus be occupied by a red agent, a green agent, or may be vacant. We denote by N V the number of vacant cells, and by N R and N G the number of respectively red and green agents. The parameter N thus controls the size of the city, the parameter v = N V /N 2 its vacancy rate, and the fraction

n R = N R /(N R + N G ) its composition.
We define a state x of the city as a N 2 -vector, each element of this vector labelling a cell of the N xN lattice. Each state x thus represents a specific configuration of the city. We note X the set of all possible configurations, the demographic parameters (N , v, n R ) being fixed.

Neighborhoods

Since Schelling (1969)'s work, two ways of conceiving the neighborhood of an agent have been developed and used in analytical and simulation models.

Bounded neighborhood models (Fig 2 .1a) describe cities divided into geographical units within which all agents are connected. The neighborhood of an agent is thus composed entirely and exclusively of the locations present in the same geographical unit as his own. In the following, when we refer to a bounded neighborhood model, we will implicitly assume that the city is divided in a set Q of blocks, each of which contains H + 1 locations, where H is a fixed integer that corresponds to the number of locations in an agent's neighborhood (hence, the relation

|Q|(H + 1) = N 2 must hold).
Obviously, the description of the city as a lattice with periodic boundary conditions is unnecessary in this case. Note that since some locations remain empty, the size H of the neighborhood of an agent can also be interpreted as the maximum number of neighbors an agent can have. For a given configuration x ∈ X of the city, we denote by R q (x) and G q (x) the number of red and green agents that live inside the block q ∈ Q. Taking into account that some locations of each block may remain empty, the {R q } and the {G q } must thus verify : As will be demonstrated in section 2.5.1, a potential function exists in the continuous neighborhood case only with very specific utility functions. In the following, we place ourselves, unless otherwise mentioned, in a bounded neighborhood case that allows us to consider a relatively broad range of utility functions. There is actually no argument in favor of bounded or continuous neighborhoods as far as the realism of the assumptions is concerned. Bounded neighborhoods can be thought of as reproducing the effects of the administrative divisions of real cities such as census areas or school districts.

q R q = N R (2.1) q G q = N G (2.2) (R q , G q ) ∈ E H+1 ≡ {(R, G), 0 ≤ R + G ≤ H + 1} (2.3)
Still, bounded neighorhoods present the drawback that the spatial arrangement of the neighborhoods is not taken into account: each neighborhood is considered independently without any connection to other neighborhoods. This is the checkerboard issue, well known in the literature on residential segregation measures. We present in section 2.5.1 some simulation results illustrating the impact of the neighborhood description on the forms of segregation at the city scale and a formal analysis showing how connections between neighborhoods, that make agents close to neighborhoods boundary also consider the composition of the contiguous neighborhood, can be introduced in our framework.

Agent's utility function

Each agent has a utility level which depends only on his neighborhood composition. Let us consider an agent whose neighborhood is composed of R red agents, G green agents and V vacant cells. Since R + G + V = H, one needs two independent parameters to describe the composition of the agent's neighborhood. In all generality, we can thus write the utility of an agent for example as a function of R and G. Like most models of the literature, we assume for simplification that agents of a same group share the same utility function. 2

2 See O'Sullivan (2009) for a treatment with heterogeneous agents.

CHAPTER 2. AN ANALYTIC SOLUTION

57

Without any loss of generality, we write the utility of an agent as:

u = u R (R, G)
for a red agent with R red and G green neighbors,

u = u G (R, G)
for a green agent with R red and G green neighbors.

The utility of an agent is thus a function of E H → R. More specifically in the case of a bounded neighborhood description, we will have :

u = u R (R q -1, G q )
for a red agent living in block q, u = u G (R q , G q -1) for a green agent living in block q.

In order to facilitate the comparison of different utility functions, utility in the examples presented below is such that a zero utility level denotes a complete dissatisfaction of the agent and a utility of one denotes complete satisfaction.

We also introduce a notation in order to characterize the level of utility on the global (city) scale:

U (x) = k u k (2.4)
where u k is the utility of agent k and U (x) denote the collective utility of a configuration

x.

A behavioral rule: the logit dynamical rule

The core of dynamic segregation models is that agents are given opportunities to move to increase their individual utility. Once the static description of the model is specified, one must add a dynamic rule that governs these moves. In the following, the city configuration evolves according to an iterative process. At the first iteration, an initial configuration is randomly chosen. At each iteration, one agent and one vacant cell are picked at random. 3 The picked agent then chooses to move to that vacant cell with a probability P r{move} that depends on the utility gain ∆u he would achieve if he was to move, as follows:

P r{move} = 1 1 + e -∆u/T (2.5)
where T > 0 is a fixed parameter.

Eq. 2.5 represents a logit choice function as developed in [START_REF] Mcfadden | Conditional Logit Analysis of Qualitative Choice Behavior[END_REF] as the outcome of a random-utility model. In such a model, it may happen that an agent takes a utility-decreasing move, either because he is making a mistake or because of a lack of information. The scalar T is used to determine the relative importance of the random part with respect to the deterministic part of the random utility function. The probability for an agent to take a utility-decreasing move drops down as T → 0 and the described rule thus converges to the non-strict best response rule. For any finite T > 0, the agents choose non-best replies with a non-zero probability, but actions that yield smaller payoffs are chosen with smaller probability. This kind of perturbed bestresponse dynamics has been developed in [START_REF] Young | Individual Strategy and Social Structure: An Evolutionary Theory of Institutions[END_REF] in the context of evolutionary games. Here, neighborhood's composition is supposed to be the main determinant of agents' actions : we restrict our analysis to the case of low values of T .

Compared to a best-response behavioral rule (where the agents move if and only if they strictly improve their utility), the logit rule allows for some fluidity in the model in the sense that blocked states are avoided [START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF]. Besides, it provides a strong analytical framework to Schelling model. Obviously, it implies that the probability that the state at the t th iteration x t is equal to a given state x only depends on the state at the previous iteration x t-1 :

Pr(x t = x|x t-1 , . . . , x 1 , x 0 ) = Pr(x t = x|x t-1 ) (2.6)
The dynamic rule thus yields a finite Markov process.

It is then easy to figure out that the Markov chain describing our system is irreducible (since T > 0 each imaginable move has a non-zero probability to happen and it is thus possible to get to any state from any state), aperiodic (given any state x and any integer k, there is a non-zero probability that we return to state x in a multiple of k iterations)

and recurrent (given that we start in state x, the probability that we will never return to x is 0). These three properties ensure that the probability to observe any state x after t iterations starting from a state y converges toward a fixed limit independent of the starting state y as t → ∞.

In other words, for each set of parameters and dynamic rule, there exists a stationary distribution

Π : x ∈ X → Π(x) ∈ [0, 1] , x∈X Π(x) = 1 (2.7)
which gives the probability with which each state x will be observed in the long run.

Clearly, for T → ∞, the randomness introduced in the dynamical rule prevails and the stationary distribution is just a constant. Similarly, for any finite T > 0, our dynamical system (the city) evolves toward an attractor composed of a subset A of X.

It follows that any measure M -such as the global utility U -performed on the state space X will in the long run fluctuate around a mean value

M ∞ = x∈A Π(x)M(x).
These mean values may depend on the intensity of the noise T , but the amplitude of the fluctuations decreases as T → 0.

In the following, we refer to two states x and y as immediately communicating states

(ICS) if we can switch from state x to state y by moving one single agent. We also note ∆ xy u the variation of utility of this agent induced by this particular move and P T xy the probability to be in state y at a given iteration if the system was in state x at the previous iteration. According to the dynamic rule presented above, one has:

P T xy = γ(1 + e -∆xyu/T ) -1 if
x and y are ICS (2.8)

P T xy = 0 if x and y are not ICS (2.9)
where the parameter

γ = 1/(N V (N R + N G )) = 1/(v(1 -v)N 4
) takes into account the probability to pick the right agent and the right vacant cell that allow to pass from x to y. P T thus corresponds to the probability transition matrix for a fixed T and the stationary distribution Π is by definition the unique normalized function defined on X that verifies for all x ∈ X:

y P T yx Π(y) = Π(x) (2.10) 2.
3 Model solving with a potential function

Definitions and properties

Following Zhang (2004a,b), we place our model in the context of evolutionary game theory and use the concept of potential function to solve it. In game theory, the concept of potential function was proposed by [START_REF] Monderer | Potential games[END_REF]. A game is said to be a potential game if the incentive of all players to choose their strategy can be expressed in one global function, which is called the potential function. In our context, the definition of a potential function takes the rather simple following form: The main property of a potential function is to link the variation of a purely individual function (the utility of the moving agent) to the variation of a global function defined on the space X of all possible configurations and characterizing the city configuration. The ensuing lemma points out even more the value of the potential function as an analytical tool.

Definition 1. Let F : x ∈ X → F(x) ∈ R

Lemma 1

If F is a potential function of the system, then the stationary distribution Π is such that for any configuration x:

Π(x) = e F (x)/T z∈X e F (z)/T
(2.11)

It follows that for T → 0, the stationary configurations are those that maximize F.

Proof. The following proof follows the classical argument presented in [START_REF] Young | Individual Strategy and Social Structure: An Evolutionary Theory of Institutions[END_REF].

Let π be the function defined as π :

X → [0, 1]; x → π(x) = e F (x)/T / z e F (z)/T .
The first step of the proof consists in checking that π satisfies the detailed balance condition:

π(x)P T xy = π(y)P T yx (2.12)
If x and y are two different and not communicating states, equality 2.12 is trivially satisfied since in this case P T xy = P T yx = 0. If x = y, the detailed balance condition is also trivially verified. In the case where x = y and x and y are two communicating states, one has:

π(x)P T xy = π(x)γ 1 1 + e -∆xyu/T = π(x)γ 1 1 + e -(F (y)-F (x))/T = π(x)γ e F (y)/T e F (x)/T + e F (y)/T = π(y)γ e F (x)/T e F (x)/T + e F (y)/T = π(y)γ 1 1 + e -(F (x)-F (y))/T = π(y)γ 1 1 + e -∆yxu/T = π(y)P T yx recalling that γ = 1/(N V (N R + N G )) = 1/(v(1 -v)N 4 ).
Hence the detailed balance condition is always verified and

x∈X π(x)P T xy = x∈X π(y)P T yx = π(y) x∈X P T yx = π(y) • 1 = π(y) , (2.13)
which defines π as a stationary distribution of the process. Because the Markov chain is finite and irreducible, it has a unique stationary distribution. Hence, for each state

x, Π(x) = π(x) = e F (x)/T / z e F (z)/T .
Define then X F as the subset of X of the states that maximize the potential function F:

X F = {y, ∀x ∈ X F(y) ≥ F(x)} (2.14)
The second part of the lemma can now be proved as follows: for two states x and y of X F , we will have F(x) = F(y) and therefore Π(x)/Π(y) = e [F (x)-F (y)]/T = 1, which means that two states that strictly maximize F are observed in the long run with the same probability; for two states x ∈ X \ X F and y ∈ X F , we will have F(x) -F(y) ≤ 0 and therefore Π(x)/Π(y) = e [F (x)-F (y)]/T → 0 as T → 0. This means that for T → 0, the probability to observe a state that does not maximize the potential function F becomes in the long run infinitesimally small.

The potential function is hence a very powerful analytical tool. First, it establishes a relation between individual changes in utility and a global characteristic of the city configuration. Second, because stationary configurations can be defined as those maximizing the potential function for low noise levels, the existence of a potential function allows to qualify analytically stationary configurations. The fact that the knowledge of ∆u is sufficient to say something on the global level is highly non-trivial since, in particular, there is no way to determine the externalities produced by the move of an agentie the variation of the utility of his former and new neighbors -only from the knowledge of the utility variation of the moving agent. Note that a low level of T is required for the maximum of the potential function to be achieved at stationary configurations.5 Still,

T has to remain strictly positive to avoid blocked states.

Main result: existence of a potential function

It is possible, using the potential function, to examine analytically the outcome of the model for different utility functions, representing different degrees of preference for mixed environments. To do so, two questions are to be answered first: given any pair of utility functions (u R , u G ), does a potential function exist and can we compute it? Reciprocally, given a potential function, can we find a pair of utility functions (u R , u G ) that can be translated into this specific potential function?

We show in the following that in the context of bounded neighborhoods, one can achieve an analytical resolution of the model under a rather mild condition. Let us begin with some definitions.

Definition 2. Let U be the set of pairs of utility functions (u R , u G ) that verify, for all (R, G) ∈ E H , the following condition:

u R (R, G) -u R (R, G + 1) = u G (R, G) -u G (R + 1, G) (2.15)
Condition 2.15 only imposes that if a block contains R + 1 red agents and G + 1 green agents, the utility gain a red agent would achieve if a green agent left must be the same as the utility gain a green agent would achieve if a red agent left. The results in the following apply to pairs of utility functions verifying this condition. As we show below, this condition is not strongly restrictive from a theoretical viewpoint.

Definition 3. Let F be the set of aggregate functions of the form

F(x) = q∈Q F (R q , G q ),
where F is an intermediate function defined on the set E H+1 of all possible numbers of red and green agents that can be present in a block.

The main result of this chapter consists in the following proposition:

Proposition 1 Each aggregate function F ∈ F : x → F(x) = q∈Q F (R q , G q ) is a potential function
to which corresponds at least a one pair (u R , u G ) of utility functions of U that can be expressed as:

u R (R, G) = F (R + 1, G) -F (R, G) u G (R, G) = F (R, G + 1) -F (R, G) (2.16)
Reciprocally, for each pair of utility functions (u R , u G ) of U, there exists one corre-

sponding potential function F [u R ,u G ] ∈ F. This function can be expressed through the functional F u R ,u G : E H+1 → R -such that F [u R ,u G ] (x) = q∈Q F [u R ,u G ] (R q , G q ) -which is defined for all (R, G) ∈ E H+1 by: b F [u R ,u G ] (R, G) = R r=1 u R (r -1, 0) + G g=1 u G (R, g -1) (2.17) = R r=1 u R (r -1, G) + G g=1 u G (0, g -1) (2.18)
a Since the definition of the potential function makes only intervene its variation, F can be defined up to an additive constant. Similarly, a utility function can also be defined up to a constant. All the formula in this insert are written with the convention u(0, 0) = F (0, 0) = F (0, 1) = F (1, 0) = 0. For more details, see the proof in A.1.

b Our notation assumes that a sum is null whenever its upper bound of summation is inferior to its lower bound of summation.

Proof. See Appendix A.1.

Proposition 1 states that it is always possible to define a function F defined at the neighborhood level corresponding to the variation of utility of a moving agent, but only a pair of utility functions verifying condition 2.15 allows this function to be pathindependent and therefore uniquely defined for any given configuration. Reciprocally, for any pair of utility functions verifying condition 2.15, the game has a potential function that is maximized at stationary configurations, and this function is the sum of neighborhood-level intermediate components. As Eq 2.17 shows, the intermediate component of the potential function corresponds to the sum of utilities of the agents arriving in succession in the block. This sum is calculated starting from an empty block, agents being introduced one by one, first the red ones and then the green ones. As Eq 2.18

shows, the same sum is obtained if green agents are introduced first and red agents after. Before giving a more general interpretation in section 2.3.3, it is useful to give the following corollary, aimed at showing that utility functions verifying condition 2.15 can be given a convenient formulation in which interactions between the two groups are expressed through the same function in the two utility functions, thus giving a more general formulation for the potential function.

Corollary 1

Any pair of utility functions (u R , u G ) belonging to U can be written:

u R (R, G) = ξ R (R) + G-1 g=0 ξ(R, g) (2.19) u G (R, G) = ξ G (G) + R-1 r=0 ξ(r, G) (2.20)
where ξ R and ξ G are arbitrary functions of {0, 1, .., H} → R and ξ is an arbitrary function

of E H → R.
For each pair of utility functions (u R , u G ) verifying 2.19 and 2.20, thanks to Eq. 2.17, one can rewrite the general form of the potential function

F [u R ,u G ] as: F(x) = const + q Rq-1 r=0 ξ R (r) + Gq-1 g=0 ξ G (g) + Rq-1 r=0 Gq-1 g=0 ξ(r, g) (2.21)
Proof. For any pairs of utility functions (u R , u G ), one can define ξ R and ξ G , two functions of {0, 1, .., H} → R and ξ RG and ξ GR , two functions of

E H → R by ξ R (r) = u R (r, 0) ξ G (g) = u G (0, g) ξ RG (r, g) = u R (r, g + 1) -u R (r, g) ξ GR (r, g) = u G (r + 1, g) -u G (r, g)
for all 0 ≤ r ≤ H and 0 ≤ g ≤ H. By definition, one can then write the utility functions as

u R (R, G) = ξ R (R) + G-1 g=0 ξ RG (R, g) (2.22) u G (R, G) = ξ G (G) + R-1 r=0 ξ GR (r, G) (2.23) for all (R, G) ∈ E H .
The condition given by Eq. 2.15 is obviously equivalent to ξ RG = ξ RG ≡ ξ, which proves Corollary 1.

Interpretation

We propose here first an interpretation of condition 2.15 and then of the form of the potential function. Proposition 1 ensures that there exists a potential function for any pair of utility functions verifying condition 2.15. In its original form, this condition says that there is a symmetry in the externalities generated by green agents on red agents and by red agents on green agents: starting from a given neighborhood composition, the variation in utility produced by the departure of an agent of the other type must be the same for the two categories. This can be seen as rather limiting, as some real world situations do not conform to this condition. For instance, well-known surveys on the appreciation by white and black individuals of their preferred residential environment show that blacks are in favor of integrated neighborhoods, whereas whites favor all-white neighborhoods [START_REF] Farley | Chocolate city, vanilla suburb: will the trend toward racially separate communities continue?[END_REF]see Farley et al., 1997 for recent figures).

However, condition 2.15 covers more general types of preferences when the rate of vacant cells is low. Namely, in the limit of a very low vacancy rate, there is no vacant cells in most of the blocks, ie in these blocks the relation R q + G q = H + 1 holds.

Hence, one only needs one parameter among (R q , G q , V q ) to define a utility function and considering for instance that an agent's utility only depends on his number of similar neighbors is sufficient to describe all possible cases. This can be done by taking ξ ≡ 0 in Eq. 2.19 and Eq. 2.20, while keeping the functions ξ R and ξ G independent and free.

In other words, in the limit of no vacant cells, each agent arriving in a neighborhood receives a utility that is fully determined by the number of like-neighbors. Therefore, the order in which the agents settle in the neighborhood does not matter and the condition for having a potential function holds. The set U hence describes all possible pairs of utility functions in the limit v → 0. It follows also that condition 2.15 holds for all pairs of utility functions in situations where vacant cells are considered in the same way as unlike-color neighbors. Note also that condition 2.15 applies to the utility functions considered in Zhang (2004a), where preferences over neighborhoods are determined by the number of like-agents only and the symmetric effect of unlike-color neighbors on each type of agent emerges as the result of the determination of housing prices by densities.

In its original form, the potential function F can be interpreted as the sum of the incentives the agents had (when they settled) to move into the neighborhood where they are located. Indeed, if x(t) denotes the state of the city at iteration t, then the potential can be rewritten as

F(x(t)) -F(x(0)) = t t =1 ∆ x(t -1)x(t ) u (2.24)
where ∆ x(t -1)x(t ) u = 0 by definition if no move happens at iteration t and where we can take F(x(0)) = 0 since the potential is defined up to a constant. Conversely, the potential function F can also be viewed as the minimum utility level each agent would require to accept quitting his neighborhood. As such, it represents, in the case T → 0, the stability of the configuration x: the higher the potential function, the smaller the incentives for agents to move.

To interpret further the potential function, it is worth noting that condition 2.15 can also be written as follows:

u R (R, G) + u G (R + 1, G) = u G (R, G) + u R (R, G + 1) (2.25)
which means that starting from any initial composition of a block, the sum of utilities of a red agent and a green agent entering successively in this block is the same whatever the order in which they enter. This expression stresses that, under condition 2.15, the value of function F in a given neighborhood q does not depend on the particular path of events that lead to the composition of this neighborhood. This is also particularly clear in the form of condition 2.15 given in corollary 1. It hence follows that the potential function F, which is the sum of the F intermediate functions, is independent of the particular order in which the agents arrived in the neighborhoods.

Hence it is also possible to define F as the average over all the possible ways of ordering the agents, which will be shown formally in section 2.5.2.

Segregation for different levels of preference for mixed environments

The main property of the potential function obtained in the previous section is that it reflects both the macro and micro scale. On one hand, F is an aggregate function defined at the city level which only depends on the number R q and G q of red and green agents in each block. On the other hand, F also keeps tracks of the individual level since it corresponds to a sum of the utility differences generated by individual moves.

When the stationary states are reached in the case T → 0, F is maximized, which means that no agent can strictly improve her utility by moving. The potential function can now be used to assess the outcomes of our location model for different utility functions, representing different degrees of preference for mixed environments, as far as these functions verify condition 2.15. We examine successively (i) linear utility functions, with a continuous preference for segregated environments, (ii) Schelling original utility function in which there is a mild preference for a mixed environment and (iii) an asymmetrically peaked utility function, according to which agents exhibit a strict preference for a mixed environment.6

Linear utility functions

We consider here utility functions that exhibit a monotone effect of the number of samecolor neighbors on utility, through linear utility functions. Zhang (2004a) proposes an analytical solution of a dynamic model of segregation with a linear utility function and

shows that the halved sum of individual utilities is a potential function of the game thus defined. In this section, we show that Proposition 1 allows to find similar results for all linear utility functions verifying condition 2.15 in the context of bounded neighborhoods.

Suppose that u R and u G are expressed as:

u R (R, G) = aR + bG u G (R, G) = bR + dG (2.26)
where a, b, d are constant parameters.7

One can easily verify that this particular pair of utility functions verifies condition 2.15 and compute the corresponding potential function:

F(x) = 1 2 q (aR q (R q -1) + dG q (G q -1) + 2bR q G q ) (2.27)
One can rewrite this potential function as:

F(x) = b - a + d 2 ρ RG (x) - a 2 ρ RV (x) - d 2 ρ GV (x)
(2.28) with:

ρ RG = q R q G q the number of red-green pairs of neighbors,

ρ RV = q R q (H + 1 -R q -G q )
the number of red-vacant pairs of neighbors and Turning now to the link between segregation of the stationary configurations and collective utility, it is useful, using proposition 1, to write the potential function as follows:8

ρ GV = q G q (H + 1 -R q -G q ) the
F(x) = 1 2 q (aR q (R q -1) + dG q (G q -1) + 2bR q G q ) = 1 2 q (R q u R (R q -1, G q ) + G q u G (R q , G q -1)) = 1 2 U (x)
With this choice of utility functions, the potential function is thus proportional to collective utility and therefore lemma 1 ensures that, for low values of T , the stationary configuration maximizes collective utility. Reciprocally, one can verify (see proof in A.2)

that if we want the potential function to be proportional to the collective utility, so that states that maximize the potential function also maximize collective utility, then the constant of proportionality is necessarily 0.5 and the pair of utility functions must take the form displayed in Eq. 2.26 (up to a constant).

To sum up, the linear utility functions as defined in 2.26 lead to segregated or mixed states depending on the values of the parameters. However, in all cases, there is no divergence between stationary configurations and the optimum: these utility functions are such that utility-improving moves also improve collective utility.

Schelling utility function

Suppose that the agents compute their utility with Schelling utility function, which is equal to 1 if their fraction of similar neighbors is superior or equal to 0.5, and equal to 0 otherwise. This utility function can be expressed in terms of the number of red and green neighbors as follows:

u R (R, G) = Θ(R -G) = 1 2 (1 + |R + 1 -G| -|R -G|) u G (R, G) = Θ(G -R) = 1 2 (1 + |R -1 -G| -|R -G|) (2.29)
where Θ is the Heaviside function defined by: Θ

(x) = 0 if x < 0 and Θ(x) = 1 if x ≥ 0.
It is easy to figure out that this particular pair of utility functions respects condition 2.15, and is therefore in the set U. Indeed, the form of the symmetric externality produced by a new unlike-color neighbor is the following:

u R (R, G + 1) -u R (R, G) = |R -G| - 1 2 (|R -G -1| + |R -G + 1|) (2.30) = u G (R + 1, G) -u G (R, G) (2.31)
It is possible to compute the potential function rather directly thanks to its interpretation, as the sum of the utility of the agents being introduced one by one in the city, this sum being independent of the precise order of introduction of the agents. To do so for a given configuration x ≡ {R q , G q }, let us consider that we introduce in each block first the agents in majority (ie the red ones if R q > G q , the green ones if G q > R q , either the red or the green ones if R q = G q ) and second the agents in minority. Each of the first agents has a utility of 1 as he settles in the city while each of the other minority agents has a zero utility when he settles. 9 Hence it is straightforward to write the potential function as: 10

F(x) = const + q∈Q max(R q , G q ) = const + q∈Q 1 2 R q + G q + |R q -G q | = const + 1 2 q∈Q |R q -G q |
One can verify that the same expression can be found using relation 2.17 (see A.3), the computation being in this case more formal than what we present here.

The reader can recognize an expression well-known to scientists working on residential segregation. This potential function is indeed a linear form of the Duncan and Duncan dissimilarity index, which in the case where the total number of red and green agents in the city are equal [START_REF] Duncan | A methodological analysis of segregation indexes[END_REF]. To the best of our knowledge, an analytical connection between the two "historical" works of Schelling and Duncan and Duncan on segregation has never been found before.

(N R = N G = N ), is written as D(x) = 1 2 q |R q /N R -G q /N G | = 1 2N q |R q -G q | (Duncan
It is worth here investigating the link between the potential function and collective 9 This example shows that to compute the potential function corresponding to a given pair (uR, uG) of utility functions, it may be worth to think ahead of a practical order of introduction of the agents. The computation of F is indeed easier and bears more meanings with an appropriate order.

10 Notice that in this particular example, we do not use the convention u(0, 0) = 0. See A.3 for details.

utility. The collective utility in a neighborhood q is:

U q = 1 2 (R q + G q + |R q -G q |) if R q = G q U q = R q + G q if R q = G q
The potential function can therefore be written:

F(x) = const + U (x) - q|Rq=Gq 1 2 R q + G q (2.32) (2.33)
This expression shows that the configuration that maximizes F does not correspond to the maximum collective utility. The divergence is due to the existence of perfectly mixed neighborhoods. To be more specific, let us compare two configurations differing by the existence, in configuration x 1 , of two perfectly mixed neighborhoods with K < (H +1)/2 agents of each color, that are changed to segregated ones in configuration x 2 due to the exchange of two agents of different color. The difference in the potential function between the two configurations is only due to the change affecting these two neighborhoods. It is written:

∆F = F(x 2 ) -F(x 1 ) = 2 (2.34)
because each of the two neighborhoods gained one agent of one color and lost an agent of the other color. The difference in collective utility consists of the loss of utility of the agents who are now in minority in their neighborhood, that is:

∆U = U (x 2 ) -U (x 1 ) = -2(K -1) = 2 -2K (2.35)
Comparing the difference in the potential function and in collective utility between these two configurations, one observes that decreasing the number of perfectly mixed neighborhoods decreases collective utility (due to the loss of those who are in the minority in the new configuration) while increasing the value of the potential function. This is because the two moving agents have still a utility of 1 in their new neighborhood, while they clearly exert negative externalities on the agents of the group which is now in minority in this neighborhood. Stationary configurations will tend therefore to exhibit few perfectly mixed neighborhoods, at the expense of collective utility.

Our analysis based on Schelling original utility function shows thus two points. First, it provides an analytical demonstration of Schelling result, that this pair of utility func-tions leads to segregated stationary configurations. Second, it sheds light on the source of the discrepancy between the collective utility of stationary configurations and the maximum utility that could be attained with a perfectly mixed environment.

Asymmetrically peaked utility functions

In this section, we apply our analytical framework to asymmetrically peaked utility functions displayed on Fig. 2.3, that have been studied in [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF].

We will see that our potential function provides a criterion for global segregation or for integration. These utility functions are particularly appealing for demonstrating Schelling's intuition, that the aggregate outcome of the game can run against individual preferences. Indeed, these functions consider a case where agents strictly prefer perfectly mixed neighborhoods against any level of segregation. In the following, we place ourselves in the case ξ ≡ 0 where the utility of each type of agents can be described entirely by the number of like-color agents. This choice permits us to write analytical results more easily. It can furthermore be understood as the limit case v → 0 For simplicity, we suppose that the number H of possible neighbors of an agent is even. The asymmetrically peaked utility functions can then be written:

u R (R, G) = ξ ap (R) u G (R, G) = ξ ap (G) with: ξ ap (s) = 2s/H if s ≤ H/2 ξ ap (s) = 2 -m -2(1 -m)s/H if s > H/2
with m a fixed parameter (see Fig. 2.3).

Using Θ the Heaviside function defined by: Θ(x) = 0 if x < 0 and Θ(x) = 1 if x ≥ 0, this utility function can also be written:

ξ ap (s) = 2 s H -(2 -m) 2 H s - H 2 Θ s - H 2
For a given state x of the city, simple calculations show that the collective utility can be written as

U (x) = q Ũ (R q ) + Ũ (G q ) , with Ũ (S) = 2 S(S -1) H -(2 -m) 2S H S -1 - H 2 Θ S -1 - H 2 , ∀0 ≤ S ≤ H (2.36)
Likewise, the corresponding potential function is

F(x) = const + q F (R q , G q ) = const + q F (R q ) + F (G q )
, where

F (S) = S-1 s=0 ξ ap (s) = (S -1)S H - 2 -m H S -1 - H 2 S - H 2 Θ S - H 2 -1 = 1 2 Ũ (S) + (2 -m) S -1 - H 2 Θ S -1 - H 2 (2.37) Proof. See A.4.
This expression implies once again that the potential F and the collective utility U are linearly related when the individual utility is linear (case m = 2). The lower m, the less linear the individual utility and the greater the divergence from the F = const+U/2 relation. Thus, relation 2.37 puts forward the crucial role of the asymmetric parameter m which is the driver of the moves that produce externalities.

To be more specific, let us compare two configurations x 1 and x 2 , which differ only in the repartition of H+1 red and H+1 green agents in two neighborhoods. In configuration

x 1 , the repartition is rather homogeneous, with H/2 + 1 red and H/2 green agents in the first neighborhood and H/2 red and H/2 + 1 green agents in the second one. In configuration x 2 , the repartition is more segregated, with H/2 + 1 + K red and H/2 -K green agents in the first neighborhood and H/2 -K red and H/2 + 1 + K green agents in the second one, K ∈ {0, 1, ..., H/2} being an integer determining the level of segregation.

The difference in the potential function between the two configurations is only due to the change affecting these two neighborhoods. It is written:

∆F = 2 F (H/2 + 1 + K) + 2 F (H/2 -K) -2 F (H/2 + 1) -2 F (H/2) = 2m H K(K + 1) (2.38) Proof. See A.4.
As could be expected, ∆F increases with m, which means that the segregated configuration is more probable and stable than the mixed one as the asymmetry toward like-agents is stronger. It also increases with K, which means that for a given m a highly segregated block is more probable than a slightly segregated one. More importantly, a perfectly segregated block will be more probable than a perfectly mixed one if and only if relation 2.38 is positive, ie if and only if m > 0.

The corresponding difference in collective utility consists of the loss of all the agents.

It can be written:

∆U = 2 Ũ (H/2 + 1 + K) + 2 Ũ (H/2 -K) -2 Ũ (H/2 + 1) -2 Ũ (H/2) = 4K m 1 2 + K + 1 H -1 (2.39) Proof. See A.4.
It is obvious that increasing segregation also increases collective utility as soon as

m ≥ 1. It is straightforward to verify based on equation 2.39 that ∆U ≥ 0 ⇔ m ≥ m * = H(H + 1) -1 . 11
Our analysis provides a microscopic criterion allowing to predict a global outcome.

For 0 < m < m * 1, complete segregated configurations will be obtained at the expense of the collective utility and for m < 0, perfectly mixed configuration will be obtained.

These results hold of course in the limit of a low noise level (T → 0). The outcome for values of m higher than 0.2 illustrates the paradox of Schelling model: large segregative patterns appear although they absolutely do not maximize the utility of most agents, as most of them are stuck inside an homogeneous area with a utility of 0.5. In this case, one of the key element driving segregation is the asymmetry of this utility function, ie, the fact that even if the agents have a strict preference for mixed environments, they still prefer to belong to the majority group instead of being in minority, as was already shown in [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF]. In particular, with the asymmetrically peaked utility function, a red (green) agent may move for example from a 49% red (green) neighborhood to a 51% red (green) neighborhood because it slightly increases her utility. Meanwhile, this move is likely to decrease the utility of the previous and new neighbors and therefore decrease the collective utility level. Both of these factors imply that a highly-segregated configuration is necessarily very stable. Indeed, once the city is divided into homogeneous areas, a red agent will have no incentive to go from the red area to the green one, because his utility would drop from 0.5 to 0.12 2.5 Discussion, limits and extensions

In this section, we first motivate the bounded neighborhood assumption with a supplementary result in the continuous neighborhood case and show how our model can be extended to get closer to a continuous neighborhood definition. We then show that the potential function of our model can be interpreted in terms of the Shapley value of a coalitional game, which allows us to relate our results to broader issues of game theory.

In a third development, we use the analytical framework to investigate some extensions of the model, such as different agents' preferences and an analysis of taxation.

Bounded vs continuous neighborhoods

Most papers based on simulations as well as those presenting analytical results for particular cases [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF]Zhang, 2004a) deal with continuous neighborhoods.

In this paragraph, we discuss the differences between bounded and continuous neighborhoods.

Analytic limitations in the continuous neighborhood case

Our previous analysis can be extended by considering continuous neighborhoods. In the following proposition, we establish the important result that, in the context of continuous neigborhoods, a potential function only exists with linear utility functions.

Proposition 2

When using a continuous neighborhood description, a potential function exists if the agents' individual utility functions are bilinear functions of the form

u R (R, G) = u R (0, 0) + aR + bG u G (R, G) = u G (0, 0) + bR + dG (2.40)
where a, b, d are three real constants. In this case, a potential function F can moreover be written as A way to handle this issue in the continuous neighborhood case is to consider linear utility functions. For these, the generated externalities do not depend on the neighbor's neighbors, because linearity implies that the newcomer generates the same change in utility on his neighbors, independently of their initial situation; the same holds for the neighbors he leaves. For non linear utilities, a potential function can exist only in the bounded neighborhood case.14

F : x → F(x) = const + U (x)/2.

Simulations and real segregation measures

Let us now investigate the differences between bounded versus continuous neighborhoods in the general case. Based on the simulations in the case of the asymmetrically peaked utility function, the snapshots displayed on the right panel of The two descriptions produce a different "transition range" (roughly 0.1 ± 0.05 in the bounded neighborhood case versus 0.25 ± 0.05 in the continuous neighborhood case).

The strongest difference between the two cases lies in the patterns observed at the city scale: as there are no connections across neighborhood boundaries in the bounded case, red and green neighborhoods are observed side by side. In the continuous neighborhood case on the contrary, segregated patterns appear at the city scale. However, these simulations suggest that the local degree of segregation does not change with the definition of neighborhoods that is used.

The same concern was raised in the residential segregation literature, where the most traditional segregation measures consider a bounded neighborhood definition with no connections between blocks [START_REF] Duncan | A methodological analysis of segregation indexes[END_REF]. To remedy this issue, spatial measures of segregation have been developed, in which the spatial arrangement of neighborhoods intervenes [START_REF] Morrill | On the Measure of Spatial Segregation[END_REF][START_REF] Reardon | Measures of spatial segregation[END_REF][START_REF] Wong | Formulating a general spatial segregation measure[END_REF].

This can be done either by taking the contiguity between neighborhoods into account, by integrating a distance matrix between all neighborhoods with a distance-decay function, thus considering that all the city locations matter when measuring potential contacts between groups in a specific location, or by using point locations instead of areal tracts.

Drawing the parallel with the bounded and continuous neighborhood segregation models, the last option would correspond to a continuous neighborhood definition.

From this viewpoint, the main drawback of our segregation model is that an agent is not affected by the composition of the blocks next to his own, which may seem unrealistic and explains why red and green neighborhoods are observed side by side in stationary configurations. Referring to the segregation measure literature, this could be solved by accounting for the contiguity between blocks. In the following, we propose a variation of our bounded neighborhood model which includes transitivity between blocks while maintaining the existence of a potential function.

Bounded neighborhood with spatial transitivity

The bounded neighborhood formulation is based on a given partition (let us call it Q 1 ) of the city lattice into blocks, as shown on

q 1 ∈ Q 1 and q 2 ∈ Q 2 he is living in and the corresponding utilities u R,i = u R (R q i -1, G q i )
where

(i ∈ {1, 2}) (resp. u G i = u G (R q i , G q i -1)). Two potential functions F 1 and F 2
where F i = F({R q i , G q i }) can similarly be assigned to the two partitions. Let us now finally define a model encompassing both partitions. The utility u of an agent is taken as the sum u 1 + u 2 corresponding to his utility in both partitions.

It is straightforward to verify that the analytical properties of our model hold in this larger description and that the states of the city can be characterized by the potential function F 12 = F 1 + F 2 , whose maxima correspond to the stationary states of the city. Moreover, the fact that partitions overlap implies spatial transitivity between blocks of a given partition. Indeed, suppose that agents compute their utility with the asymmetrically peaked utility function, as in section 2.4.3. We showed earlier in the model with one partition that for m > 0, stationary states maximizing the potential function correspond to states where each block is either completely red or completely green, while mixed blocks were dynamically unstable. It is possible to show that in the two partitions model, the same result holds because the simultaneous maximization of the two potential functions can be achieved by minimizing the number of mixed blocks, which leads to a gathering of blocks of the same color, as illustrated on Fig 2.5b.

A coalitional game formulation

The formulation of Schelling model in the context of evolutionary game theory can yield other fruitful results. The following corollary gives a general form of the potential function that can be interpreted in terms of the Shapley value of a non cooperative coalitional game [START_REF] Shapley | A Value for n-Person Games[END_REF].

Corollary 2

The potential function F can be written as the sum of the following intermediate functions F :

F [u R ,u G ] (R, G) = 0≤r≤R, 0≤g≤G (r,g) =(0,0) R r G g (r + g -1)! (R + G -r -g)! (R + G)! ν(r, g) (2.41) where ν(r, g) = r u R (r -1, g) + g u G (r, g -1) (2.42)
is the collective utility in a block having r red and g green agents.

Let us consider a coalitional game defined by the set of the R q + G q agents present in block q along with a coalition worth equal to the sum of their utilities

ν q (R q , G q ) = R q u R (R q -1, G q ) + G q u G (R q , G q -1)
, that is the collective utility at the neighborhood level. The sum of the potential functions of the |Q| coalitional games defined on the |Q| blocks is equal to the potential function F.

Proof. The form of F given in expression 2.41 is derived in A.1. Then, acknowledging that in a neighborhood with R q + G q agents, there are R r G g possible coalitions having g green and r red agents and applying the formula of the potential function of the Shapley value derived in [START_REF] Hart | Potential, value and consistency[END_REF], one obtains exactly the formula of the potential function given in 2.41. Hence the potential function F can be written as the sum of these potential functions of the |Q| coalitional games defined on the |Q| blocks.

The potential function F of our non cooperative game can thus be written as the sum of the potential functions of |Q| coalitional games defined on the |Q| blocks. 15 Notice furthermore that the corresponding Shapley value can be straightforwardly identified, thanks to Eq. 2.16 and the relationship between the Shapley value and its potential, as the vector of R Rq+Gq whose components are the utilities enjoyed by the agents inside block q. This also means that condition 2.15, that has to be verified by the utility functions to have a potential function, corresponds to the Balance Contribution property of the Shapley value taken in the particular case of two agents of different colors.

Drawing the parallel a bit further allows also to highlight that the same difference exists between the potential function of the coalitional game and the grand coalition worth as between the potential function F and the collective utility U . Whereas F represents the sum of the agents' utilities at the time when they have moved into their current location starting with a totally empty city (or are considered to have done so), U represents the sum of the agents' utilities once they are all settled. Hence, while stationary configurations maximize F they do not necessarily (and the following examples show that they generally don't) maximize the collective utility.

Segregation by ethnic origin, income, and preferences for public amenities

Up to now, we have always implicitly supposed that the sole characteristic that the agents use to evaluate a location is the composition of its neighborhood. Other determinants of residential location choice however exist that are not necessarily correlated to neighbors' characteristics, such as local public goods. The red and green labelling of our two groups thus may correspond to two different ethnic origins or two groups with different preferences for local public goods. Tiebout ( 1956)'s analysis of the sorting induced by local public goods is perhaps the main competitor of [START_REF] Schelling | Dynamic models of segregation[END_REF] in terms of its influence on later work on neighborhood choice.

It is very easy to write versions of our model which take into account the agents' preferences for public goods while keeping the existence and properties of a potential function. Noting for example A the set of all the public facilities and d i,a the distance between an agent i and an amenity a ∈ A, the utility of an agent i could be rewritten in a general fashion as

u i (R, G) -→ u i (R, G) + ũi ({d i,a } a∈A ) (2.43)
and one could then easily derive the more general form of the potential function

F(x) -→ F(x) + i ũi ({d i,a } a∈A ) (2.44)
This generalized approach could provide a means to correct one of the bias of our analytical model, namely the lack of heterogeneity in locations. However, the extraction of the properties of the stationary states from this condensate global function would become quite challenging, as the dimension of the state variable of the system increases with the number of added amenities.

Taxation

In order to illustrate the usefulness of the potential function, we further consider the introduction of a tax against segregation. The basic concept at the center of a model à la

Schelling is that of an agent deciding where to move according solely to the utility gain she would achieve if she was to move. Her move affecting her past and new neighbors, an implicit consequence is that she could generate externalities that amount to ∆U -∆u while moving.

Suppose now the existence of a benevolent planner who subsidizes positive externalities and taxes negative externalities. A way to model the action of that planner is to write the probability that a move happens as:

P r{move} = 1 1 + e -∆u+α(∆U -∆u) /T
(2.45)

where 0 ≤ α ≤ 1 is a parameter controlling the tax level. The limit case α = 0 corresponds to a standard Schelling model and the limit case α = 1 corresponds to a case where only the interest of the collectivity as a whole is taken into account.

Following the path of the proofs developed in section 2.2, one can infer the stationary distribution in the bounded neighborhood framework:

Π(x) = e (1-α)F (x)+αU (x) /T z e (1-α)F (z)+αU (z) /T
(2.46)

The potential function can thus in this context be generalized to (1 -α)F(x) + αU (x). We already noted that the configurations maximizing F are not in general maximizing U and could even in certain cases (asymmetrically peaked utility functions) be very unfavorable to U . We show here that the parameter α = 1 of the tax indeed allows the planner to obtain a stationary configuration in which the collective utility is maximized. 16Such a Pigouvian tax supposes that the central government has a precise knowledge of the neighborhood composition of each moving agent, which is a rather utopian assumption. We propose here a new variation of Schelling model incorporating a different tax rule, based on more realistic assumptions regarding the goverment intervention ability. We define a simple tax, which aims at preventing the emergence or maintenance of a dominant group in each block. The central government imposes on each agent a tax which is defined as:

r(S, θ) = θ|S/H -0.5| if S/H > 0.5 0 otherwise (2.47)
where S is the number of agents similar to the taxed agent within his block and θ is a fixed parameter controlling the tax level. Note that the tax is paid only by every agent belonging to the majority in their district and therefore does not penalize agents in the minority. Note also that this definition of the tax is defined at the scale of the block of size H. This assumption implies a direct competition between the segregative effect of a model la Schelling, which favors values of s/H greater than 0.5, and the tax mechanism which favors values of S/H below 0.5.

The utility of red and green agents is then redefined, taking into account the penalty imposed by the tax, as:

ûR (R, G, θ) = u R (R, G) -r(R, θ) ûG (R, G, θ) = u G (R, G) -r(G, θ) (2.48)
The tax is null for θ = 0. For θ > 0, one can expect that a rise in θ implies a rise in the probability of having non-segregated configurations in the stationary states.

From an analytical viewpoint, the properties of the model resulting from the Markov chain theory remain unchanged: there exists one unique stationary distribution and the final configurations do not depend on the initial ones. It is also straightforward to check that if the pair of utility functions (u r , u G ) verifies condition 2.15, then so does the pair (û r , ûG ) and it is hence possible to derive a potential function incorporating the tax effects.

To be more specific, suppose that the utility of the agents is given by the asymmetrically peaked function introduced in section 2.4.3, which is a case where the the stationary configuration clearly diverges from the collective optimum. An agent utility û can be rewritten in this case as:

û(S, θ) = u ap, m (S) -r(S, θ) = 2S/H -0 if S/H ≤ 0.5 2 -m -2(1 -m)S/H -θ|S/H -0.5| if S/H > 0.5 = 2S/H if s i ≤ 0.5 2 -(m -θ/2) -2(1 -(m -θ/2))S/H if S/H > 0.5 = u ap, m-θ/2 (S) (2.49)
Hence our tax mechanism can be interpreted in this case as a direct control by the central government of the asymmetry parameter m in the agents' utility function.

According to the analytical results obtained in section 2.4.3, the asymmetry parameter must be inferior to m c = 0 in order to avoid segregation. The equivalence stated in Eq.

2.49 thus allows us to predict that the minimal tax level necessary to break segregated patterns is:

θ c (m) = 2(m -m c ) = 2m (2.50)
Our analytical framework thus allows one to consider the consequences of different tax levels in a very simple way. Other public policies against segregation could also probably be analysed.

Conclusion

In this chapter, we used recent tools from evolutionary game theory to develop an ana- Nash equilibrium where R q = G q = (H + 1)/2 and T > 0, the logit rule implies that there is a positive probability that an agent accepts a slight decrease of his utility, and leaves a block with composition R q = G q = (H + 1)/2. The agents of the same colour remaining in his former block now have a lower utility and are even more likely to leave. This creates an avalanche which empties the block of agents of the same color, as each move away further decreases the utility of the remaining agents. Conversely, highly-segregated configurations are very stable. Indeed, once the city is divided into homogeneous areas, a red agent will have no incentive to go from the red area to the green one, his utility dropping from m to 0.

lytical
The analytical tool given here will permit one to consider the outcomes of other types of utility functions, in particular those that emerge from empirical findings on social preferences. It is now conceivable to analyze the theoretical outcomes of these preferences and possibly to test the effect of introducing public policy instruments aimed at decreasing segregation. It is also worth noticing that with the original utility function suggested by Schelling, the potential function happens to be a linear form of the Duncan and Duncan segregation index. We thus built a bridge between theoretical models of segregation and residential segregation measures.

The kind of solution that is developed here has been used in physics in equilibrium statistical mechanics. Equilibrium statistical mechanics has developed powerful tools to link the microscopic and macroscopic levels. These tools are usually limited to physical systems, where dynamics is governed not by a selfish criterion but by a global quantity such as the total energy. [START_REF] Blume | The Statistical Mechanics of Best-Response Strategy Revision[END_REF] already built a bridge between statistical physics and a coordination game with local interactions. Here, by using the potential function, which is analogous to state functions in thermodynamics, we have extended the analytical framework of statistical mechanics to Schelling model. By doing so, our work paves the way to analytical treatments of a much wider class of social systems, where dynamics is governed by individual strategies.

Chapter 3

Competition between collective and individual dynamics 3.1 Introduction

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 [START_REF] Cotterill | The Cambridge Guide to the Material World[END_REF][START_REF] Goodstein | States of Matter[END_REF], neurons give rise to consciousness (Damasio, 1995;[START_REF] Changeux | The Physiology of Truth: Neuroscience and Human Knowledge[END_REF] or individuals shape societies [START_REF] Smith | An Inquiry into the Nature and Causes of the Wealth of Nations[END_REF][START_REF] Latour | Reassembling the Social: An Introduction to Actor-Network-Theory[END_REF].

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 [START_REF] Goodstein | States of Matter[END_REF]. In contrast, economic agents behave in a selfish way, and equilibrium is attained when no agent can increase its own satisfaction [START_REF] Mas-Colell | Microeconomic Theory[END_REF]. Although similar at first sight, the two approaches lead to radically different outcomes.

In this chapter, we illustrate the differences between collective and individual dynamics on an exactly solvable model, similar to Schelling's segregation model [START_REF] Schelling | Dynamic models of segregation[END_REF]. The model considers individual agents which 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 [START_REF] Schelling | Dynamic models of segregation[END_REF] has generated an abundant literature.

Many papers have simulated how the global state depends on specific individual utility functions, as reviewed by (Clark & Fossett, 2008). There have been attempts at solving

Schelling's model analytically, in order to provide more general results concerning the consequences of individual preferences on segregation levels [START_REF] Pollicott | The Dynamics of Schelling-type segregation models and a nonlinear graph laplacian variational problem[END_REF]Zhang, 2004b;[START_REF] Dokumaci | Schelling Redux: An Evolutionary Dynamic Model of Residential Segregation[END_REF]

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 [START_REF] Schelling | Dynamic models of segregation[END_REF] (see below and appendix B). The city is divided into Q blocks (Q 1), each block containing H cells or flats (Fig 3.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 he is living in. 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 coarse-grained 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, within two different blocks. Then the agent moves in that empty cell with probability:

P xy = 1 1 + e -C/T , (3.1)
where x and y are respectively the configurations before and after the move, and C is the cost associated to the proposed move. The positive parameter T is a "temperature" which introduces in a standard way [START_REF] Anderson | Discrete Choice Theory of Product Differentiation[END_REF]) 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. . . ).

We write the cost C as :

C = ∆u + α(∆U -∆u) (3.2)
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 cost C, 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 below). 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 cost C can be written as C = ∆V ≡ V (y) -V (x), where V (x) is a function of the configuration x, then the dynamics satisfies detailed balance Evans et al.

(2005) and the distribution Π(x) is given by

Π(x) = 1 Z e F (x)/T , (3.3)
with F (x) = V (x) + T S(x) and Z a normalization constant. The entropy has for large H the standard expression S(x) = H q s(ρ q ), with

s(ρ) = -ρ ln ρ -(1 -ρ) ln(1 -ρ).
(3.4)

We now need to find the function V (x), if it exists. Given the form (3.2) of C, finding such a function V (x) amounts to finding a "linking" 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:

(ρ) = ρ 0 u(ρ )dρ . (3.5)
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 :

f (ρ) = -T ρ ln ρ -T (1 -ρ) ln(1 -ρ) + αρu(ρ) + (1 -α) ρ 0 u(ρ )dρ . ( 3
(ρ) = 2ρ if ρ ≤ 1/2 and u(ρ) = m+2(1-m)(1-ρ) if ρ > 1/2
, where 0 < m < 1 is the asymmetry parameter. Agents strictly prefer half-filled neighborhoods (ρ = 1/2). They also prefer overcrowded (ρ = 1) neighborhoods to empty ones (ρ = 0).

The probability Π(x) is dominated by the configurations x = {ρ q } that maximize the sum q f (ρ q ) under the constraint of a fixed ρ 0 = 1/Q Q q=1 ρ q . To perform this maximization procedure, we follow standard physics methods used in the study of phase transitions (like liquid-vapor coexistence [START_REF] Callen | Thermodynamics and an introduction to thermostatistics[END_REF]), 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 , while the others have a density ρ * 2 > ρ 0 (see Appendix B).

Interestingly, the potential F = (1 -α)L + αU + T S 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 + T S is equivalent to the minimization of the free energy E -T S. 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 to predict analytically the global town state. Such an achievement eluded so far individualistic, Schelling-type models, which had to be solved through numerical simulations (Clark & Fossett, 2008).

To obtain explicitly 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 [START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF], which indicates that agents prefer mixed blocks (Fig 3 .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, to avoid entropy effects. The qualitative behaviour of the system is unchanged for ρ 0 = 1/2 or for low values of the temperature, as shown in the appendix B.

m < 2/3 2/3 ≤ m ≤ 1 ρ s 1 2 (2 -m)/(1 -m) 1 U * 1 1 + (1 -m)/(2 -m) m L * 1 1 + (1 -m)/(2 -m) 1/2 + m/4
In the collective case (α = 1), the optimal state corresponds to the configuration that maximizes the global utility, which can be immediately guessed from Figure 3.2, namely ρ q = 1/2 for all q (Fig 3 .1a). On the contrary, in the selfish case (α = 0, Fig

3.1b

), 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 another ρ q = 1/2 block. This creates an avalanche which 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. 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). In case of a homogeneous town (an unstable Nash equilibrium for which ρ q = 1/2 for all q), the normalized collective utility is given by U * = U/(ρ 0 HQ) = u(ρ 0 = 1/2) = 1. The normalized link equals, for all m, L * = L/(ρ 0 HQ) = (ρ 0 )/ρ 0 = 1/2, where is given in Eq. 3.5. The values of L * and U * displayed in Table 3.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 values of the homogeneous and segregated configurations increases with m. This helps understanding 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 ones by a phase transition at the critical value α c = 1/(3-2m)

-which increases with m (Figure 3.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 economics' 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 [START_REF] Auerbach | The theory of excess burden and optimal taxation[END_REF], one expects that α = 1 is necessary to reach the optimal state, since by definition this value internalizes all the externalities the agent causes As T is increased, the whole diagram is affected by the entropic term. Compared to the T = 0 case, the main change is the appearance of a second homogeneous phase for ρ 0 < 1/2. But while for ρ 0 > 1/2 homogeneity corresponds to the optimal choice for the agents, for ρ 0 < 1/2, collective utility is not maximized in a homogeneous city. The city is homogeneous by noise, not by choice.

Note that an increase in α tends to reduce this domain, while it tends to increase the homogeneous domain for ρ 0 > 1/2.

to the others when moving. Our results show that the optimal state is maintained until much lower tax values (for example, α c = 1/3 at m = 0), a surprising result which deserves further analysis. Another interesting effect is observed for m > 2/3 (Figure 3.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 to density of the blocks (see Fig. 3.4).

Discussion

There are two main differences between our simple model and Schelling's original model [START_REF] Schelling | Dynamic models of segregation[END_REF] : the existence 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 agents of two "colors" (such as red and green). Simple calculations (see appendix B) show that for two species which only care about the density of neighbors of their own color, the block potential (eq. 3.6) becomes :

f (ρ R , ρ G ) = -T ρ R ln ρ R -T ρ G ln ρ G -T (1 -ρ R -ρ G ) ln(1 -ρ R -ρ G ) + α ρ R u R (ρ R ) + ρ G u G (ρ G ) + (1 -α) ρ R 0 u R (ρ )dρ + ρ G 0 u G (ρ )dρ
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 the appendix B).

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 can not 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 states 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 Figure 3.5a). For α ≥ α c , the system settles in mixed states where the density of a group in a block is either 0 or 1/2 (see Figure 3.5b). The reader is referred to appendix B for more details.

We now turn to the difference in agent's neighborhoods. In Schelling's original model, agents' neighbors are defined as their 8 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 which abandons the individual point of view and is limited to a specific utility function (Zhang, 2004b). Finally, the simulations presented on Figures 3.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 modelling, 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 [START_REF] Kirman | Whom or What Does the Representative Individual Represent?[END_REF]: the optimization strategy based on purely individual dynamics fails, illustrating the unexpected links between micromotives and macrobehavior [START_REF] Schelling | Micromotives and Macrobehavior[END_REF]. However, the emergent collective state can be efficiently captured by the maximization of the linking function (ρ) given in Eq. (3.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. This means that no agent can increase its utility by moving (since ∆u = ∆L), consistently 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 is 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 [START_REF] Monderer | Potential games[END_REF], we have extended the framework of statistical mechanics to a Schelling-like model. Such an approach paves the way to analytical treatments of a much wider class of systems, where dynamics is governed by individual strategies. Effective Free Energy for Individual Dynamics

Introduction

The intricate relations between the individual and collective levels are at the heart of many natural and social sciences (Grauwin et al., 2009a). Physics looks at the collective level, selecting the configurations that minimize the global free energy [START_REF] Goodstein | States of Matter[END_REF].

In contrast, economic agents behave in a selfish way, and equilibrium is attained when no agent can increase its own satisfaction [START_REF] Mas-Colell | Microeconomic Theory[END_REF].

Recently, physicists have tried to use statistical physics approaches to understand social phenomena such as the segregation transition [START_REF] Dall'asta | Statistical physics of the Schelling model of segregation[END_REF][START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF]. The idea seems promising because statistical physics has successfully bridged the gap between the micro and macroscopic levels for physical systems governed by collective dynamics. However, progress remained slow due to the lack of an appropriate framework allowing to take into account the selfish dynamics typical of socio-economic agents. On the other hand, game theorists have developed in the last decades the notion of Potential Games, in which each player's gain resulting from a change of state is equal to the variation of a potential function [START_REF] Anderson | Discrete Choice Theory of Product Differentiation[END_REF][START_REF] Young | The evolution of conventions[END_REF][START_REF] Monderer | Potential games[END_REF][START_REF] Ui | A Shapley value representation of potential games[END_REF]. This potential function hence provides what physicists need: a link between individual and collective levels.

In this chapter, we propose a generic analytical framework that builds on concepts originating both from statistical physics and game theory. We introduce a rigorous generalization of the physicist's free energy, which encompasses individual dynamics.

By introducing a "link" state function that is maximized in the stationary state, we

The Model

Generic model

Our model represents in a schematic way the dynamics of agents making individual choices. Throughout this chapter, N = {1, . . . , N } denotes a finite set of agents, q i ∈ {1, . . . , Q} the choice of agent i ∈ N , the vector q = (q i ) i∈N describing the state of the system and N q (resp. n q ) the set (resp. number) of agents following choice q ∈ {1, . . . , Q}. Each agent i ∈ N can moreover be characterized by his utility function, which describes the degree of satisfaction concerning his choice. An agent's utility function is supposed to depend only on his own choice and on the set N q i of agents making the same choice, namely u i ( q) = u i (q i , N q i ). We also introduce the collective utility, defined as the total utility of all the agents:

U ( q) = i u i ( q).
The dynamical rule allowing the agents to change their choice is the following. At each time step, one picks up at random an agent and a choice q * ∈ {1, . . . , Q}. Then the agent goes from choice q i to choice q i = q * with probability:

P q i →q i = 1 1 + e -∆u i /T , (4.1)
where ∆u i = u i ( q ) -u i ( q) is the variation of the agent's own utility upon his change of choice. The parameter T > 0 is a "temperature" that introduces in a standard way some noise on the decision process [START_REF] Anderson | Discrete Choice Theory of Product Differentiation[END_REF]. It can be interpreted as the effect of features that are not explicitly included in the utility function but still affect the decision.

We wish to find the stationary probability distribution Π( q) of the microscopic configurations q. If ∆u i can be written as ∆u i = ∆L ≡ L( q ) -L( q), where L( q) is a state function of the configuration q, then the dynamics satisfies detailed balance [START_REF] Evans | Nonequilibrium statistical mechanics of the zero-range process and related models[END_REF] and the distribution Π( q) is given by

Π( q) = 1 Z e L( q)/T , (4.2)
with Z a normalization constant.

It can be shown (Grauwin et al., 2009a;[START_REF] Ui | A Shapley value representation of potential games[END_REF] that a sufficient and necessary CHAPTER 4. EFFECTIVE FREE ENERGY FOR INDIVIDUAL DYNAMICS 101 condition1 for a "linking" function L to exist is u i (q i , N q i \ {j}) -u i (q i , N q i ) = u j (q j , N q j \ {i}) -u j (q j , N q j ) (4.3)

for any i ∈ N and j ∈ N . Note that this relation is automatically satisfied in the case q i = q j . Eq. (2.15) expresses a symmetric condition on the utility variation (or externality) an agent produces on another one when he changes his choice. Condition

Eq. ( 4.3) is also rather easy to satisfy in case of homogeneous agents sharing the same utility function (see examples in section 4.3). In contrast, this condition imposes more restriction to models with heterogeneous agents and explicit examples are then more difficult to build.

Interestingly, the linking function L appears as (the opposite of) an effective energy in terms of physical systems (Eq. ( 4.2) being the analogue of a Gibbs distribution), but also corresponds to the notion of potential function in game theory [START_REF] Monderer | Potential games[END_REF][START_REF] Ui | A Shapley value representation of potential games[END_REF].

Homogeneous agents

In the following, we restrict our study to models where the agents' utility functions can be written as u i ( q) = u(q i , n q i /H), where H is a parameter characterizing the typical number of agents making a given choice (for instance the natural capacity of an infrastructure). This parameter is assumed to scale linearly with N , the ratio h = H/N being fixed. This particular form of utility function implies that the agents share homogeneous properties and that they are sensitive to the relative proportion of agents making the same choice as them. It also implies that Eq (4.3) is verified, meaning that a linking function L always exists. It is straightforward to check that it can be written as :

L( q) = Q q=1 nq( q) m=0
u(q, m/H) (4.4)

In the limit N → ∞ with ρ q = n q /H fixed, one finds

L( q) → hN Q q=1 ρq 0 u(q, ρ) dρ. (4.5) CHAPTER 4. EFFECTIVE FREE ENERGY FOR INDIVIDUAL DYNAMICS 102
This particular form of the potential function L allows us to interpret it as the sum of the individual marginal utilities gained by agents as they progressively enter the system after leaving a reservoir of zero utility.

Since the agents are supposed to be identical (but still distinguishable), it seems natural to keep track of "mesoscopic" observables such as the coarse-grained states

x ≡ {ρ q } rather than the "microscopic" states q. The number of states q corresponding to a given coarse-grained state x is quantified by its logarithm:

S(x) = ln N ! q n q ! h, {ρq} fixed --------→ N →∞ -N ln h -hN Q q=1 ρ q ln ρ q . (4.6)
The stationary distribution of the coarse-grained configurations hence takes the form:

Π N,T (x) = 1 Z N,T e F (x)/T = 1 Z N,T
e (hN/T ) q f N,T (q,ρq) (4.7)

where F (x) ≡ L(x) + T S(x) can be seen as (the opposite of) an effective free energy of the system, Z N,T = Z N,T h -N and where f N,T (q, ρ) = ρH m=0 u(q, m/H) -T ρ ln ρ (4.8)

In the limit N → ∞ with ρ q = n q /H fixed, one finds

f N,T (q, ρ) → f ∞,T (q, ρ) ≡ ρ 0 u(q, ρ ) dρ -T ρ ln ρ (4.9)
According to the form of the distribution Π N,T given by Eq (4.7), in the limit of large N the stationary configurations are those that maximize the sum q f ∞,T (q, ρ q ) under the constraint h q ρ q = 1. We explore different maximization procedures in examples of applications presented in next section.

Applications

Road congestion

We apply here our generic model framework to a simplified version of Chu's [START_REF] Chu | Endogenous trip scheduling: the Henderson approach reformulated and compared with the Vickrey approach[END_REF] reflect that bigger roads are built when the traffic is more important) and the parameter γ measures the elasticity of travel time with respect to n t . is the number of agent queueing on the road at a given time t. It is computed as the difference between the number of departed and arrived agents Q t = t t =0 d t -n t , where the distribution of departure time {d t } is deduced from the distribution of arrival time {n t } and travel time {T T (t)}. See [START_REF] Chu | Endogenous trip scheduling: the Henderson approach reformulated and compared with the Vickrey approach[END_REF] for more details on this procedure. The computations have been realized in the limit T → 0, with the parameters values t * = 900, α = 2, β = 1, ν = 4, γ = 4, h = 4. 10 -4 . This congestion model fits our framework model, the utility of an agent arriving at time t being

u(n t ) = -c(t) = - α(n t /H) γ + β|t * -t| if t < t * α(n t /H) γ + ν|t * -t| if t ≥ t * (4.10) CHAPTER 4.

EFFECTIVE FREE ENERGY FOR INDIVIDUAL DYNAMICS 104

The stationary coarse-grained configurations in the limit of large N are thus those that maximize the sum t f ∞,T (t, ρ t ), where: which can be easily derived using Lagrange multipliers. Eq (4.12) provides for each time step t an implicit relation between ρ t and ρ t * (resp. the normalized densities at time t and t * ). All these implicit relations along with the conservation of the number of agents expressed by the condition h t ρ t = 1 allow one to compute numerically the distribution {ρ t }. Fig. 4.1 presents results that have been computed with this method, for N → ∞ and for a finite value (N = 5000) of the number of agents obtained by solving numerically an equivalent of Eq. (4.12). These results suggest that finite size effects remain small as soon as N reaches values of a few thousands, and that the main properties of the model can be studied in the limit N → ∞. Notice that our analysis of the congestion model in terms of a potential games allows us to determine (numerically) the stationary state of the systems even for finite size, which is rarely possible with usual economics analysis since, quoting [START_REF] Otsubo | Vickrey's model of traffic congestion discretized[END_REF], the common practice in transportation science and economics is to use continuous models for analyzing phenomena that are essentially discrete.

f ∞,T (t, ρ) = α γ+1 ρ γ+1 + βρ|t * -t| -T ρ ln ρ if t < t * α γ+1 ρ γ+1 + νρ|t * -t| -T ρ ln ρ if t ≥

Residential choice

As a second example, we apply our generic framework to a Schelling-like model describing the dynamics of residential moves in a city (Grauwin et al., 2009a;[START_REF] Schelling | Micromotives and Macrobehavior[END_REF].

The virtual city is divided into Q blocks (Q 1), each block containing H cells or flats (Fig 4 .2). We assume that each cell can contain at most one agent, so that the number n q of agents in a given block satisfies n q ≤ H. An agent's utility depends only on the density ρ q = n q /H of the block he is living in, ie u i ( q) = u(ρ q ), with the convention that u(ρ) = -∞ for ρ > 1.

Once again, this residential model can be solved thanks to our framework. With the particular choice of the asymmetrically peaked utility function given Stationary configurations of a virtual city for T 1. Agents are distributed homogeneously between the blocks. The city is composed of Q = 36 blocks containing each H = 100 cells, with a mean density ρ q = N/HQ = 1/2. maximize the sum q f ∞,T (q, ρ q ), where 2 :

f ∞,T (q, ρ) = ρ 2 -T ρ ln ρ if ρ < 1/2 -ρ 2 /2 + 3ρ/2 -3/8 -T ρ ln ρ if ρ ≥ 1/2 (4.13)
To perform the maximization procedure, one can follow standard physics methods used in the study of phase transitions (like liquid-vapor coexistence [START_REF] Callen | Thermodynamics and an introduction to thermostatistics[END_REF]). In this case, it is a simple exercise to determine that for N 1 and in the limit T → 0, a phase separation occurs. A fraction min 2 √ 3/3hQ, 1 of the blocks have a density min √ 3/2, 1/hQ while the others are empty. This result is illustrated on Fig. 4.2.

For more details on the maximization procedure, the interested reader is referred to (Grauwin et al., 2009a, or appendix B).

Discussion

We derived in this chapter an effective free energy F = L + T S in a generic framework model. The main property of this function is to intimately connect the individual and global points of view. Our simple model raises a number of interesting questions: in the limit T → 0, the stationary configurations are those maximizing the potential L and not

2 Caution: the expression of the entropy S(x) depends on the precise definition of the "microscopic" states of the system. If the agents were to choose the cell (instead of the block ) in which they would like to move, one would need to add the term S (x) = q ln H! (H-nq )! in the expression of the entropy.

CHAPTER 4. EFFECTIVE FREE ENERGY FOR INDIVIDUAL DYNAMICS 106

the collective utility U . Hence, they may differ from the simple collection of individual optima [START_REF] Kirman | Whom or What Does the Representative Individual Represent?[END_REF], illustrating the unexpected links between micromotives and macrobehavior.

More specifically, we derived a simple expression of this effective free energy in the thermodynamic limit N → ∞ for homogeneous agents. We showed that this simple form allows us to derive in an easy and flexible way quantitative solutions to economics models based on individual dynamics. This approach can be extended to some models with heterogeneous agents. Possible examples range from a two-population residential segregation model (Grauwin et al., 2009a, or chapter 2), Ising-like model with heterogeneous pairs interactions [START_REF] Nadal | Physique statistique de phénomènes collectifs en sciences économiques et sociales[END_REF], or the Hopfield model [START_REF] Ui | A Shapley value representation of potential games[END_REF].

Part II Complex Systems Science: Dreams of Universality, Reality of Interdisciplinarity

Maps of Science

Introduction

Fundamental science has striven to reduce the diversity of the world to some stable building blocks such as atoms and genes. To be fruitful, this reductionist approach must be complemented by the reverse step of obtaining the properties of the whole (materials, organisms) by combining the microscopic entities, a notoriously difficult task [START_REF] Hayden | Life is complicated[END_REF][START_REF] Anderson | More is Different[END_REF]Grauwin et al., 2009a;[START_REF] Gannon | Too complex to comprehend?[END_REF]. The science of complex systems tackles this challenge, albeit from a different perspective. It adds the idea that "universal principles" could exist, which would allow for the prediction of the organization of the whole regardless of the nature of the microscopic entities. Ludwig Von Bertalanffy wrote already in 1968: "It seems legitimate to ask for a theory, not of systems of a more or less special kind, but of universal principles applying to systems in general " (Von Bertallanffy, 1976). This dream of universality is still active: "[Complex networks science] suggests that nature has some universal organizational principles that might finally allow us to formulate a general theory of complex systems " [START_REF] Solé | quoted in the New York Times[END_REF].

Results

In this chapter, we empirically study the "complex systems" field and its claims to universality. To collect a representative database of articles, we selected from the ISI Web of knowledge (WoS, 2011) all records containing topic keywords relevant for the field of complex systems (refer to Table 5.5 for the precise query. In this chapter, we limit ourselves to papers published after 2000). Table 5.1 contains the 20 most frequent cited references and journals within our dataset. To analyze the data, we build a network (Börner & Schernhost, 2009) in which the ∼ 141 000 articles are the nodes.

These nodes are linked according to the proportion of shared references (bibliographic coupling [START_REF] Kessler | Bibliographic coupling between scientific papers[END_REF]. For this study, bibliographic coupling offers two advantages over the more usual co-citation link: it offers a faithful representation of the fields, giving equal weight to all published papers (whether cited or not) and it can be applied to recent papers (which have not yet been cited). For more details, the reader is referred to the section "Methods".

Figure 5.1 shows the largest communities (thereafter also called "fields" or "disciplines") obtained by modularity maximization of the network of papers published in the years 2000-2008. We first note that all important complex systems subfields 1 are 1 In the following, we use italics to refer to the names of the communities.

present 2 . At the center, we find mostly theoretical domains: self-organized criticality, dynamical systems, complex networks, neural networks. These fields are connected to more experimental communities lying at the edges (materials science, biology or neurosciences). The links between theoretical and experimental fields suggest that complex systems science models have connections to the "real" world, as claimed by their practitioners.

Figure 5.1: Community structure obtained with a first run of the modularity maximization [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF](Blondel et al, ) on the 2000(Blondel et al, -2008 network (141,098 articles) network (141,098 articles). The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I,j∈J ω ij /N I N J . The layout of the graph is obtained thanks to a spring-based algorithm implemented in the Gephi visualization software [START_REF] Bastian | Gephi: An Open Source Software for Exploring and Manipulating Networks[END_REF]. For the sake of clarity, communities with less than 300 articles are not displayed. The label of a community represents the most frequent and/or significant keyword of its articles. CN stands for Complex Networks, SOC for Self Organized Criticality, DS for Dynamical Systems, DigitCom for Digital Communication and Sur-faceSO for Self-organization on Surfaces. EMC is a more composite community where the three most representative keywords are Ecology, Management and Computational Models. See Figure 5.2 for details.

2 As can be checked by consulting authoritative CS web sites such as Santa Fe's and its "Exploring complexity" lectures: http://www.santafe.edu/news/item/ exporing-complexity-science-and-technology-santa-fe-institute-perspective/ (accessed June 1st, 2010).

To understand the inner structure of these large communities, we use recursive modularity optimization (see [START_REF] Fortunato | Resolution limit in community detection[END_REF] and "Methods"). Most fields display a rich inner structure (Figure 5.2) with subcommunities (thereafter also called "subfields" or "subdisciplines") organized around several specific topics and references.

The only exceptions are self-organized criticality and complex networks, where all articles cohere around a few references. Table 5.2 displays some quantitative informations about each subfield. For a more detailed presentation of the subfields, including their main authors, most used journals, references and keywords, see Appendix C. We analyze this complex structure at two levels. First, at the global scale, complex systems science appears to be a densely interconnected network. This is somewhat surprising since sharing references between subdisciplines means that they are able to read and understand these references, and moreover, that they find them useful. Would these shared references point to "universal" principles? Second, we focus on a more local scale, on the links that specifically connect two different disciplines (ie two different colors in Figure 5.1) to understand how they manage to exchange knowledge.

Complex systems' science overall coherence

Let us start with the field's overall coherence. We have looked for the references cited by many subfields and form the "glue" that links many subdisciplines and connects the network. More precisely, we define the networking force of a reference N (r) as the sum, over all pairs of subfields, of the proportion of their links explained by that reference (see Methods). Table 5.3 shows that the references that glue the network are more methodological than theoretical: the most networking reference is "Numerical Recipes" (Press et al, 2010), a series of books that gathers many routines for various numerical calculations and their implementation in computers. Most of the other linking references are mathematical handbooks or data analysis tools. If one looks for universality in the complex systems field, the computer -as a tool -seems to be a serious candidate.

Among the leading contributors to the glue, we also find several references on selforganization (SO). Self-organization is not a predictive theory, but an approach that focuses on the spontaneous emergence of large-scale structures out of local interactions between the system's subunits (Mehdi et al, 2009). Several subdisciplines in Figure 5.2 can be related to this approach, as they use a keyword akin to "self-organization" (SO) in more than 10% of their articles (for a more complete list of the communities using this keyword, see appendix C). Among theses we find swarm SO, molecular SO linking chemistry to biology, growth SO and pattern formation SO linking surface science to dynamical systems. This suggests that the field of complex systems focuses on the CHAPTER 5. COMPLEX SYSTEMS SCIENCE: DREAMS AND REALITY 113 cases in which the link from microscopic to macroscopic can be analyzed through selforganization, which gave rise to several fruitful scientific programs, as we discuss below (section Discussion). The acronyms and abbreviations in parenthesis correspond to the label of the subfields displayed on Fig 5 .2. The opposite of the average of the inner links's weight of a subfield < ω in > -1 is (the opposite of ) an inner coherence measure that support a straightforward interpretation. Indeed, if the weights of the inner links of a subfield were homogeneously distributed between all pairs of articles, two articles randomly chosen of this subfield would share 1 reference over < ω > -1 . an interesting research topic. For example, physical sciences look for universal laws, while social [START_REF] Borgatti | Network Analysis in the Social Sciences[END_REF] and biological (Fox-Keller, 2005) sciences emphasize the variations in structure across different groups or contexts and use these differences to explain differences in outcomes. Physicians are interested in practical medical advances while physicists want to know whether physiological rhythms are chaotic or not [START_REF] Glass | Synchronization and rhythmic processes in physiology[END_REF].

Subfield N < ω > -
Where do the links come from then? In an illuminating analogy, Peter [START_REF] Galison | Image and Logic: A Material Culture of Microphysics[END_REF] compares the difficulty of connecting scientific disciplines to the difficulty of communicating between different languages. History of language has shown that when two cultures are strongly motivated to communicate -generally for commercial reasons -they develop simplified languages that allow for simple forms of interaction. At first, a "foreigner talk" develops, which becomes a "pidgin" when social uses consolidate this language. In rare cases, the "trading zone" stabilizes and the expanded pidgin becomes a creole, initiating the development of an original, autonomous culture. Analogously, biologists may create a simplified and partial version of their discipline for interested physicists, which may develop to a full-blown new discipline such as biophysics. Specifically, [START_REF] Galison | Image and Logic: A Material Culture of Microphysics[END_REF] has studied how Monte Carlo simulations developed in the postwar period as a trading language between theorists, experimentalists, instrument makers, chemists and mechanical engineers. Our interest in the concept of a trading zone is to allow us to explore the dynamics of the interdisciplinary interaction instead of ending analysis by reference to a "symbiosis" or "collaboration".

Table 5.4 gives a list of the main "trading zones" which connect theoretical and experimental fields in Figure 5.1 and capture a significant fraction of the links between these fields. The clearest example is transcriptomics data analysis, a subfield of neural networks which connects biologists interested in the interpretation of data retrieved from DNA chips and computer scientists interested in data analysis via methods from the neural networks field. The transcriptomics data analysis subfield represents 2.3% of neural networks papers but accounts for 46.3% of the connections between neural networks and biology and 16.5% of the links between neural networks and complex networks.

Other trading zones are computational systems biology, linking biology to many theoret- Diffusion-limited aggregation 0.234 [START_REF] Cohen | Statistical power analysis for the behavioral sciences[END_REF] Statistics and behavioral sciences (book) 0.223 [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF] Neural networks 0.217 [START_REF] Stanley | Introduction to phase transitions and critical phenomena[END_REF] Phase transition (book) 0.202 Whitesides et al. (2002) Self-assembly 0.188 [START_REF] Marquardt | An algorithm for least-squares estimation of nonlinear parameters[END_REF] Applied mathematics 0.174 [START_REF] Chomczynski | Single-step method of RNA isolation by acid guanidinium thiocyanate-phenol-chloroform extraction[END_REF] RNA isolation 0.167 Venter et al. (2001) Human genome sequence 0.160 ical fields, among which dynamical systems, self-organized criticality and complex networks, neural synchronization linking dynamical systems and neurosciences, cytoskeleton self-organization linking biology to dynamical systems and self-organized criticality and calibration linking neural networks and material sciences. Note that a single trading zone can be used by a fields to exchange with several other fields, as long as these other fields share the same "language". For example, computational systems biology, links biology to dynamical systems, self-organized criticality and complex networks, three subfields which share the physicists' toolkit. Since our map cannot cover all scientific fields, we may not recognize some subfields as trading zones, such as electrocardiogram which is likely to connect dynamical systems to medecine, or even miss a trading zone between geosciences and self-organized criticality. discipline, able to understand data analysis and its biological interest was built around transcriptomic tools. The two references most used by this subfield stress the applicative side: the purpose of the first paper is "to describe a system of cluster analysis Table 5.4: Strongest trading zones. The trading force T of a subcommunity measures the fraction of the links between two fields (in Fig. 5.1) which goes through this subcommunity. More precisely, the trading force of I, a subcommunity of Ī, towards any community J is the total weight of the article-article links between the subcommunity I and community J, normalized by the total weight of the the article-article links between Ī and J: TĪ J (I) = i∈I,j∈ J ω ij / i∈ Ī,j∈ J ω ij . The expected force T exp is the value of the trading force one would expect if all the links between Ī and outside communities were equally shared among all sub-communities of Ī, which is simply the fraction N I /NĪ of articles of I in Ī. The acronyms of the subfiels used here correspond to those explained in for genome-wide expression data from DNA microarray hybridization [. . . ] in a form intuitive for biologists" [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF] while the second "describes the application of self-organizing maps for recognizing and classifying features in complex, multidimensional [transcriptomic] data" (Tamayo et al, 1999). The transcriptomics data analysis papers are clustered together because they share references presenting this kind of applications. The applicative character of transcriptomics data analysis can also be seen in the origin of the references that link them to neighbor subfields (Figure 5.4). The common references between transcriptomics data analysis and biology (mainly transcriptomics)

are similar to references used by transcriptomics data analysis papers themselves. This means that the link arises from biologists citing results obtained by transcriptomics data analysis scientists or techniques they use. On the other hand, the common references between transcriptomics data analysis and self-organizing maps (a subfield of neural net- The orientation of the links is quite different for computational systems biology (CSB) and complex networks (CN), because these subfields tend to pump their neighbors' references, while the other subfields do not find much use in computational systems biology and complex networks references.

works) are similar to references used by self-organizing maps papers. This means that the link arises from transcriptomics data analysis scientists citing classification techniques created by self-organizing maps scientists, while these scientists do not often use transcriptomics data analysis references. Therefore, transcriptomics data analysis allows self-organizing maps techniques to be understood and used to interpret biological data, with a relevance certified by biologists' citations. The case of another trading zone, computational systems biology, is different. Its most used references point to computational methods -mainly Gillespie's algorithm (Gillespie, 1977) or to experimental papers in which there is no explicit modelling but that show complex cellular dynamics, thus justifying indirectly the need for modelling. The link between experiments and modelling CHAPTER 5. COMPLEX SYSTEMS SCIENCE: DREAMS AND REALITY 121 is still speculative, as summarized by one of the most used references in this subfield (Tyson et al, 2010): "we hope that this review will [...] promote closer collaboration between experimental and computational biologists." Moreover, the common references between computational systems biology and biology are from biology, as if computational systems biology scientists were eager to quote potentially interesting biological applications for their modelling approach, while many biologists were still unaware of these models. In short, compared to transcriptomics data analysis, computational systems biology seems a more speculative trading zone, at the frontier of biology and modelling, but presently lacking a specific object or concept to define an operational trading zone. These two maps show an overall division of the science literature in less than a dozen main fields (here represented by colors), with a clear separation between biology, medicine and neuroscience (on the left hand side) and chemistry, mathematics, physics and computer science (on the right hand side).

Complex Systems

While these maps are very interesting in many ways, it should be noted that they do not contain any "complex systems" subfield, although we can find a Self-Organized Criticality (SOC) community on the 2000 map (middle right hand side) and a Complex Networks (CN) community on the 2010 map (middle right hand side). These maps suggest that there exists (yet?) no conceptual kernel for "complexity science", some unified theory that could give the field enough coherence to be a subfield identifiable by shared references (and therefore by bibliographic coupling). Self-Organization, Self-Organized Criticality or Complex Networks do constitute such coherent subfields. However, despite some claims, these subfields seem to have only weak links to the rest of the complex systems "galaxy" shown above, which prevents the formation of a coherent "complex systems science".

Discussion

Our empirical study of the "complex systems" field shows that its overall coherence does not arise from a universal theory but from computational techniques and successful adaptations of the idea of self-organization. The computer is important for advancing the understanding of complex systems because it allows scientists to play with simple but nonlinear models and to handle large sets of data obtained from complex systems.

The essential role of the computer is confirmed by historical studies showing (Fox-Keller, 2009) that the complex systems field is heir of the postwar sciences born around the computer: operational research, game theory and cybernetics. These fields started when physicists, mathematicians and engineers started collaborating to maximize the efficiency of WW II military operations [START_REF] Pickering | The mangle of practice[END_REF][START_REF] Bowker | How to Be Universal: Some Cybernetic Strategies, 1943-70[END_REF].

Let's now examine the various claims to universality. A "general systems theory" would possess a collection of theoretical books or papers revealing the "universal" explanation. This would be evidenced in Figure 5.2 by a central group to which other groups would connect. Instead, our analysis shows a variety of modelling disciplines in a central position. Certainly, a few theoretical papers, such as Bak's [START_REF] Bak | Self-organized criticality: an explanation of 1/f noise[END_REF] (in self-organized criticality) or Albert and Barabasi's (Albert & Barabasi, 2002) (in complex networks) point to "universal" mechanisms and are heavily cited. However, more than 80% of their citations arise from modelers themselves 3 , suggesting that they may be universal... for theorists. Our data support the local character of these "universal" laws. First, Albert and Barabasi's (Albert & Barabasi, 2002) 3 Counted on Web of Science (January 28th 2011) by analyzing the citing papers by discipline. Specifically, "Subject Areas" (Web of Science name for subdisciplines) related to Physics (such as Physics Multidisciplinary or Physics Mathematical) account for 2272 out of 3158 citations (72%) for Bak's paper [START_REF] Bak | Self-organized criticality: an explanation of 1/f noise[END_REF] while more "applied" subject areas (such as Geosciences and Applied mathematics) account for 676 citations (21%). Subject areas related to Physics or Mathematics account for 4201 out of 5281 citations (80%) of Albert and Barabasi's paper (Albert & Barabasi, 2002), while subject areas related to biology or more applied fields account for 1060 citations (20%). Instead, areas related to biology account for most of citations to Barabási and Oltvai's introduction of network theory to biologists (Barábasi & Oltvai, 2004). The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 40 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis.

Figure 5.6: 2010's french research subfield community networks. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 40 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis. fields are similar to those of the experimental fields. This means that the links between these modelling practices and their potential applications are mostly rhetorical: complex networks and self-organized criticality papers often quote experimental work as legitimating their models, while experimentalists rarely refer to them. To try to become universal, theoretical approaches have to be "translated" into other disciplines. An example of this strategy is shown in Figure 5.3d which shows the links established between network science and biology thanks to Barabasi and Oltvai's introduction of networks for biologists (Barábasi & Oltvai, 2004).

It could be argued that links between these theories and experimental fields take time to establish and will be seen in the future. An interesting insight of the possible evolution of universality claims is given by the history of self-organization, which was considered by many as a universal key to Nature in the 1980's [START_REF] Fox-Keller | Organisms, Machines, and Thunderstorms, a history of Self-Organization[END_REF]. This idea was fecund in that it gave birth to several active subdisciplines (cytoskeleton SO, growth SO...) (Figure 5.2). However, it should be noticed that these heirs of selforganization are nowadays almost unrelated. The different self-organization subfields are more linked to their own discipline (biology, materials science . . . ) than between them. This is shown by the plain fact that community detection puts these SO subfields into different disciplines (different colors in Figure 5.2) instead of creating a single, unified, self-organization field. The reason is that these subfields use widely different references, as illustrated by the fact that there is no common reference among the 10 most used references for all the different self-organization subcommunities. Self-organization is therefore not a universal explanation but rather a kind of banner, which needs to be associated to references to specific elements (including techniques, microscopic entities and their interactions) to be fruitful.

In summary, we have obtained a global point of view on the structure of the "complex systems" field. This has allowed us to test empirically the idea of universality, showing that it remains a dream, albeit one which has lead to interesting but more modest realities. At the global scale, the whole domain is linked by the focus on self-organization and the use of computer-based methods for solving non-linear models. At a more local scale, the links between different disciplines are achieved through the development of "trading zones" [START_REF] Galison | Image and Logic: A Material Culture of Microphysics[END_REF]. These allow for coordination between vastly different scientific cultures, for example theoretical and experimental disciplines, which are only marginally connected. These disciplines may differ on the very conception of what is an interesting topic, but can work together around specific tools (a DNA microchip) or concepts (a network). Today, these interdisciplinary collaborations are a key to essential scientific challenges such as the analysis of the massive amount of data recently made available on biological and social systems [START_REF] Lazer | Computational social science[END_REF]Microsoft, 2006) and the understanding of the complex intertwining of different levels of organization that is characteristic of these systems.

Methods

Extraction of the data

Our data have been extracted from the ISI Web of Knowledge database (WoS, 2011) in December 2008. The science of complex systems is particularly challenging as an epistemic object since there exists no consensual definition of the domain, nor any list of disciplines or journals that would gather all the relevant papers. Therefore, we selected all the articles of the database whose title, abstract (for articles published after 1990) or keywords contained at least one of a chosen list of topic keywords (Table 5.5). These keywords were derived from discussions with experts of the field, mainly scientists working at the complex systems institute in Lyon (IXXI). We have retrieved 215 305 articles (141 098 between 2000 and 2008) containing 4 050 318 distinct references. Each record contains: authors, journal, year of publication, title, keywords (given by the authors and/or ISI Web of Science) and the list of references of the article. Any choice of keywords being potentially biased and partial, our strategy was to risk choosing too many of them -thus bypassing the lack of precise definition of the "complex systems" field and retrieving all its important subfields -and to trust the subsequent analysis to eliminate irrelevant articles.

In fact, as shown in table 5.5, around 40% of the articles of the database comes solely from the combination of keywords "complex*" and "control". While most of those articles were close to biology and not directly related to the field of complex systems, we chose to keep them in order to test the robustness of our analysis. As shown below, our strategy was successful, since most of these "irrelevant" articles are grouped into a few communities (such as Apoptosis or Immunology) that lie at the network's edges and do not bias the results.

Links between articles

Weight of links between articles are calculated through their common references (bibliographic coupling [START_REF] Kessler | Bibliographic coupling between scientific papers[END_REF]. We define a similarity between two articles i and j as the cosine distance:

ω ij = |R i ∩ R j | |R i | |R j | (5.1)
where R i is the set of references of article i. By definition, ω ij ∈ [0, 1], is equal to zero when i and j do not share any reference and is equal to 1 when their sets of references are identical. For this study, bibliographic coupling offers two advantages over the more usual co-citation link: it offers a faithful representation of the fields, giving equal weight to all published papers (whether cited or not) and it can be applied to recent papers (which have not yet been cited). Moreover, the links are established on the basis of the author's own decisions (to include or not a given reference) rather than retrospectively from other scientists' citations. Thus, bibliographic coupling can be used to analyze the community of research as it builds itself rather than as it is perceived by later scientists that cite its publications.

Community detection and characterization

In order to structure this network into groups of cohesive articles, we partition the set of papers by maximizing the modularity function. Given a partition of the nodes of the network, the modularity is the number of edges inside clusters (as opposed to crossing between clusters), minus the expected number of such edges if the network was randomly conditioned on the degree of each node. Community structures often maximize the modularity measure. We compute our partition using the algorithm presented in [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], which is designed to efficiently maximize the modularity function in large networks. More precisely, we used the weighted modularity Q Girvan & Newman (2004); Fortunato (2010), which is defined as Q = I q I , where the module q I of a community I is given by

q I = Ω II Ω - J =I Ω IJ + 2Ω II 2Ω 2 (5.2)
where

Ω II = 1 2 i∈I, j∈I
ω ij is the total weight of the links inside community I,

Ω IJ = i∈I, j∈J
ω ij is the total weight of the links between communities I and

J = I Ω = 1 2 i,j ω ij = (i,j)
ω ij is the total weight of the links of the graph.

Each module q I compares the relative weight of edges Ω II Ω inside a community I with the expected weight of edges

J =I Ω IJ +2Ω II 2Ω 2
that one would find in community I if the network were a random network with the same number of nodes and where each node keeps its degree, but edges are otherwise randomly attached. See Ref Fortunato & Barthélemy (2007) for a more explicit interpretation of the modularity, its properties and limits.

Applying the Louvain algorithm yields a first partition of the network into communities (also referred to as "fields" or "disciplines", see Figure 5.1). To obtain the substructure of these communities, we apply the Louvain algorithm a second time on each of them. We find that most of these communities display a clear substructure with high values of internal modularity Q i (typically between 0.4 and 0.8). Only two of them (self-organized criticality and complex networks) are strongly bound around a few references and present much lower values of Q i (typically less than or around 0.2).

Consequently they were not split into subfields which would not have much scientific relevance.

This recursive modularity optimization leads us to a "subfield" graph (Figure 5.2).

We have checked that all the obtained sub-communities satisfy the criterion (q I ≥ 0)

proposed by [START_REF] Fortunato | Resolution limit in community detection[END_REF] to check their relevance (see Table 5.2).

Links between communities and their orientation

The link between two communities I and J can be quantified by the average distance between an article i ∈ I and an article j ∈ J:

< w > -1 IJ = < w ij > -1 i∈I,j∈J = (Ω IJ /N I N J ) -1 (5.3)
A link between a community I and a community J exists if at least one reference is shared between an article of I and an article of J. To analyze the scientific content conveyed by the link, it is important to know if the shared references are more similar to the references used by community I or to the references used by community J. To take into account this similarity, we define the orientation of a community-community link in the following way.

Let n r,I be the number of papers of community I using reference r. Then,

• the number of article-article links inside community I which use reference r is L r,II = n r,I (n r,I -1)/2

• the number of article-article links between communities I and J which use reference

r is L r,IJ = n r,I n r,J
We compare the set of references shared by the two communities I and J to the references used by I and J by computing the cosine similarity measures:

cos II,IJ = r L r,II L r,IJ r L 2 r,II r L 2 r,IJ comparing the shared refs to those of I cos JJ,IJ = r L r,JJ L r,IJ r L 2 r,JJ r L 2 r,IJ
comparing the shared refs to those of J For example, if cos II,IJ < cos JJ,IJ , the shared references are more similar to the references binding community J than to the references binding community I. We then direct the link from community J to community I, as community I "pumps" community J references to establish the link. See Figure 5.4 for examples of link orientation.

Networking power of references

To understand which references link the different subdisciplines to form a connected network, we define the "glue" as the set of references shared between subfields. To give equal weight to all these links, we normalize each link to 1, leading to the normalized networking strength N (r) of reference r as:

N (r) = 1 Z I =J f IJ (r) (5.4)
where f IJ (r) is the fraction of links between an article of community I and an article of community J in which reference r is used and where Z is a normalization constant such that r N (r) = 1. The normalization ensures that N (r) represents the proportion of all the links of the complex systems field that can be assigned to reference r.

CHAPTER 5. COMPLEX SYSTEMS SCIENCE: DREAMS AND REALITY 130 Table 5.5: Topic keywords used in our request in the ISI Web of Knowledge database and number of articles matching independently to each of these topic keywords. Each topic keywords except the first six where coupled with the topic keywords "complex*". We moreover rejected the articles containing the topic keywords "complex scaling" or "linear search", two terms refering respectively to (heavily used) specific methods of quantum chemistry and computer science. Mapping Science Institutions: the case of ENS de Lyon

Introduction

Scientometrics has proved a valuable tool to understand the organization of scientific fields [START_REF] Small | Visualizing Science by Citation Mapping[END_REF] and their evolution [START_REF] Chavalarias | The Reconstruction of Science Phylogeny[END_REF][START_REF] Mogoutov | Data search strategy for science and technology emergence: A scalable and evolutionary query for nanotechnology tracking[END_REF]. Global science maps [START_REF] Small | Visualizing Science by Citation Mapping[END_REF][START_REF] Klavans | Toward a consensus map of science[END_REF][START_REF] Small | Co-citation in the scientific literature: A new measure of the relationship between two documents[END_REF]Börner & Schernhost, 2009;[START_REF] Leydesdorff | A Global Map of Science Based on the ISI Subject Categories[END_REF][START_REF] Rafols | Science Overlay Maps: A NewTool for Research Policy and Library Management[END_REF][START_REF] Agarwal | Self-organising maps: applications in geographic information science[END_REF] have become feasible recently, offering a tentative overall view of scientific fields and fostering dreams of a "science of science" (Börner & Schernhost, 2009). In this article, we propose a more modest but less explored mapping, that of single scientific institutions. The scope is to achieve a global point of view on the institutions that no individual can have, in order to understand their organization, their strong and weak points, the papers or authors that link different Departments or disciplines... Such maps may become important as policy tools as few directors have such a global view of their institution.

Recently, Rafols and Leydesdorff have suggested a simple way to picture the disciplinary weight of an institution [START_REF] Rafols | Science Overlay Maps: A NewTool for Research Policy and Library Management[END_REF]. This method is rapid and can be carried out online. As it uses Web of Science (WoS, 2011) "subject categories" as relevant subdisciplines to project the data, it has the advantage of enabling a comparison across different institutions or years. The drawback of this rigid projection skeleton is that it preselects, without local information, the relevant communities. As acknowledged by Rafols and Leydesdorf (Rafols & Leydesdorff, 2010): "The two characteristics that make overlay maps so useful for comparison, their fixed positional and cognitive categories, are also inevitably, their major limitations and a possible source of misreadings. Since the position in the map is only given by the attribution in the disciplinary classification, it does not say anything about the direct linkages between the nodes."

Here we propose different ways of mapping scientific institutions based on the articles published with that address (and not the journals as in [START_REF] Rafols | Science Overlay Maps: A NewTool for Research Policy and Library Management[END_REF]).

We do not propose a real methodological innovation, but rather a toolbox that allows to draw, in a few hours, several maps of the chosen scientific institution. More specifically, we show four different ways of mapping our institution, ENS de Lyon, and show how each of these gives different information. Our scope is to display -in an accessible (but not too simplistic) way -the institution's complexity thus helping to generate discussions on its policy among its scientists.

Methodology

Data Extraction

The "Ecole normale supérieure de Lyon" (ENS de Lyon), focused on Natural sciences, was created in Lyon in 1987 after a move from Saint-Cloud in the suburbs of Paris.

In 2010, it merged with the "Social and Human Sciences" Ecole Normale Supérieure.

Today, it gathers 350 researchers, 270 professors, 390 administrative and technical personnel and a budget of more than 110 million Euros. A simple query (performed in January 2011) in the ISI Web of Knowledge database (WoS, 2011) yields 7584 papers containing an ENS de Lyon address (mostly under the form "Ecole Normal Super Lyon", but also "ENS-LYON" and "ENS de Lyon"). We save the "Full records" of all these articles, the records containing authors, journal, year of publication, title, keywords (given by the authors and/or ISI Web of Science), subjects, addresses (institutions, cities and countries), and the list of references of the articles. It is well-known that Social and Human sciences (especially French ones) are not well represented in Web of Science.

Therefore, our maps mainly deal with the natural sciences at ENS de Lyon.

Records are parsed and gathered in MySQL tables, which renders the handling of the data more straightforward. Simple frequency analysis of the records allows to a get a first global representation of the institution. Our method uses the relations present in the data [START_REF] Börner | Visualizing Knowledge Domains[END_REF] to display different perspectives on the inner structure of an institution.

Bibliographic coupling

Links between articles are calculated through their common references. The bibliographic coupling similarity between two articles i and j is defined as [START_REF] Kessler | Bibliographic coupling between scientific papers[END_REF]:

ω ij = |R i ∩ R j | |R i | |R j | (6.1)
where R i is the set of references of article i.

In comparison to co-citation link (which is the more usually used measure of articles similarity), bibliographic coupling (BC) offers two advantages: it allows to map recent papers (which have not yet been cited) and since it deals with all published papers (whether cited or not), it represents "normal science". The reason why weighted links are used is that they reinforce the dense (in terms of links per article) regions of the BC networks. This reinforcement facilitates the partition of the network into meaningful groups of cohesive articles, or communities. A widely used criterion to measure the quality of a partition is the modularity function [START_REF] Girvan | Finding and evaluating community structure in networks[END_REF][START_REF] Fortunato | Resolution limit in community detection[END_REF], which is roughly is the number of edges inside communities (as opposed to crossing between communities), minus the expected number of such edges if the network were randomly produced. We compute the graph partition using the efficient heuristic algorithm presented in [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF].

Applying the Louvain algorithm yields a partition of the network into communities (see Figure 6.2). Simple frequency analysis then allows to characterise each community through its more frequent items (keywords, authors, etc...). The significativity σ of the presence of a given item into a community is computed by comparing its frequency f in the community to its frequency f 0 within the whole database. More precisely, we use the normalized deviation

σ = √ N f -f 0 f 0 (1 -f 0 ) (6.2)
where N is the total number of article in the database. The links between two communities I and J can also be characterized qualitatively by analyzing their shared references and quantitatively by computing the mean weight ω IJ =< ω ij > i∈I, j∈J .

The final step in order to create a representation of the BC communities network is to choose a visualization algorithm. We use the Gephi software [START_REF] Bastian | Gephi: An Open Source Software for Exploring and Manipulating Networks[END_REF]. Gephi is a intuitive and interactive software allowing, in which force-directed layout algorithms are implemented. These algorithms produce a graph by simulating the dynamics of the network as if it were a physical system (the nodes being charged particles and the edges springs). The simulation is run until the system comes to an equilibrium state.

Subject

Copublication coupling

The data can also be analyzed through more common approaches, such as coauthoring or co-keyword analysis [START_REF] Börner | Visualizing Knowledge Domains[END_REF]. For this, a list of all items (authors, keywords, addresses) are taken from the records to obtain the nodes of our maps, whose size are proportional to the number of articles in which they appear. Two nodes (items) i and j are linked whenever the number n ij of articles in which they both appear is non-zero.

More specifically, we use weighted links, where the co-occurrence normalized weight is chosen as

w ij = n ij √ n i n j (6.3)
The visualization step of the produced maps is once again achieved through Gephi and its force-based layout algorithms.

Software available

We have developed a "Biblio Toolbox" which allows to draw the different maps presented here in a few hours. The toolbox needs access to Web of Science database but otherwise CHAPTER 6. MAPPING SCIENCE INSTITUTIONS 135 relies on OpenSource software. It is available at our website (http://www.sebastiangrauwin.com/).

6.3 Gaining perspective on the ENS de Lyon

Statistical analysis

ENS de Lyon gathers a broad spectrum of scientific subjects (Table 6.1), mostly in the natural sciences as discussed above. The institution has significantly grown over the last 20 years, as shown by its increasing production of papers (Fig 6 .1). Our data gathers 12398 distinct authors, among which 952 have authored more than 5 papers.

By construction of the database, at least one author of each article is a member of ENS de Lyon but this number also takes into account all the authors of the papers among whom some may not be members of the ENS. ENS de Lyon collaborates with a broad range of institutions of different countries as shown below.

Bibliographic Coupling communities map

Figure 6.2 shows the map obtained with bibliographic coupling of articles and their grouping into "natural" subfields through modularity maximization. Each community is characterized by its more frequent author and keyword. Table 6.2 displays an "ID card" for the community labelled Hansen JP/Molec-Dynamics. This community gathers physicists interested in the understanding of condensed matter using molecular dynamics simulations. The "ID Cards" of the other communities are available online on http://www.sebastian-grauwin.com/.

What do we learn from this first map? First, note that the spatial organization of the communities fits well with the scientific organization of ENS de Lyon in different departments (different colors in Figure 6.2). This confirms that bibliographic coupling can recover the scientific organization of institutions. Interestingly, the precise community structure does not match the inner administrative/scientific subdivision of departments.

For example, the physics lab is administratively divided into four groups, while our map distinguishes seven teams. This raises interesting questions on the structuration of the groups and their interactions. Two physics' communities (Oswald P/LiquidCrystals and Peyrard M/DNA) belong to the "soft-matter and biological systems" group but our map shows that they are quite distant, which means that they do not share many references.

The difference between the map and the physics lab organization is one example of the discussions that our work can generate.

Another example is given by the overall spatial structure. Our map clearly places physics at the scientific center of the ENS de Lyon, a fact that was used by its director to suggest the importance of his lab within the institution. The question is then : how much does this central position depend on the precise visualization algorithm used? Is it robust enough to allow for an interpretation and possibly orient governance? The forthcoming maps will comment on this issue, but let us already note that the central position of the Physics Lab within this representation is quite robust. The reason is quite simple : the Physics Lab is the only one to have strong links to the other labs.

Indeed, different physics' communities are linked to all other labs (for example Mathematics and Computer science (through Livine E/Quantum gravity), to Biology (through Peyrard M/DNA)...). The other labs are strongly linked only to one or two other labs (for example, Biology is only linked to Chemistry, through Pichot C/Adsorption, in addition to its link with the Physics lab), which explains their more peripheral position in the map. Therefore, the central position of the Physics lab can tentatively be interpreted as its central position in terms of modelling tools (molecular simulations tools Figure 6.2: "Bibliographic Coupling" community structure of the ENS de Lyon. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling. For the sake of clarity, communities with less than 10 articles are not displayed. Labels are obtained thanks to a frequency analysis of the authors and keywords. Each color corresponds to one of the ENS de Lyon scientific departments : biology (green), chemistry (yellow), physics (pink), computer science (red), mathematics (violet), earth sciences (blue) and astrophysics (turquoise). The belonging of a community to a department is determined through the proportion of community's articles that use the department (for an example, Table 2 shows that more than 50% of "HansenJP/Molec-Dynamics" articles' display the Physics Lab in the address). shared with chemists for example), experimental tools (on "frictional mechanics" with the geophysics lab for example) or theoretical concepts (spin glass theory also studied by mathematicians). All these shared tools generate common references which lead to the links that structure our map.

International collaborations

It is straightforward to use the communities of the preceding map to include the international collaborations of the different teams (Fig. 6.3). We simply define links as given by the frequency of appearance of a foreign country in the community's articles addresses.

For example, the strongest link is obtained for the Astrophysics papers, for which 41% of the papers are written in collaboration with a USA institution. The map shows that some groups rely heavily on many international collaborations (Emsley L/RMN has strong links with England, Italy and USA), while others are strongly linked to a single country (Dauxois T/Long range inter, to Italy) and others have mainly French collaborations (Oswald P/Liquid crystals).

Figure 6.3: International collaborations of the communities. The size of the nodes correspond to the number of articles in each community which imply a collaboration with a foreign country. We only keep countries appearing in more than 10 articles and links corresponding to more than 3% of the articles implying a collaboration with the linked country. The width of the links is proportional to the proportion of linked articles.

Co-keywords, co-authors and heterogeneous maps

We now turn to more traditional maps, obtained by co-occurrence of keywords or authors in articles. Figure 6.4 shows the co-keywords map obtained by using Web of Science and authors' keywords. One should be cautious since some terms are clearly polysemic ("evolution", "particles"...) and create links between subdisciplines which are not very relevant. However, it is clear that physics is no longer at the center of the map. Instead, "crystal-structure" links chemistry (top left) with biology (right), "growth" links biology to physics and "transition" and "dynamics" link chemistry to physics (left). Another significant difference : what appeared to be a coherent whole when investigated through bibliographic coupling (the "Albarede F/Geodynamics" community) turns out to split into geochemistry (bottom of Figure 6.4) and geophysics (just up of the latter, close to physics, with keywords as "high-temperatures" or "high-pressures"). To improve over the limitations of both co-keyword and co-author analysis and gather most of the available information in a single map, it is possible to include all the co-occurrences between keywords, authors and institutions. Fig. 6.6 shows the map obtained for the ENS de Lyon. It displays the connecting rôle of a physics-biology interdisciplinary lab (Lab Joliot Curie, center right). One can also see that, while the CNRS plays an important an central rôle, other institutions collaborate on more specialized subfields (for example Univ California, Berkeley, lower left).

Discussion, Conclusions

Our aim in this chapter was to present a toolbox to make institution mapping easy and rapid and to show on the example of our institution, ENS de Lyon, what kind of insights can be derived from these maps. It should be clear by now that there is not a unique (or a "best") map of a scientific institutions, but rather many possible representations, each map containing a projection from a specific perspective [START_REF] Leydesdorff | A Global Map of Science Based on the ISI Subject Categories[END_REF]; [START_REF] Roessner | Quantitative and qualitative methods and measures in the evaluation of research[END_REF][START_REF] Stirling | Opening up" And "Closing down": Power, participation, and pluralism in the social appraisal of technology[END_REF].

We are now experimenting with ENS scientists' and direction. ENS heads are enthusiastic about this global vision and five posters representing this chapters' figures are now displayed in the building. We hope that scientists at ENS de Lyon will test these maps against their own knowledge of the institution, will argue with us when what we picture does not fit and join the public discussion by offering alternative interpretations.

As Nietzsche said (Nietzsche, 1969): "the more affects we allow to speak about one thing, the more eyes, different eyes, we can use to observe one thing, the more complete will our 'concept' of this thing, our 'objectivity' be". The point is that although everybody acknowledges that maps are only representations and not the real thing, maps affect how we think about the institution [START_REF] Wood | The Natures of Maps: Cartographic Constructions of the Natural World[END_REF].

We hope that our toolbox will lead other scientists to build maps of their own institutions, thus fostering ongoing dialogue and praxis in the institution. Future work includes preparing different maps for successive time periods, in order to grasp the evolution of the institution, and collaboration with other institutions (such as CNRS and CEMAGREF) which are interested in such global maps. The Whole is Smaller than the Sum of its Parts: a Tentative Tardean Model

Word of caution: for more than a year, we have been meeting a team of sociologists led by Bruno Latour at Science Po Medialab. In the frequent discussions, we have been trying to define the essential bricks of a sociologically grounded model, focusing on the social theory developed by Gabriel Tarde at the end of the 19th century. Most of the time, however, was devoted to mutual understanding and to development of a common language. This was the case for me at least! The introduction of this chapter is an attempt to summarize the main ideas that came up in our discussions. I hope that the unavoidable misunderstanding and distortions of sociological ideas will be forgiven.

Introduction

The individual / society dichotomy Various sociological theories try to apprehend social phenomena under different points of view. Hence, according to the holistic paradigm which is issued from Emile Durkheim's ideas, individuals are embedded into social structures and institutions that constrain them, shape their actions and emotions. Social facts (such as social classes) are notions pre-existing the individuals that should be taken as primary and most significant to explain social phenomena. On the contrary, in the atomic (or individualistic) paradigm, individuals should be considered as the central ontological elements in social systems.

According to this notion, each individual is a social atom, linked to other atoms and which acts in function of its interests and desires. Constant interactions between the atoms construct society, ie structures, institutions, norms, which are supposed to serve the interests of the individuals.

Both the holistic and the atomistic approaches are based on a strong assumption:

there is a clear dichotomy between two "levels", namely individuals and society. This clear distinction of two levels is often summarized by the notion that "the whole is greater than the sum of its parts". This assumption is put into question in some recent approaches (see Latour et al, forthcoming). According to these approaches, the distinction between two levels is an artefact originating in the difficulty of navigating through huge amounts of data and in visualizing the evolution of social phenomena without making a distinction between the individual and the aggregated levels.

From KISS to KIDS

A clear example of the "atomistic" approach are agent-based models, which attempt to recreate complex collective phenomena through the interactions of "rational", utilitymaximizing agents. Examples of such models include :

• Schelling's segregation model [START_REF] Schelling | Dynamic models of segregation[END_REF], which uses individual interactions to explain the emergence of segregation on a global scale

• Large-scale models were proposed by Axelrod (1997). They simulate the emergence of global phenomena such as exchange markets, seasonal migrations... starting from individual interactions between simple agents.

• Opinion dynamics, whose main scope is to understand why cultural diversity can persist at the global level even when individual interactions push towards convergence. These models have specifically interested a growing number of physicists (for a recent review, see Science, 2009;[START_REF] Castellano | Statistical physics of social dynamics[END_REF].

• Many additional examples can be found in the Journal of Artificial Societies and Social Simulation (http://jasss.soc.surrey.ac.uk/JASSS.html).

In the last decades, "atomic" agent-based models demonstrated their importance to overpass the severe limitations of current theoretical frameworks, especially in the modelling of economic phenomena. They allow to move beyond equilibrium states to study transient regimes, which show far more complex and interesting behavior. They overpass the drastic simplifications needed to warrant analytical treatments (such as agents' homogeneity, cognitive closure in game theory...). A key principle common to most of these model is known as K.I.S.S. ("Keep it simple, stupid", Axelrod (1997)).

Indeed, in the various effort to model social phenomena, the main tradition has so far mainly consisted in starting from discrete atomic entities endowed with the smallest set of properties and to see whether or not, through their interactions, it would be possible to obtain the emergent phenomena most often associated with the notion of society (For a recent overview of this approach, see Cho, 2005). In this tradition, the success of the model often lies on finding the minimal sufficient rules for atoms and interactions allowing to obtain the maximal number of structural features. A Tardean approach for understanding social data

Therefore, it seems interesting to build a model able to follow the emergence and evolution of social structures or institutions with two specific starting points :

• there should not be any ontological distinction between "agents" and "structures"

ie no notion of levels

• following the KIDS principle, agents should be taken as complex as possible A good starting point to overpass the individual-structure paradigm may well be the work by Gabriel Tarde, a 19th century sociologist whose work has been somewhat dormant in the social science during the 20th century, but has been recently unearthed and given a new impetus by the development of Actor-Network Theory [START_REF] Latour | Reassembling the Social -An Introduction to Actor-Network-Theory[END_REF][START_REF] Barry | Gabriel Tarde: Imitation, invention and economics[END_REF][START_REF] Latour | Tarde's idea of quantification[END_REF].

The central element in Tarde's theory (see [START_REF] Tarde | Monadologie et sociologie[END_REF][START_REF] Tarde | Les lois de l'imitation[END_REF] is the monad, a concept originally developed by Leibniz. For Tarde, there is no need for a notion of overarching society and there is no individual to begin with either: everything is a monad, that is a representation, a reflection, or an internalization of a whole set of other elements borrowed from the world around it [START_REF] Latour | Tarde's idea of quantification[END_REF]. A monad has to be understood as an entity with some asperity which can be linked to other entities. An individual is a monad defined by the set of links towards all the entities that characterizes the individual (in a sense, his "profile", or curriculum vitae, ie a list of everything the individual has done in the past, the people he has seen, the clothes he has worn...). A group of people is a monad defined by the the set of links towards entities that defines them (/ that they have in common). A neuron is a monad defined by the set of neurons connected with it. There is not a single entity that can be defined per se, every entity is defined by its "profile", i.e. the set of entities to which it is linked (Figure 7.1). Each "individual" entity is then a "whole" by itself. In Tarde's ontology, there are no individuals, no wholes, only monads, monads connected to monads, monads within monads. . . Monads perfectly match our conditions: they are complex entities which go beyond the notions of agents and structures. Still, how can social phenomena be understood in terms of monads? Tarde proposed two notions to explain social phenomena: imitation 1

1 In Tarde (1890)'s words: Quel est le fait social élémentaire ? C'est la communication ou la modification d'un état de conscience par l'action d'un être conscient sur un autre. (...) parler à quelqu'un, prier une idole, tisser un vêtement, scier un arbre, donner un coup de couteau à un ennemi, sculpter une pierre, ce sont là des actes sociaux, car il n'y a que l'homme en and invention. Everybody imitates what or who he admires, things that he finds good for him, but creates an original mix from the imitated models chosen at different sources.

History can be understood as successive imitative fluxes, successive successful models copied by a large number of individuals. Imitation is a natural counterpart of the notion of monad. Indeed, conceiving individuals as monads means conceiving them as a large set of reflections. We find pieces of each other in one another, and choose to imitate pieces of one another. In Tarde's terminology, our choice of things to imitate and the way we innovate by combining them is driven by beliefs and desires.

Let us finally stress an important point, which is the relation between monads and the usual notion of "structural features" or wholes. For Tarde, what is usually taken as "structural features" are the intersections of complex individual monads (Figure 7.2).

In some sense, for him, the whole is always simpler and smaller than the parts. . . These structures evolve in time because the monads themselves combine differently the elements of the world but may repeat and keep unchanged some feature (the keyword "self-organization" persist in time while the authors citing it change over time), which Tarde calls imitative rays.

In next section, we describe a tentative model describing a virtual society built on Tarde's precepts. Our goal is to emphasize and discuss the harsh constraints imposed by the need for properly defined, complete and coherent algorithms required for simulations.

Needless to say, the positive side of these constraints is to force social theorists to provide better definitions of their concepts !

A Tentative Tardean Model

We present in this section an attempt to formalize Tarde's ideas into a mathematically defined model to allow the construction of a simulation algorithm. To build models of interactions between complex agents, we have greatly benefited from discussions with Guillaume Beslon and we have freely gleaned in a wide literature, mainly [START_REF] Holland | Building Blocks, Cohort Genetic Algorithms and Hyperplane-Defined Functions[END_REF][START_REF] Dawkins | The Selfish Gene[END_REF]Kauffman, 1993;[START_REF] Gilbert | Innovation Networks -A Simulation Approach[END_REF]. A discussion on the difficulties encountered in this exercise follows in next section.

The model considers a population of N complex agents (i = 1, 2, ...N ) completely characterized by a sequence S i = (s i1 , s i2 , ...s iL ) of L 1 bits. In analogy with what is done in genetic algorithms (see for example [START_REF] Knibbe | A long-term Evolutionary Pressure on the Amount of Non-coding DNA[END_REF], we assume the existence The agents can imitate each other by copying parts of each other bits' sequences if they are linked. The initial interaction network is taken as an Erdös-Rényi network of average degree K, ie the agents are initially linked to K neighbors.

The dynamics of the systems is defined as follows: at each interaction, an agent i is picked at random. Then, one of two following processes occurs :

• With a probability α 1 , imitation occurs.

A neighbor j of the picked agent i and a random sequence of agent j is chosen at random. Agent i then imitates agent j by copying the sequence of bits in his own sequence (at the same position) with a probability:

P 1 = 1 1 + exp -β 1 (f (S i ) -f (S i )) (7.1)
where f (S i ) is the fitness of agent i sequence and f (S i ) the fitness his sequence will have if he decides to imitate. The parameter β 1 allows for some tuning of the imitation process. For β 1 1, imitation will occur if and only if it implies an increase in agent i fitness. For β 1 1, the probability to imitate does not depend on the fitness value and agent i decision is just random.

• With a probability α 2 , innovation occurs.

A bit l ∈ (1, ..., L) of agent i is chosen at random. Agent i will to choose to 'innovate' by flipping this bit with a probability

P 2 = 1 1 + exp -β 2 (f (S i ) -f (S i )) (7.2)
where f (S i ) is the fitness of agent i's sequence and f (S i ) the fitness his sequence will have if he decides to innovate. Here again, the parameter β 2 allows for some tuning of the influence of the fitness function on the innovation process.

Obviously, the parameters α 1 and α 2 (where α 1 + α 2 = 1) define the ratios between the time scales on which each process occurs. The parameters β 1 and β 2 measure the influence of noise in the agents' choices

In order to understand the rationale behind these rules, we discuss the expected qualitative evolution of the model. When agents are completely isolated (ie not linked to other agents), the only way to increase their fitness is by a succession of inventions in their sequences, which will happen on a rather long time scale (since only one bit is changed at each time). When the agents are connected, two processes will accelerate the increase in fitness. First, longer sequences may be exchanged in a single iteration.

Second, "good" sequences may be imitated and therefore act like social coordinators, forming stable "structures" or "institutions".

Depending on the exact definition of the fitness function, a large phenomenology of collective events can be expected. If the fitness function is constant, each sequence is a priori equivalent. In case there is no innovation (α 2 = 0), one expect that the agents will converge in the long run toward the same sequence S * . With our choice of W and D, one can even expect this sequence to correspond to the sequence of initial majority bits (ie for each l ∈ (1, ..., L), s * l = 1 if i s il > N/2, and s * l = 0 otherwise). If invention is added, there will be a competition between imitation and invention, the imitative process promoting convergence of the agents' sequences and the invention process promoting diversity.

Suppose now that the fitness function has a single maximum, eg by taking f (S) = l s l (meaning that the fitness function increases linearly with the number of 1 in a sequence). In case there is no innovation, once again we expect a convergence toward a consensus sequence S * . However, even if the agents are rational imitators (β 1 1), the consensus sequence does not necessarily correspond to the optimum sequence in terms of fitness. Indeed, all it takes for imitating a sequence is an increase in fitness. A 'second-best' sequence such as '11110111' would be imitated by most of the agents and could diffuse and impose itself to the general population. In a sense, there is a competition between imitation and optimization that can temper the collective optimization.

Turning rational (β 2 1) innovation on would allow here the agents to mutate their sequence to obtain a fully optimal sequence. If innovation is more random (β 2 finite), the invention process promote diversity and there is here again a competition between imitation and invention.

In case of more complex fitness functions presenting several local maxima (see Figure 7.3), more complicated collective behaviors are obviously expected. In line with Tarde's intuition, we do not expect a single sequence to dominate all the society. We rather anticipate that these local maxima will affect the dynamics by "recruiting" agents in some "niches" (ie the patterns of sequences allowing to reach those maxima). These standardized niches will endure through time before being modified again through agent's innovations. We therefore expect global trend towards complexification of sequences, leading to an overall increase of agent's fitness. An important and tricky part of the work consists in playing with the numerous parameters of the model to obtain these satisfactory outputs.

Obviously, all these speculations are only anticipations whose validity has to be checked. Some unpredictable consequences of the chosen dynamic rules, parameters, fitness function may very well be uncovered through actual simulations.

Discussion

The different elements present in our model has been chosen to fulfil Tarde's prescriptions. Our agents have been chosen as complex entities : long binary sequences. Moreover, sequences and sequences define at the same time the agents and the structures (diffusing sequences). Hence, in our model there is no ontological distinction between agents and structure, which is exactly what we wanted at the beginning. In agreement with Tarde's sociology, our model offers a complete reversibility in following how agents come to agree by simplifying themselves through the influence of diffusing sequences, and following how these sequences spread among populations of agents by modifying themselves and "recruiting" agents interested in them. In that sense, these diffusing sequences adopted and sometimes modified by the agents are similar to Tarde's 'imitative rays'. Moreover, once a sequence has been accepted by an agent, it changes the agent's perception of all the other sequences (through the utility function), making these perceptions more similar to the perceptions of all the agents sharing this sequence.

If our model manages to recover important Tardean features, several of the choices we made are debatable. The main problem we encountered was to find a proper explicit criterion for deciding whether an agent should choose to imitate or not, innovate or not, etc... Tarde bases the agents' choices on the notions of belief and desire. We choose to transcribe these notions in a unique, constant in time fitness function, which already shows complex collective behaviors. From a sociological point of view, this fitness function gives a strong foundation to the social outcomes without completely determining them (for a given complex fitness function, the states of the systems might depend on the initial conditions, some random processes. . . ). This 'monolithic' extrinsic aspect may however appear at odds with the common notion of beliefs and desires. In another version of the model, individual and dynamic fitness functions could emerge as a result of the agents' interactions and choices. Another possibility would be to introduce individual effective fitness functions. In this hypothesis, the existence of a unique objective function is assumed, but the agents are not aware of it. They use their own filtered versions obtained through experience and social interactions. But could we define properly those effective fitness functions?

Our choices of dynamic rules are also debatable. We use logit probabilities mostly by convenience, while the logit form is a priori no more justified than any other form taking into account the fitness variations. The same criticism applies to the other (un)explicit choices. For example, we could choose to work in a whole connected society rather than on a random network, or allow the agents to change neighbors instead of assuming a static interaction network. The general question we encountered while trying to formalize Tarde's ideas hence was : what are the good criteria to judge that we have built a 'good' model, or that the simulation outputs could be interesting?

The answer we reach here is that the formalization of a theory is not sufficient to built a complete, ready-for-simulations model. In order to complete this framework, one should start from the study of a specific social phenomenon and derive precise rules from analysis of real data...

Chapter 8

Lasting Structures from Non Lasting Entities

One of the central questions of sociology is the durability of institutions at the human time scale : how can lasting structures emerge from non lasting entities? This is one of the recurrent topics of our discussions with the Medialab team. Here we show a simple model, inspired by models proposed by physicists, which tackles this question.

The relevance of such a model for the real social world is discussed at the end of this chapter.

Introduction, motivation

One of the standard strands of models for physicists interested in social systems are the so-called "opinion" models. As often in this field, one should be cautious about the terms, because "opinion" refers here only to a drastically simplified image of this rich social concept, i.e. a real or integer number supposed to distinguish among different possible opinions. These models introduce interactions between the agents which lead to changes in agents' opinions and the links they establish with other agents. Various models differ on the precise nature of the opinion (whether it is discrete or continuous, uni or multi-dimensional), on the topology and the dynamics of the interaction network (complete graph, regular lattices, random graph, scale-free network, static or adaptive network), on the precise rule of interaction between agents . . . (for a recent review, refer to Castellano et al., 2009, and references therein).

A central question investigated by these models is the persistance of pluralism of opinion in a more and more connected world, in which individuals are constantly imi-tating each other. In Axelrod (1997)'s word: If people tend to become more alike in their beliefs, attitudes and behaviors when they interact, why do not all differences disappear ? Most of these models concentrate on the study of the final states of the system. There are several possibilities : either all agents end up into a single cluster (consensus), or several opinion clusters form, containing a significant fraction of agents (polarization), or alternatively agents are scattered on a large number O(N ) of clusters (fragmentation).

Most papers are focused in obtaining the well-balanced polarized state, because the two extremes of consensus or fragmentation are trivial outcomes. Axelrod (1997) and [START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF] are two widely known examples of models with imitating agents which yield polarized final states. However, the stability of the polarized state rests on a -rather unrealistic -strict interaction rule allowing agents to interaction only if their opinions are close enough. If this strict condition is softened (eg by introducing some noise), the polarized states become instable and the system reaches consensus [START_REF] Klemm | Nonequilibrium transitions in complex networks: A model of social interaction[END_REF][START_REF] Kozma | Consensus formation on adaptive networks[END_REF]. To improve the robustness of the polarized states, recent models have introduced an "adaptive" rewiring of the network, allowing agents to dynamically rewire their links to agents with similar opinions [START_REF] Holme | Nonequilibrium phase transition in the coevolution of networks and opinions[END_REF][START_REF] Kozma | Consensus formation on adaptive networks[END_REF][START_REF] Iñiguez | Opinion and community formation in co-evolving networks[END_REF]. This rewiring leads to the creation of more stable polarized states. As [START_REF] Kozma | Consensus formation on adaptive networks[END_REF] claimed : the behavior of the model on adaptive networks is in fact more robust than on static networks, since the same global picture [polarized states] is observed for strict or probabilistic communication rules. However, a close inspection of the probabilistic interaction rules they use reveals that these are asymmetric and rather artificial. Actually, the probability for two neighbors with an opinion difference less than d to break their link is strictly 0 (see [START_REF] Kozma | Consensus formation on adaptive networks[END_REF]. While this asymmetry prevents agents close enough in opinion to break their links and therefore prevents any disaggregation of clusters, it is not clear if the stationary states of their model remain robust when this rule is softened.

In this chapter, we build on a modified version of [START_REF] Kozma | Consensus formation on adaptive networks[END_REF] to investigate this question and try to obtain structures that last from entities that do not last, as our friends sociologists request. We first show that by introducing a more natural, symmetric noise in the interaction rule, the rewiring process is not sufficient to avoid a collapse towards consensus in the long run.

o i (t + 1) = o i (t) + µ(o j (t) -o i (t)) o j (t + 1) = o j (t) + µ(o i (t) -o j (t)) (8.2)
where µ ∈ [0, 1/2] is a convergence parameter. We will assume here that µ = 1/2, meaning that both agents i and j adopt the same opinion once they have interact. We also introduce a possibility for link rewiring. To do so, we suppose that at each iteration, with a probability p break = 1 -p conv , the link between i and j is broken and a new link between agent i and a randomly chosen agent is created. In our simulation, we typically take ω = 5, meaning that two neighbors sharing the same opinion will break their link with a probability ∼ 0.01.

Finally, we introduce the fact that agents are "non lasting" entities. For this, after the agent and one of its neighbors have been selected and the interaction/rewiring process has been carried out, with a probability ν we change randomly its opinion while keeping the same links. This can be interpreted as the "death" of the agent and the birth of another one, with different characteristics (different opinion) but belonging to the same group (same links). In other words, the agents' average lifetime is 1/ν.

To summarize, on each step we do the following:

• 1. Pick an agent i at random. If that agent has no neighbor, do nothing. Otherwise, pick one of its neighbors j and continue the process.

• 2. Generate a random number r ∈ [0, 1].

• 3. If r < p conv (i, j), then the opinions of i and j converge according to

o i (t + 1) = o i (t) + (o j (t) -o i (t))/2 o j (t + 1) = o j (t) + (o i (t) -o j (t))/2
• 4. Else (ie if r ≥ p conv (i, j)) update the link between i and j:

Choose a randomly chosen agent k which is neither i nor i's neighbor Connect i to k and break the link between i and j.

• 5. With a probability ν, update agent i: o i takes a new random value between 0 and 1.

Following [START_REF] Kozma | Consensus formation on adaptive networks[END_REF], we track the evolution of the system by detecting the opinion clusters of agents. Defining opinion neighbours as two linked agents whose difference of opinions is smaller than the tolerance threshold d, an opinion cluster is defined as a set of agents such that between any two of these agents there exists a path of opinion neighbours. Compared to topological clusters which track the connected component of the network, opinion clusters tracks the set of agents between which a path of communication (∆o < d) exists.

Results

The detailed analysis of our model is still in progress. In this section, we only present some simulation outputs illustrating the different behaviors obtained by varying the different parameters. In all the simulations presented here the opinions of the agents are initially randomly chosen between 0 and 1, the number of agents is fixed to N = 1000, the average degree to K = 10 and the tolerance threshold is fixed to d = 0.04.

Reference case : no noise, no death

In order to investigate the effects of each parameter, we start with the reference case, where ν = 0 (ie without opinion noise or, in our interpretation of ν as a typical lifetime, with "immortal" agents), and with no leakage (ω 1). This last condition is fulfilled These polarized states are the typical outcome obtained in the case of no opinion noise and no leakage (at least for small d and reasonable values of N and K), and correspond to the results obtained by [START_REF] Kozma | Consensus formation on adaptive networks[END_REF].

Introducing opinion leakage

We now investigate the effect of the introduction of leakage. Do we still obtain several stable opinion groups when we introduce a small probability for neighbors with close opinions to break their link and neighbors with very different opinions to interact?

Lasting Structures from Non Lasting Entities

We now introduce an additional feature to the model: the opinion noise or death/birth cycle of the agents. Obviously, the introduction of agents born with a random opinion tends to counteract the unavoidable convergence of opinions implied by the leakage.

Two time scales are now relevant : a characteristic coalescence time t coal (see above)

and the characteristic lifetime 1/ν of the agents. For νt coal 1, the coalescence process is preponderant and the system converges towards a consensus state with some fluctua- Clearly, the number of opinion clusters depend on d, but also on ν and ω (which controls t coal ). Preliminary analysis suggest that at short time scales, clusters randomly diffuse both in number of agents and average opinion (Figure 8.4). This brownian motion arises by death of the clusters' agents and capture of free agents that are born close in opinion space. At longer time scales however, this random drift is limited by the cluster-cluster correlations induced by the interactions of the capture zones of neighboring clusters in CHAPTER 8. LASTING STRUCTURES FROM NON LASTING ENTITIES 165 opinion space. This competition for newborn agents leads to a strong stability of the total number of clusters, which last for times much longer than the agents' lifetime.

Addition of Generation Effects

At this point, we have managed to obtain long lasting structures (the opinion clusters) from perishable agents. Actually, from a sociological point of view, the structures might even last too long, since they never seem to decay. The reason of the stability of these structures is the simplicity of the opinion space, which leads to easy assimilation of newborns by existing opinion clusters. In other words, the one-dimensional opinion space is too homogeneous to allow for a complex collective behavior.

We have started to explore the effects of including a last ingredient to the opinion space, namely "generation" effects. Specifically, we keep the same model, but we replace in Eq. 8.1 the simple opinion distance ∆o by a combination of opinion and age distance,

where the age a(t) of an agent is simply the number of normalized iterations it has lived since its birth. Eq. 8.1 then becomes :

p conv (i, j) = 1 1 + exp (ω ( |∆o| 2 + |ν∆a| 2 -d)/d) (8.3)
The term ν∆a introduces heterogeneity in the opinion space : for example, two agents with similar opinions but widely different ages (measured in ν units) may easily break their link. A (pseudo)sociological rationale for this ingredient would be that different generations may see the opinion space differently. Fig 8.5 shows an example of the complex phenomena produced by generation effects. On short time scales (compared to 1/ν), opinion clusters still exist and are rather stable. On longer time scales, we observe that some opinion clusters disappear by progressive death of their agents, while others can recruit young agents and last for hundreds of agents' lifetimes. We also see merging of clusters close enough in opinion and growth of a new cluster in the space left free by this fusion. We are currently investigating this rich phenomenology, trying

to understand what determines clusters' distinct evolutions, to quantify their lifetime, their evolution in opinion space (random walk?), how mergers can be predicted . . .

Discussion

The work presented in this chapter focuses on simple models of "opinion" clustering, of the emergence and persistence of structures that can last longer than individuals that give rise to them. We have developed a series of models that lead to robust polarized states and dynamical equilibria. The last model reminds us of a classic sociology text, Georg Simmel's study of the persistence of social groups [START_REF] Simmel | The Persistence of Social Groups[END_REF] : it is meaningful to speak of group identity, despite shifting membership and low institutionalization, if there is some membership continuity in contiguous stages [...] The change, the disappearance and entrance of persons, affects in two contiguous moments a number relatively small compared with the number of those who remain constant. The departure of the older and the entrance of the younger elements proceed so gradually and continuously that the group seems as much like a unified self as an organic body in spite of the change of its atoms.

Despite this parallel, we do not think that this kind of simplistic model should aim at being realistic by inclusion of additional ingredients. Rather, our discussions with Sciences Po's sociologists open another direction. We speculate that these models can help them enriching their conceptualizations of the structuration phenomenon. This could arise from a detailed examination of the structuration that happen in this virtual society and their tentative interpretation using the usual sociological theories. Does this confrontation help them in any way in renewing their conceptual repertoire? Do we observe group evolutions that are unexpected and difficult to explain? The future of this stimulating and demanding collaboration will tell! aa aa

Conclusion Recapitulation

The original motivation for this thesis was to explore social phenomena using tools derived from statistical physics, and more generally quantitative tools. Most of our work was concentrated on three different projects which all share a central question, that of the relation between individual and collective, aggregated entities.

The first part of the thesis focused on Schelling's segregation model. We believe that our work has strongly contributed to the development of a deeper understanding of the mechanisms at stake in this paradigmatic model. We hence investigated in Chapter 1 the robustness of unwanted global segregation patterns in respect with the introduction of coordination between the agents' moving decisions. Our simulations of different forms of taxation or induced collaboration between the agents showed that even a small amount of coordination can significantly reduce unwanted segregation.

We then presented in Chapter 2 a framework for Schelling's model which allowed us to derived general and unprecedented analytical results. Specifically, we were able to characterize the global configurations of a virtual city by a potential function which maximizes the stationary states -at least for a given range of the individual utility functions. We showed in particular that in the context of continuous neighborhood, the only solvable case was the one already presented by Zhang (2004a), ie the case of linear utility functions. We hence put forward the concept of bounded neighborhood -an alternative way to define the network of interactions of the agents in the city. In In chapter 4, we presented our analytical approach in a more general framework,

showing how it could apply to a wider range of socio-economic models.

In the second part of the thesis, we explored huge databases on scientific literature (mostly Web of Science) to investigate the existence and evolution of paradigms or scientific institutions.

Chapter 5 hence tackled the question of the existence and coherence of "complex system science". Starting from a large database (141 098 records) of relevant articles published between 2000 and 2008, we measured a scientific similarity between articles thanks to the bibliographic coupling approach -based on shared references -and we detected the field communities emerging from these interactions. These 'natural communities' presented a far richer structure than the usual partition of science in fixed disciplines or institutions. Our analysis of this structure revealed that the overall coherence of the 'complex systems' field does not arise from a universal theory but rather from computational techniques and fruitful adaptations of the idea of self organization to specific systems. We also put forward the existence of 'trading zones', ie small communities creating an interface between disciplines around specific tools or concepts. The place of complex systems science within the whole landscape of science was also investigated in two preliminary maps representing French 2000 and 2010 natural science communities.

While Self-Organization, Self-Organized Criticality and Complex Network do constitute coherent subfields in those maps, no unified conceptual kernel for "complexity science" is identified.

In Chapter 6, we presented a set of routines allowing to draw different maps of the research carried out in a scientific institution. We took the example of our institution, ENS de Lyon, to show how different maps, namely co-occurrence (of authors ,keywords, institutions) maps and bibliographic coupling communities maps, can be built and what kind of information they can provide. We emphasized the fact that these different maps, based on the same elements, offered different views on the institutions at the global scale.

Finally, in the third part we presented the work that resulted from our collaboration with a team of sociologists from the MediaLab at Sciences Po.

Chapter 7 hence questioned the assumption of a clear dichotomy between two 'levels', namely individuals and society. Building on the social theory developed by Gabriel

Tarde at the end of the 19th century, we explored different possibilities to visualize (and therefore conceptualize) the evolution of social phenomena without making a distinction between two levels. Bibliometric data were used as an example. We also proposed an attempt to formalize Tarde's theory in the scope of an algorithmic model. While our prototype model fulfilled several of Tarde's precept, it raised many more questions.

In Chapter 8, we focused on a single question, namely the existence of lasting structure from non lasting entities. We built on the -more standard -physicist approach developed in opinion model. While most papers focus on the stationary properties of the model, we chose to build a model to investigate the dynamical properties of social structures which are always changing. The key ingredients of the model we presented are the use of adaptive network, the introduction of noise in the agents' interactions, a turnover in the population of agents and the introduction of generation effect, the agents taking into account their opinion and age difference in their interaction. The outcomes of our model display a rich phenomenology of group dynamics.

Approach

The research presented in this thesis was performed in a strong interdisciplinary spirit.

Indeed, for each research project we took great care to tackle the questions at the heart of these projects in a mutually beneficial way for both social and natural sciences.

Hence, our work on economics's aspects of Schelling model in chapters 1 an 2 is counterbalanced by a the presentation of aspects of this resolution that may be of interest for a physicist in chapters 3 and 4. In the same way, our discussion on the nature of social entities of the chapter 7 is counterbalanced by chapter 8.

If this balance is somehow necessary to ensure the permanence of a collaboration between researchers from different disciplines, it is my firm belief that these interdisci-plinary collaborations's worth comes from the development of new ways of thinking and of conceptualizing the objects of one's discipline.

Perspectives

Several extensions of the work presented in this thesis could be explored.

As stated in chapter 4, we believe that the concept of 'link' potential function could be applied to other systems. [START_REF] Lemoy | Socio-economic utility and chemical potential Europhysics[END_REF] The conclusions we drawn in chapter 5 on the nature of complex systems science are based on a particular database issued from the Web of Science, and mostly on one technique: bibliographic coupling. It would hence be interesting to check the robustness of our conclusions with other databases selected with different criteria than ours, or by using other techniques for defining a similarity between articles. A possibility could be to performed co-word analysis, ie defining a similarity based on the nature and number of words -for example the word present in the titles and abstracts -shared by the articles.

We hope that the toolbox we presented in chapter 6 will lead other scientists to build maps of their own institutions, thus fostering ongoing dialogue and praxis in the institution. The policy issues raised by the utilisation of bibliometrics indices and such 'maps of sciences' are certainly not going to disappear and that is why we think it is important that these tools may be known and accessible to everyone. A collaboration with other institutions (such as CNRS and CEMAGREF) which are interested in such global maps have already begun. Future improvement of our toolbox will include the possibility to prepare different maps for successive time periods, in order to grasp the evolution of the institution. It might also be interesting to couple the bibliometric data that can be obtained on the Web of Science with data accounting for the other activities of the researchers of an institution (teaching, patents, ...).

Finally, our collaboration with sociologists is still on its way: the main perspective of the third part of this thesis is to continue to develop and explore the kind of models we presented. Is it possible to build a solid bridge between physicists' models starting from simple agents and Tarde's theories demanding to start from complex monads?

For S -1 ≤ H/2, it is straightforward to write: The computation of ∆F in relation 2.38 is based on the expression of F (S) (equation A.18), which gives, with K ∈ {0, 1, ..., H/2}: densities and also equal to the slope connecting these two points, ie,

F (S) = 2 H S-
∆F = 2 F (H/2 + 1 + K) + 2 F (H/2 -K) -2 F (H/2 + 1) -2 F (H/2) = 2 H H 2 + K H 2 + K + 1 + H 2 -K -1 H 2 -K - H 2 H 2 + 1 - H 2 -1 H 2 - 2(2 -m) H K(K + 1) = 2m H K(K + 1)
f (ρ 2 ) -f (ρ 1 ) ρ 2 -ρ 1 = f (ρ 1 ) (B.2) f (ρ 2 ) -f (ρ 1 ) ρ 2 -ρ 1 = f (ρ 2 ) (B.3)
For the computation of functions depending on the global state of the city such as the normalized collective utility U * (x) = U (x)/ q n q , two cases have to be distinguished

• The case when there is one phase of density ρ 0 . In this case, the utility of each agent is equal to the normalized collective utility :

U * (x) = u(ρ 0 ) (B.4)

• The case when there are two phases of densities ρ 1 and ρ 2 . In this case, the normalized collective utility can be written as

U * (x) = γ ρ 1 ρ 0 u(ρ 1 ) + (1 -γ) ρ 2 ρ 0 u(ρ 2 ) (B.5)
with the conservation of the number of agents providing the value of the fraction γ = (ρ 2 -ρ 0 )/(ρ 2 -ρ 1 ) of blocks of density ρ 1 .

B.2 Asymmetrically peaked utility function

The specific form of the utility function is an input of the model, and it can be postulated on a phenomenological basis, or rely on a theory of the interactions among agents. To illustrate the influence of the parameter α, we choose to work with the asymmetrically peaked utility function defined as:

u(ρ) = 2ρ if ρ ≤ 1 2 u(ρ) = m + 2(1 -m)(1 -ρ) if ρ > 1 2
where m < 1 is a real parameter. Let us first consider the limiting case T → 0. From the above expression of f (ρ), it turns out that f (ρ) is convex for 0 < ρ < 1/2 and concave for 1/2 < ρ < 1, as 1 -m > 0.

Thanks to Fig. B.2, it is pretty clear that there exists ρ 2 (α, m) > 1/2 such that a phase of mean density ρ 0 is stable if ρ 0 ≥ ρ 2 (α, m). In the opposite case, a phase separation occurs, and the densities ρ 1 and ρ 2 can be computed as previously explained.

However, in the limit T = 0, the line joining ρ 1 and ρ 2 does not correspond to a double tangent. Due to the concavity of f on [0, 1/2], one has ρ 1 = 0, but f (0) = 0 while the slope of the line is negative. To determine ρ 2 , we first assume that 1/2 < ρ 2 < 1, so that the line joining ρ 1 = 0 to ρ 2 is a tangent to f at ρ 2 , which is expressed as: From Eq. (B.9), we find that ρ 2 is in the range 1/2 < ρ 2 < 1 if (and only if) the following condition is satisfied: The situation ρ R ≤ 0.5 and ρ G > 0.5 can be obtained by replacing g ↔ r in the previous paragraph.

f (ρ 2 ) = 1 ρ 2 f (ρ 2 ) -f (
For T = 0 f is concave in ρ R and ρ G for ρ R and ρ G ≤ 0.5. For ρ R > 0.5 and ρ G ≤ 0.5, f is concave in ρ R and convex in ρ G (and conversely for ρ R ≤ 0.5 and ρ G > 0.5, f is concave in ρ G In part B the system is split into 3 phases of densities (0, ρ 2 ), (ρ 2 , 0) and ( 1 2 , 1 2 ) in respective quantities

Q 1 = Q ρ 2 (2ρ 0G -1)+ρ 0R -ρ 0G 2ρ 2 (ρ 2 -1) , Q 2 = Q ρ 2 (2ρ 0R -1)+ρ 0G -ρ 0R 2ρ 2 (ρ 2 -1) and Q 3 = Q ρ 2 -ρ 0R -ρ 0G ρ 2 -1 .
In part C the phase decomposition is the same as in part B of case 1 and in part D it is the same as in part C of case 1.

Case 3

The different domains of phase decomposition are shown on figure B.9.

In part A of figure B.9 the system separates into 3 phases like in part A of case B.

In part B there are 2 phases of densities (ρ 0R + ρ 0G , 0) and (0, ρ 0R + ρ 0G ) in respective

quantities Q 1 = Q ρ 0R ρ 0R +ρ 0G and Q 2 = Q ρ 0G ρ 0R +ρ 0G .

Interpretation

At zero temperature, the two populations model is indeed very similar to the one population model: both populations of agents see each other only as occupied cells (the utility of a red agent does not depend on the number of green agents in the block).

The only difference with two superimposed one population models lies in the fact that blocks with density ( 1 2 , 1 2 ) are full of agents with maximal utilities and cannot take in more agents, so that for certain values of the global densities, in cases 1 and 2, there of the Royal Society of London. Series B, Biological Sciences, 237(641), 37-72. Venter, J.C., Adams, M.D., Myers, E.W., Li, P.W., Mural, R.J., Sutton, G.G., Smith, H.O., Yandell, M., Evans, C.A., Holt, R.A., et al. 2001

C.3 Communities "ID cards"

We present in this section the "ID Cards" of the six most discussed communities of the subfield community network, ie lists of the most frequent keywords, journals of publication, articles refered to and journal refered to. These ID Cards allow to grasp in a fairly good way the scientific content of a given community. For each decade, we report the number of articles within the bibliographic network, the modularity Q f , the number of field communities C f containing more than T hr articles (and total number of articles N f within) of the field community network obtained by the first run of the Louvain algorithm. The second run of Louvain algorithm performed independently on each field lead to subfields community networks whose modularity Q sf and number of communities C sf (of size superior than T hr) are also reported. Note that the finer partition of the subfield network comes with a lowering of the modularity. This double recursive use of a modularity optimization was also used by [START_REF] Fortunato | Resolution limit in community detection[END_REF], on smaller networks (less than 1000 nodes) and with another community detection algorithm. They noted that by restricting modularity optimization to a [single community during the second application of Louvain algorithm], we neglect all links between the original communities and we have no guarantee that we accurately detect its substructure and that this is a safe way to proceed. Thus, we have to check whether all substructures we detected are real [communities], ie if a subcommunity of a given up community is also a community of the entire network. To do so, they propose a simple criterion: a set I of articles is a suitable community if: q I ≥ 0 (D.1)

where q I is the module of a community as defined in Eq. 5.2. We found that this criterion was well respected for all the subfield communities in all the networks we built. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 100 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis. Figure D.5: 1995Figure D.5: -2004's subfield community network. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 100 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis. -2009, 1995-2004, 1990-1999 and 1985-1994 decades). The procedure leading to these diagrams is explained in the main text. The relative position of the communities are here meaningless.

  As soon as 1969, Thomas C. Schelling proposed a model aiming at formalizing the aggregate consequences of individual preferences regarding the social environment

  's work, continuous neighborhood models describe cities where the neighborhoods are centered on the local perception of each agent. In a continuous neighborhood description, one assumes that the neighborhood of an agent is composed of the H nearest locations surrounding him. The H = 4 "Von Neumann neighborhood" and the H = 8 "Moore neighborhood" that are displayed among other examples on Fig 2.1 are the most commonly used neighborhoods in agent-based computational models.

Figure 1 . 1 :

 11 Figure 1.1: Different forms of neighborhood. Red, green and white squares denote respectively red agents, green agents and vacant cells. The neighborhood of an agent corresponds to his H nearest cells/locations. Around the agents marked in yellow, we enlightened by the white frontiers a H = 4, a H = 8, a H = 24 and a H = 44 continuous neighborhood. [If you printed this document in black and white, the red and green squares should appear respectively in dark grey and soft grey.]

Fig 1. 3 Figure 1 . 3 :

 313 Fig 1.3 displays some examples of configurations along with their s * -values. The reference value s * = 0 corresponds to an average random configuration. Positive values of s * mean that the agents have more similar neighbors than in the random case,and negative values that their neighborhood contains less similar neighbors than in an average random case. A maximum value s * = 1 corresponds to the case where all the neighbors of all agents belong to their own group. Practically, given the random fluc-

  Figure 1.4: Evolution towards a highly segregated configuration starting from a random configuration in the case of the WC rule. Top panel. Some snapshots of the evolution of the city for a noise level T = 0.1; Bottom panel. Evolution with τ of the index of similarity and of the collective utility for different simulations with different noise levels. The grey dots on the T = 0.1 curves correspond to the snapshots presented on the top panel. m = 0.5.

Fig. 1 .

 1 Fig. 1.4 further shows that the level of noise has an effect on the fluctuations of s * and U * in the stationary phase. While these fluctuations are rather low for T = 0.05, their amplitude increases with T before reaching a saturation value. Finally, while further studies would be necessary to characterize the influence of T on the time needed to reach the stationary phase, one can infer from fig 1.4 that as T decreases, this transition time increases.The influence of the parameters T and m on the stationary configurations can be observed on Fig.1.5 and 1.6. For high values of T (T ≥ 0.5), the dynamics is essentially governed by the randomness introduced in the logit. In the limit T 1, the agents are distributed uniformly in the corresponding stationary configurations, which induces a similarity index equal to zero for all values of m. In this case, the probability p(s) for an agent to have a fraction s of similar neighbors being independent of m and thank to the bilinear form of the asymmetrically peaked utility function, the collective utility can

Figure 1 . 6 :

 16 Figure 1.6: Stationary mean values of the similarity index and of the collective utility as a function of m, for different level of noise T . The error bars give the standard deviation of the fluctuations of s * and U * once the system has reached its stationary phase. The mean value and standard deviation are computed over 10 periods of the stationary phases (when the fluctuation are important, we use larger temporal windows).

Figure 1 . 7 :

 17 Figure 1.7: Snapshots of typical stationary configurations of the city for different values of α and m. The introduction of partial coordination can destabilize the highly segregated configurations and leads to configurations which present structured mixed patterns. T = 0.1 and H = 8.

Figure 1 . 8 :

 18 Figure 1.8: Stationary mean values of the similarity index and of the collective utility as a function of m, for different tax level α, with the partial coordination dynamic rule. The error bars give the standard deviation of the fluctuations of s * and U * once the system has reached its stationary phase. The mean value and standard deviation are computed over 10 periods of the stationary phases. T = 0.1 and H = 8.

Figure 1 . 9 :

 19 Figure 1.9: Snapshots of typical stationary configurations of the city for different values of Hg, θ and m. The introduction of tax proportional to the level of segregation at the district level can destabilize the highly segregated configurations and leads to configurations which present structured mixed patterns. T = 0.1 and H = 8.

Figure 1 . 10 :

 110 Figure 1.10: Stationary mean values of the similarity index, collective utility and tax as a function of m, for different district size Hg, with the feasible tax rule. The error bars give the standard deviation of the fluctuations of s * and U * once the system has reached its stationary phase. The mean value and standard deviation are computed over 20 periods of the stationary phases. T = 0.1, H = 8.

  model which favours values of s H greater than 0.5 and the tax mechanism which favours values of s Hg below 0.5. The results obtained for H g = H = 8 corresponds to what we stated above based on the transformed utility function: for m ≥ m c + θ/2, the segregation patterns that exist in the WC case vanish. 1.5 A local coordination by voting 1.5.1 Basic setup We define the co-proprietors of an agent as the agents living on the h nearest cells surrounding him. Here, h is a fixed integer which verifies h ≤ H. Co-proprietors represent in a stylized way next-door neighbors or the people living in the same residential building whereas the neighbors represent the people living in the same street or in the same district. Examples of possible forms of neighborhoods and co-properties are shown below in Fig 1.11.

Figure 1 . 11 :

 111 Figure 1.11: Examples of neighborhood and co-property used in our simulations. A red agent is located on the central cell. His co-property corresponds to the orange cells and his neighborhood to the orange and white cells. From the left to the right, (H = 8, h = 4), (H = 24, h = 4) and (H = 44, h = 4).

Figure 1 . 12 :

 112 Figure 1.12: The introduction of local coordination destabilizes the highly segregated configurations and leads to configurations which present locally mixed patterns. Top panel: some snapshots of the evolution of the city for T2 = 0.1 and h = 4. Bottom panel: evolution with τ of the index of similarity and of the collective utility, the grey dots on the T2 = 0.1 curves corresponding to the snapshots of the top panel. T = 0.1 and m = 0.5.

Figure 1 . 14 :

 114 Figure 1.14: Stationary mean values of the similarity index and of the collective utility as a function of m, for different level of noise T2, with the qualified vote dynamic rule. The error bars give the standard deviation of the fluctuations of s * and U * once the system has reached its stationary phase. The mean value and standard deviation are computed over 10 periods of the stationary phases. The plots corresponds to a neighborhood size H = 8, a co-properties size h = 4 and a noise level T = 0.1. The black curve corresponds to 'Without Coordination' simulations that have been performed using the same parameters.

Figure 1 . 15 :

 115 Figure 1.15: Stationary mean values of the similarity index and of the collective utility as a function of m, for different level of noise T2, with the qualified vote dynamic rule. The error bars give the standard deviation of the fluctuations of s * and U * once the system has reached its stationary phase. The mean value and standard deviation are computed over 10 periods of the stationary phases. The plots correspond to a neighborhood size H = 44, a co-properties size h = 4 and a noise level T = 0.1. The black curve corresponds to 'Without Coordination' simulations that have been performed using the same parameters.

Figure 2 . 1 :

 21 Figure 2.1: Different forms of neighborhood. Red, green and white squares denote respectively red agents, green agents and vacant cells. a. Example of a bounded neighborhood in which the city is divided in square blocks containing H + 1 = 25 cells/locations; b. In the case of a continuous neighborhood description, the neighborhood of an agent corresponds to his H nearest cells/locations. Around the agents marked in yellow, we enlightened by the white frontiers a H = 4, a H = 8, a H = 24 and a H = 44 continuous neighborhood. [If you printed this document in black and white, the red and green squares should appear respectively in dark grey and soft grey.]

  be an aggregate function describing each of the potential configurations. By definition, F will be a (cardinal) potential function of our model if and only if each gain in utility ∆u of a moving agent is equal to the variation ∆F that is induced on the global level by the move of this agent. 4 A cardinal potential function will thus verify: F(y) -F(x) = ∆ xy u with ∆ xy u previously defined (section 2.2.4).

  number of green-vacant pairs of neighbors.This last form provides a convenient interpretation of the potential function. Putting aside at this point the last two terms, F(x) is proportional to ρ RG , that gives a measure of the relative contact between the two groups. Hence, the sign of the prefactor b-(a+d)/2 indicates whether mixed states (when positive) or segregated states (when negative) are obtained at the global level. Notice that the two groups do not need to both have strong preferences for like neighbors for segregation to emerge. It is the average preference over the two groups that determines the level of segregation.The terms proportional to ρ RV and ρ GV show that agents avoid the proximity of vacant cells when a > 0 and d > 0. All these insights gained from the study of the potential function can be checked by means of simulations (Fig 2.2).

Figure 2 . 2 :

 22 Figure 2.2: Typical stationary configurations obtained by simulations for different values of (adb). Top panel: for 2b -(a + d) < 0, the system evolves towards segregated configurations where red and green agents tends to live in different blocks. Bottom panel: for 2b -(a + d) > 0, the system evolves towards mixed configurations where the number of red-green pairs of neighbors is maximized. From left to right: the sign of a and d controls the tendency of red and green agent to prefer to live in dense or uncrowded areas. The demographic parameters are (N = 20, v = 10%, nR = 0.5). Neighborhood size is fixed to H + 1 = 16 and the level of noise is T = 0.1

Figure 2 . 3 :

 23 Figure 2.3: Asymmetrically peaked function for some values of m.

  The same is observed with simulations. The snapshots presented on the left panel of Fig.2.4 are typical stationary configurations obtained by simulating an artificial city where the agents' preferences are given by the asymmetrically peaked utility function with bounded neighborhoods. These snapshots allow us to compare the analytical results obtained for v → 0 and T → 0 with a more realistic v = 5% and T = 0.1. We can see that for values of the asymmetry parameter m close to 0, the system converges toward randomly-organized mixed configurations which also maximize the utility of most agents. On the contrary, for higher values of m, completely segregated configurations are obtained. The transition between these two extreme outcomes occurs for values of m included between 0.05 and 0.2. The relative smoothness of this transition is due to the non-zero values of the vacancy rate and of the level of noise.

Figure 2 . 4 :

 24 Figure 2.4: Typical stationary configurations obtained by simulations with the asymmetrically peaked utility function. The demographic parameters are (N = 30, v = 5%, nR = 0.5). Neighborhood sizes are fixed to H = 24, and the level of noise is fixed to T = 0.1. Left: with a bounded neighborhood description. Right: with a continuous neighborhood description.

  Fig. 2.4 present stationary configurations obtained using a continuous neighborhood description. The left panel of Fig. 2.4 shows the influence of a bounded neighborhood on the stationary configurations obtained with the same parameters. Mixed random configurations are obtained in both bounded and continuous neighborhood descriptions for low values of m and segregative patterns also appear in both descriptions for high values of m.

  Fig 2.1a. We may define a second partition Q 2 of the city lattice in such a way that blocks of partition Q 2 overlap with blocks of partition Q 1 . Fig 2.5b shows an example where partitions are shifted from each other by a half a block's diagonal. Let us assign to each red (resp. green) agent the two blocks

Figure 2 . 5 :

 25 Figure 2.5: Illustration of the expected effects of a "two partitions" model. a In the one partition model, homophilic preference leads to a pattern where blocks are exclusively populated by either red or green agents as seen in Fig 2.4. In this case however, agents are not aware of the composition of nearby blocks. b In the two partitions framework (in each partition, blocks are delimited by either white or blue lines), nearby blocks of a given partition have a transitive influence on each other through the overlapping blocks of the other partition. The same segregative dynamics implying a minimization of the number of mixed blocks of either partition will lead to a gathering of same-color blocks.

  solution of Schelling segregation model for bounded neighborhoods and two homogeneous groups of agents with general utility functions. This represents a major step forward compared to previous work, mostly based on computer simulations or providing analytical results for specific models. We showed that the stationary configurations reached following the selfish individual moves of the agents maximize a potential function under mild conditions on the agents' utility functions. This potential function can be interpreted as the sum of the agents' utilities as they move into their neighborhood, starting from a totally empty city. In other words, the potential function cumulates the incentives the agents had to move into the neighborhood where they are located.Thanks to this potential function, we are able to solve Schelling model with general utility functions. This step forward was enabled by a partial reduction in the heterogeneity of agents' neighborhoods through the use of bounded neighborhoods. This allows one to keep track of how each individual move affects the global configuration. Instead, when continuous neighborhoods are used, this information is lost because the way a moving agent affects his past and new neighbors depends on factors (the type of their neighbors' neighbors) that are not fully determined by the agent's decision. Therefore, it is generally impossible to know how an individual move affects a function of the global configuration unless the utility functions are linear.We used the potential function to assess the outcomes of our location model for different utility functions, representing different degrees of preference for mixed environments.We examined successively linear utility functions, Schelling original utility function and asymmetrically peaked utility functions. The first two utility functions lead to segregated stationary configurations. In the linear utility case (and for meaningful values of the parameters), the segregated configurations, that maximize the potential function, also maximize the collective utility. With Schelling original utility function, a divergence between collective utility and the potential function appears. Asymmetrically peaked utility functions lead to segregated configurations even for a slight asymmetry, because this asymmetry provokes moves to slightly segregated neighborhoods that will never be compensated by reverse moves. Note finally that when the vacancy rate approaches 0, any pair of utility functions gives a potential function that allows to characterize the stationary configurations.Our analytical approach helps understanding the ingredients that contribute to the paradoxical result that has generated interest for Schelling model. Even if the dynamics is governed by agents moving to improve their own utility, the evolution leads to city configurations in which most of the agents are far from being satisfied. The results presented in this chapter show rigorously what the two main ingredients of segregation are. First, the most important element driving segregation is the asymmetry of the utility function. Symmetric functions do not lead to segregation. Once utility functions favor a majority status over a minority status, segregation is found, even if agents have a strict preference for mixed environments, as in the asymmetrically peaked utility function. The second important element is the existence of externalities. As already noted byZhang (2004b) and[START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF], the existence of externalities explains why individual preferences for integrated environments may lead to segregated configurations. Indeed, location choice by an agent is only based on her own utility level, even if it also affects her neighbors' utility levels. This makes mixed neighborhoods unstable and segregated configurations very stable. The unstability of mixed neighborhoods is particularly clear in the block configuration for the asymmetrically peaked function. Starting with the

Figure 3 . 1 :

 31 Figure 3.1: Configurations of a city composed of Q = 36 blocks containing each H = 100 cells, with ρ 0 = 1/2. (a) Mixed state. Stationary state of the city for m = 0.5, α = 1 and T → 0. Agents are distributed homogeneously between the blocks, each of them having a density of 0.5. (b) Segregated configuration. Stationary state of the city for m = 0.5, α = 0 and T → 0.Agents are gathered on 20 blocks of mean density 0.9, the other blocks being empty. In the original Schelling model[START_REF] Schelling | Dynamic models of segregation[END_REF], each agent has a distinct neighborhood, defined by its 8 nearest neighbors. Here, we only keep the essential ingredient of blocks of distinct densities. Our model shows the same qualitative behavior as Schelling's but can be solved exactly, thanks to the partial reduction of agent's heterogeneity.

  Figure 3.2: Asymmetrically peaked individual utility as a function of block density. The utility is defined as u(ρ) = 2ρ if ρ ≤ 1/2 and u(ρ) = m+2(1-m)(1-ρ) if ρ > 1/2,where 0 < m < 1 is the asymmetry parameter. Agents strictly prefer half-filled neighborhoods (ρ = 1/2). They also prefer overcrowded (ρ = 1) neighborhoods to empty ones (ρ = 0).

Figure 3 . 3 :

 33 Figure 3.3: Phase diagram of the global utility as a function of the cooperativity α and the asymmetry m, at T → 0 and ρ 0 = 1/2. The average utility per agent U * = U/(ρ 0 HQ) is calculated by maximizing the potential F (x) for the peaked utility shown in Fig. 3.2, see Appendix B. The plateau at high values of α corresponds to the mixed phase of optimal utility, which is separated from the segregated state by a phase transition arising at α c = 1/(3 -2m). The overall picture is qualitatively unchanged for low but finite values of the temperature, see appendix B.

Figure 3 . 4 :

 34 Figure 3.4: Phase diagrams for the asymmetrically peaked individual utility (Fig. 3.2, with m = 0.8) for different values of T . Increasing the temperature T tends to favour homogeneous states. For small but finite temperatures (roughly T < 0.2), the phase diagram is modified only for extremal values of ρ 0 , as expected from the entropic term T s(ρ) = -T ρ ln ρ -T (1 -ρ) ln(1 -ρ).As T is increased, the whole diagram is affected by the entropic term. Compared to the T = 0 case, the main change is the appearance of a second homogeneous phase for ρ 0 < 1/2. But while for ρ 0 > 1/2 homogeneity corresponds to the optimal choice for the agents, for ρ 0 < 1/2, collective utility is not maximized in a homogeneous city. The city is homogeneous by noise, not by choice. Note that an increase in α tends to reduce this domain, while it tends to increase the homogeneous domain for ρ 0 > 1/2.

Figure 3 . 5 :

 35 Figure 3.5: Stationary configurations obtained by simulating the evolution of a city inhabited by a equal number of red and green agents whose preference are given by the asymmetrically peaked utility function (m = 0.5). The rate of vacant cells (in white) is fixed to 10%. Top panel. The city is divided into blocks of size H = 100. In accordance with the analytic model, a segregated configuration is obtained when α = 0 (snapshot a) and a more homogeneous configuration is obtained for α = 1 (snapshot b). Bottom panel. The utility of an agent depends on the local density of similar neighbors computed on the H = 108 nearest cells. While of different topological nature, a segregated configuration is still obtained for α = 0 (snapshot c) and a homogeneous configuration is still obtained for α = 1 (snapshotd). In all those simulations, we take T = 0.1. The small amount of noise hence generated, while not changing the nature of the stationary states compared to the case T → 0, conveniently reduces the time of convergence of the system.

CHAPTER 4 .

 4 EFFECTIVE FREE ENERGY FOR INDIVIDUAL DYNAMICS 100 pave the way to analytical treatments of a much wider class of systems, where dynamics is governed by individual strategies. Quantitative solutions of two models are also provided as examples.

Figure 4 . 1 :

 41 Figure 4.1: Stationary values derived by a maximization of L for N = 5000 (in red) and N → ∞ (in black) commuters. (a) Normalized proportion of arriving agents ρ t = n t /H. (b) Normalized proportion of agents on the road Q t /H, where Q tis the number of agent queueing on the road at a given time t. It is computed as the difference between the number of departed and arrived agents Q t = t t =0 d t -n t , where the distribution of departure time {d t } is deduced from the distribution of arrival time {n t } and travel time {T T (t)}. See[START_REF] Chu | Endogenous trip scheduling: the Henderson approach reformulated and compared with the Vickrey approach[END_REF] for more details on this procedure. The computations have been realized in the limit T → 0, with the parameters values t * = 900, α = 2, β = 1, ν = 4, γ = 4, h = 4. 10 -4 .

  Figure 4.2: (a). Asymmetrically peaked individual utility as a function of block density. The utility is defined as u(ρ) = 2ρ if ρ ≤ 1/2 and u(ρ) = 3/2 -ρ if ρ > 1/2. Agents strictly prefer half-filled neighborhoods (ρ = 1/2). They also prefer overcrowded (ρ = 1) neighborhoods to empty ones (ρ = 0). (b) Stationary configurations of a virtual city for T → 0. Blocks are separated in two phases with different densities of agents. (c) Stationary configurations of a virtual city for T1. Agents are distributed homogeneously between the blocks. The city is composed of Q = 36 blocks containing each H = 100 cells, with a mean density ρ q = N/HQ = 1/2.

Figure 5 . 2 :

 52 Figure 5.2: Community structure obtained with a second run of the modularity maximization on the 2000-2008 network. This community structure is obtained by optimizing the internal modularity Q i of each community obtained by the first run of the modularity maximization algorithm on the 2000-2008 network, displayed on Figure 5.1 (See Methods for details on the procedure). The surface of each community is proportional to its number of articles and the width of the link between two communities I and J is proportional to the mean weight ω IJ . For the sake of clarity, communities with less than 300 articles and links with a mean weight ω IJ less than 2.10 -5 are not displayed. The color of a community (see online) corresponds to the color of the field (Fig 5.1) it belongs to. Community labels are based on a frequency analysis of the keywords. For a detailed presentation of the subfields, including their authors, most used journals, references and keywords, see Appendix B.

Figure 5 . 3 :

 53 Figure 5.3: Local "networking" force for four different references on the 2000-2008 network (Fig 5.2). Links established using the reference are shown in color. The number of citations corresponds to those included in papers of our database published between 2000 and 2008. References used: a. Albert & Barabasi (2002) (2058 citations) b. Press et al (2010), Numerical Recipes -all editions (1267 citations) c. Nicolis & Prigogine (1977) (342 citations) d. Barábasi & Oltvai (2004) (244 citations).

Figure 5 . 4 :

 54 Figure5.4: Directed network. On this subset of the graph presented in Figure5.2, the arrows are directed to the subfield that uses the other subfield's references to establish the link. More precisely, the common references shared by two linked subfields are more similar to the internal references of the subfield from which the arrow originates than to the internal references of the subfield to which the arrow points (see "Methods" for more details). The figure shows that transcriptional data analysis (TDA) feeds from self-organizing maps (SOM) and neural networks (NN) methodological references, while biology subcommunities (mainly Transcriptomics) use transcriptional data analysis references. The orientation of the links is quite different for computational systems biology (CSB) and complex networks (CN), because these subfields tend to pump their neighbors' references, while the other subfields do not find much use in computational systems biology and complex networks references.

  's relation to the overall scientific literature To explore the question of the relation of CSS to the overall science, we present two preliminary maps displaying the communities obtained from a database containing records of the overall French scientific literature of 2000 and 2010 (as obtained from the Web of Science). We try to point out the place of CSS in these overall maps. We have gathered the records of the 63840 articles published in 2000 and the 78058 articles published in 2010 containing a french address from the ISI Web of Knowledge database (WoS, 2011, query performed in March 2011 ). We present in this section the two preliminary maps of the state of French research in 2000 and 2010, obtained once again by computing the bibliographic weight between articles and detecting the communities thanks to the Louvain algorithm.

  paper is the most cited in the 2000-2008 decade but only links complex networks and self-organized criticality subfields (Figure 5.3a). The contrast with the global networking achieved by methodological references such as Metropolis' algorithm or Numerical Recipes (Figure 5.3b) or self-organization references (Figure 5.3c) is clear. Second, the references that complex networks (Figure 5.4) and self-organized criticality communities share with experimental

Figure 5

 5 Figure5.5: 2000's french research subfield community networks. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 40 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis.

Figure 6 . 1 :

 61 Figure 6.1: Number of paper with an ENS de Lyon address published by year, according to WoS, January 2011.

Figure 6 .

 6 Figure 6.5 displays a co-author map. This represents an accessible way of showing data to the institutions' scientists, since names are usually well-known by the community. It also represents a good way to tap into directors' previous knowledge of the institution. However, coauthorship indicates quite a different (and stronger) link from the link established by sharing references (as in bibliographic coupling). This is visible in Figure 6.5 which does not show many links across disciplines (and some of the links are actually homonyms, such as Bertin E). The main co-publication link arises from collaborations between a biophysics lab and computer simulations of biological molecules (Peyrard/Bouvet/Gilson).

Figure 6 . 4 :

 64 Figure 6.4: Co-Keywords Network. The size of the nodes is proportional to the number of times a keyword is used in our database. The width of the links indicates the cooccurrence weight between two keywords in the same article. We keep only keywords used in more than 10 publications. Colors correspond to a community analysis performed by gephi based on the same Louvain algorithm used for the Bibliographic Coupling analysis.

Figure 6 . 5 :

 65 Figure 6.5: Co-Authors Network (detail). The size of the nodes is proportional to the number of articles of our database authored by the author. The width of the links indicates the cooccurrence weight between two co-authors. We keep only authors used with more than 5 publications. Colors correspond to a community analysis performed by Gephi based on the same Louvain algorithm we used for the bibliographic coupling analysis.

Figure 6 . 6 :

 66 Figure 6.6: Heterogeneous Network, mixing authors, keywords and institutions. The size of the labels is proportional to the number of articles of our database in which an item appear (we keep only items used in more than 20 publications). The width of the links indicates the cooccurrence weight between two items (we kept only links with a co-occurrence weight ω > 0.1). Colors correspond to the type of the items (authors in black, keywords in blue and institutions in red).

Figure 7

 7 Figure 7.1: 'Profile' of the keyword self-organization. This co-occurrence map shows the keywords, references and addresses of the articles which use the keyword selforganization (the central node without label) between 1996 and 2000 according to the Web of Science c . Refer to chapter 6 for the method of construction of such maps.

Figure 7 . 2 :

 72 Figure 7.2: Keyword self-organization considered as a 'whole' produced by the intersection of 'monads' (articles) which are far richer than this single keyword. We use the 18 articles published in 1991 which use the keyword self-organization (the central node without label) and built the co-occurrence map of their authors, addresses and keywords as in Figure 7.1. To highlight the idea of 'intersection', the attributes of three 'monads' (articles) are shown surrounded by a circle.

  fitness function' 2 f which assign a score f (S) ∈ [-1, 1] to each sequence S. This fitness function is taken to be very simple for test cases, but we ultimately want to use complicated function presenting several competing optima (see Figure7.3). While the interpretation of the fitness function is widely accepted in Darwinian evolution, its meaning in a social context is less clear and will be discussed below. This function is supposed to be fixed and identical for all the agents.

Figure 7 . 3 :

 73 Figure 7.3: Left. Complex agents. The agents of our model are completely characterized by a sequence of bits that they can exchange with their neighbors. Right. Fitness landscape. Example of a bumpy fitness landscape, here with two input variables. The landscape shows several local maxima corresponding to several optimum sets of input parameters.

  Figure 8.1: Limit case ω → ∞: without leakage, convergence towards stable polarized states. Left: Evolution of the opinions of a sample of 100 out of the N = 1000 agents. Right: Evolution of the mean opinion of detected opinion clusters with more than 10 agents. The width of the error bars (in green) is proportional to the number of agents within the opinion clusters. Other parameters are fixed to K = 10, d = 0.04 and ν = 0. Fig 8.1 displays the temporal evolution of the mean opinion inside the opinion clusters containing more than 10 agents and the temporal evolution of the opinion of a sample of agents. Opinion clusters are detected independently at each normalized iteration (corresponding to N iterations). We also keep track of the number of agents within each opinion cluster. On the left panel of Fig 8.1, we observe that, starting from random opinion, local convergence processes take place and lead to several opinion clusters. On

Figure 8 . 2 :

 82 Figure 8.2: Introducing leakage yield slow convergence towards consensus. Left: Evolution of the opinions of a sample of 100 out of the N = 1000 agents. Right: Evolution of the mean opinion of detected opinion clusters with more than 10 agents. The width of the error bars (in green) is proportional to the number of agents within the opinion clusters. Other parameters are fixed to K = 10, d = 0.04, ω = 5 and ν = 0.

Figure 8 . 3 :

 83 Figure 8.3: Time for cluster -cluster coalescence as a function of their initial opinion difference. Data is well fitted by t coal = 0.136 exp(O * 116.03), with 116 ω/d = 125. Estimating the time needed for coalescence into a single cluster (assuming a distance ∆O = 0.5 for the two last clusters) is 10 26 . Parameter values : K = 10, d = 0.04, ω = 5 and ν = 0.

  Figure 8.4: Opinion noise combined to leakage yield slightly fluctuating polarized states. Left: Evolution of the opinions of a sample of 100 out of the N = 1000 agents. Right: Evolution of the mean opinion of detected opinion clusters with more than 10 agents. The width of the error bars (in green) is proportional to the number of agents within the opinion clusters. Other parameters are fixed to K = 10, d = 0.04, ω = 5 and ν = 10 -4 .

Figure 8 . 5 :

 85 Figure 8.5: Generation effects produce rich collective behaviors. Left: Evolution of the opinions of a sample of 50 out of the N = 500 agents. Right: Evolution of the mean opinion of detected opinion clusters with more than 10 agents. The width of the error bars (in green) is proportional to the number of agents within the opinion clusters. Other parameters are fixed to K = 10, d = 0.04, ω = 5 and ν = 10 -5 .

  that context, we showed that a potential function exists for a much broader range of utility function. We use this potential function to analyze the outcome of the model for three families of utility functions, namely linear utility functions, Schelling's original stair-like utility functions and asymmetrically peaked utility functions. In all cases, the potential function allowed us to derive the segregation level and the corresponding cost in the collective utility.In chapter 3, we used a simplified version of our analytical model -with only one type of agent -to come back to the question of the level of coordination necessary to reduce unwanted segregation patterns. By introducing a 'cooperativity' parameter α allowing to tune continuously between strictly individual-driven and strictly collectivedriven dynamics, we characterized a qualitative transition from a segregated phase of low collective utility towards a mixed phase of high collective utility. This study was performed from a physicist's point of view, in which we identify the generalized potential function -encompassing both individual and collective dynamics -as an effective free energy.

  already used it in a typical model of urban economics dealing with land use and transport. In particular, they extended our comparison of the potential function with an effective free energy to a comparison with an effective chemical potential. A second interesting extension of the work presented in chapter 4 would be a deeper analysis of the individual / collective transition. Going back to simulations and continuous neighborhood, this transition could be analyzed in a more standard physics framework. What is the nature of this transition, what are the critical exponents characterizing it, how does it relate to the usual Ising transition? All these questions are certainly worth to investigate.

Figure B. 1 :

 1 Figure B.1: Phase separation. The system of density ρ 0 splits into two phases of densities ρ 1 and ρ 2 if it increases its potential. The standard double tangent construction determines the densities of the two phases at equilibrium.

  It is straightforward to verify that the function f (ρ) reads for ρ ≤ 1/2f (ρ) = -T ρ ln ρ + (1 -ρ) ln(1 -ρ) + (1 + α)ρ 2 (B.6)and similarly, for ρ > 1/2f (ρ) = -T ρ ln ρ+(1-ρ) ln(1-ρ) -(1+α)(1-m)ρ 2 +(2-m)ρ-(1-α)(2-m)/4 (B.7)B.2.1 Limiting case T goes to 0

  Figure B.2: Graphic representation of the f function for m = 0.7, T = 0 and α = 0, 0.3, 0.5, 0.7, 1. The dash lines represent the part of the curves merging with their concave hulls. The solid line hence corresponds to the range of mean densities ρ 0 for which there is phase separation.

  α ≥ α c (m), ρ 2 sticks to the value ρ 2 = 1/2. Similarly, for α ≤ α t (m), one has ρ 2 = 1. These results are illustrated on Fig B.3. The dependency of the outcome with the mean density of agents is quite simple. For ρ 0 < ρ 2 (α, m), two kinds of blocks coexist in the stationary states: empty blocks and blocks of density ρ 2 . The collective utility can then be written asU * (x) = u(ρ 2 ) = 2 -m -1 -α 1 + α (2 -m)(1 -m) (B.11)This expression clearly increases with α, as expected.In the opposite case for which ρ 0 ≥ ρ 2 (α, m), the density of the blocks in the stationary states is homogeneous and the collective utility is thenU * (x) = u(ρ 0 ) = 2 -m -2(1 -m)ρ 0 (B.12) Notice furthermore that the independence of collective utility with the tax parameter α observed on Fig 3 of the article for α > α c and α < α t correspond to domains for B.3.3 With a peaked utility function Expression of the f function Let us consider for both populations the asymmetrically peaked utility function defined for m < 1 as:u(ρ) = 2ρ if ρ ≤ 0.5 u(ρ) = m + 2(1 -m)(1 -ρ) if ρ > 0.5For ρ R ≤ 0.5 and ρ G ≤ 0.5, the f function is:f (r, g) = -T r ln r -g ln g -(1 -r -g) ln(1 -r -g) + (1 + α)(r 2 + g 2 ) ∂f ∂r (r, g) = -T ln r -ln(1 -r -g) + 2(1 + α)r ∂ 2 f ∂r 2 (r, g) = -T /r -T /(1 -r) + 2(1 + α)(Partial derivatives relative to g are obtained by replacing g ↔ r)For ρ R > 0.5 and ρ G ≤ 0.5:f (r, g) = -T r ln r + g ln g + (1 -r -g) ln(1 -r -g) -(1 + α)(1 -m)r 2 + (2 -m)r -(1 -α)(2 -m)/4 + (1 + α)g 2 ∂f ∂r (r, g) = -T ln r -ln(1 -r -g) -2(1 + α)(1 -m)r -(2 -m) ∂ 2 f ∂r 2(r, g) = -T /r -T /(1 -r -g) -2(1 + α)(1 -m) ∂f ∂g (r, g) = -T ln g -ln(1 -r -g) + 2(1 + α)r ∂ 2 f ∂r 2 (r, g) = -T /g -T /(1 -r -g) + 2(1 + α)

Figure B. 8 :

 8 Figure B.8: Domains of different phases for different global densities in case 2

  . The sequence of the human genome. Science, 291(5507), 1304. Watson, JD, & Crick, FHC. 1953. Molecular structure of nucleic acids: a structure for deoxyribose nucleic acid. Nature, 171(4356), 709-758. Whitesides, George M., & Grzybowski, Bartosz. 2002. Self-Assembly at All Scales. Science, 295(5564), 2418-2421. Witten, T.A., & Sander, L.M. 1981. Diffusion-limited aggregation, a Kinetic Critical Phenomenon. Physical Review Letters, 47(19), 1400-1403.

Figure D. 2 :

 2 Figure D.2: 1985Figure D.2: -1994's subfield community network. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 100 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis.

Figure D. 4 :

 4 Figure D.4: 1990Figure D.4: -1999's subfield community network. The surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . For the sake of clarity, communities with less than 100 articles and links with a mean weight ω < 2.10 -5 are not displayed. Labels are based on a frequency analysis.

Figure D. 6 :

 6 Figure D.6: Community filiation diagrams. A. Complex Networks B. Self-Organized Criticality C. Computational Systems Biology D. Pattern Formation & Self-OrganisationThe surface of a community I is proportional to its number of articles N I and the width of the link between two communities I and J is proportional to the mean bibliographic coupling ω IJ = i∈I, j∈J ω ij /N I N J . Colors corresponds to different chronological periods (from top to bottom: red, orange, yellow and blue for respectfully the2000-2009, 1995-2004, 1990-1999 and 1985-1994 decades). The procedure leading to these diagrams is explained in the main text. The relative position of the communities are here meaningless.

  Reciprocally, no potential function exists for any other form of utility functions.

The first part of this claim -which is that a potential function exists if the utility functions are chosen as in Eqs. 2.40 -is the main subject of

Zhang (2004a)

. The second part of this claim -which is that no potential function exists for any other choice of utility functions (in the context of the model presented in this chapter and with continuous neighborhoods) has to our knowledge never been proved elsewhere.

13

A sketch of the proof of Proposition 2 is given in A.5. The main reason why no potential function exists in general is that when a moving agent generates externalities on his (past and new) neighbors, these externalities depend on the type of his neighbors' own neighbors.

  . However, these are limited to specific utility functions. More recently, physicists have tried to use a statistical physics approach to understand the segregation transition[START_REF] Dall'asta | Statistical physics of the Schelling model of segregation[END_REF][START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF][START_REF] Gauvin | Phase diagram of a Schelling segregation model[END_REF]. The idea seems promising, since statistical physics has successfully bridged the micro-macro gap for physical systems governed by collective dynamics. However, progress was slow by lack of an appropriate framework allowing for

individual dynamics

[START_REF] Dall'asta | Statistical physics of the Schelling model of segregation[END_REF]

. In this chapter, we introduce a rigorous generalization of the physicist's free energy, which includes individual dynamics. By introducing a "link" state function 1 which is maximized in the stationary state, we pave the way to analytical treatments of a much wider class of systems, where dynamics is governed by individual strategies. As an example, we provide a quantitative solution to Schelling's segregation model for very general utility functions.

Table 3 .

 3 1: Characteristics of the segregated equilibrium. The table displays the density ρ s in the non-empty blocks, the normalized collective utility U * and the normalized link L * of the stationary configurations obtained for α = 0. It is straightforward to check that U * (m) ≤ 1 and L * (m) ≥ 1/2 for m ≤ 1.

  congestion model. In this model, a number N of identical commuters travel every morning from home to work. All agents travel on the same road and wish to arrive at CHAPTER 4. EFFECTIVE FREE ENERGY FOR INDIVIDUAL DYNAMICS 103 time t * . Since congestion is a collective phenomenon that no single agent can master to arrive at her preferred arrival time t * , agents have to choose a less optimal arrival time t ∈ Z (time is supposed to be discrete) in order to minimize the private trip cost, c(t), which includes two parts. The first part is the travel time cost αT T (t) where α is the unit cost of travel time and T T (t) is the travel time. The second part is the schedule delay cost, which is β(t * -t) if one arrives early and ν(t -t

* ) if one arrives late, β and ν being unit costs of schedule delay. To make analytical calculations possible, the travel time is supposed to depend on the number n t of commuters arriving at time t through the function T T (t) = (n t /H) γ where H and γ are fixed parameters. The parameter H can be interpreted as a standard road capacity (the linearity between H and N can thus

  t * (4.11) under the constraint h t ρ t = 1. Since the sum t f ∞,T (t, ρ t ) is maximized by the stationary configuration, the stationary values of {ρ t } verify (for any t such that ρ t = 0)

	the relation:	∂f ∞,T ∂ρ	(t, ρ t ) =	∂f ∞,T ∂ρ	(t * , ρ t * )	(4.12)

Table 5 .

 5 2: 2000-2008 subfields' sizes N and inner coherences < ω in > -1

  CHAPTER 5. COMPLEX SYSTEMS SCIENCE: DREAMS AND REALITY 117 Table5.3: The 20 most networking references in the 2000-2008 decade. The references followed by a star correspond to books or papers which appeared in the database under several forms -essentially different publication years for the books -for which the networking power N (r) have been summed. The complete references of these papers are given in Appendix B.

	Reference	Topic	N (r) (%)
	Press et al. (1992)*	Numerical recipes (book)	1.250
	Shannon (1948)*	Information theory	0.607
	Metropolis et al. (1953)	Monte Carlo integration	0.509
	Nicolis et al. (1977)*	Self organization (book)	0.420
	Kauffman (1993)*	Self organization (book)	0.309
	Hebb (1949)	Neuropsychology and behavior (book)	0.297
	Alberts et al. (1994)	Molecular and cellular biology (book)	0.288
	Abramowitz et al. (1968)* Handbook of mathematical functions	0.269
	Feller (1958)*	Introduction to probability theory (book)	0.268
	Watson & Crick (1953)	Structure of DNA	0.250
	Lakowicz (1999)	Fluorescence spectroscopy	0.249
	Turing (1952)	Morphogenesis	0.237
	Witten et al. (1981)

  Table 5.2.

	Subfield	Fields	T (%) T /T exp
	TDA	Biology/Neural Networks	46.355	20.51
	CSB	Biology/Dynamical Systems	49.704	8.87
	CSB	Biology/SOC	49.255	8.79
	ProteinStruct Biology/Material Sciences	47.442	8.32
	CSB	Biology/CN	42.931	7.66
	TDA	CN/Neural Networks	16.543	7.32
	Hemodyn	Neurosciences/FluidMech	54.552	7.22
	NeuralSynchr Neurosciences/Dynamical Systems 59.788	5.20
	Hemodyn	Biology/FluidMech	39.113	5.18
	CytoskSO	Biology/SOC	9.561	4.71
	CytoskSO	Biology/Dynamical Systems	9.522	4.69
	Calib	Material Sciences/Neural Networks	8.717	4.51
	CellularNN	CN/Neural Networks	9.605	4.30
	Transcrip	Biology/CN	25.806	4.05

Table 6

 6

	Prop of articles (%)

.1: Most frequent ENS de Lyon's Subjects.

Table 6 .

 6 2: Community "ID Card". The community Hansen JP/Molec-Dynamics contains N = 547 articles. Its average internal link weight is < ω in > 1/223 (roughly, two random articles within the community share 1 reference over 223).

	Institution

  Our model is based on the Deffuant Model[START_REF] Deffuant | Mixing beliefs among interacting agents[END_REF] with an adaptive network similar to what can be found in[START_REF] Kozma | Consensus formation on adaptive networks[END_REF]. The model considers

	CHAPTER 8. LASTING STRUCTURES FROM NON LASTING ENTITIES	159
	ing new members, contract and disappear by losing members, merge with other clusters
	. . . In other words, we obtain a dynamically stable state which is more appealing for
	sociologists and might stimulate their conceptualization of structure emergence.
	8.2 An opinion model with adaptive network
	8.2.1 Model
	p conv (i, j) =	1 1 + exp (ω (∆o -d)/d)	(8.1)
	where ∆o = |o
		Then, we show how robust polarized states
	can be obtained by introducing random fluctuations in the agents' opinions. Ironically,
	this polarized state is now too robust to please sociologists. We therefore end this chap-
	ter by showing our work in progress on a last model which takes into account the "age"
	of the agents and leads to interesting "generation" phenomena and constantly changing
	polarized states. In this last model, opinion clusters can continuously grow by recruit-

a population of N agents (i = 1, 2, ...N ) which are characterized by a continuous opinion at time t o(t) ∈ [0, 1]. The initial interaction network is taken as an Erdös-Rényi network of average degree K, ie agents are initially linked to K neighbors on average and opinions are also chosen at random. Following the spirit of

[START_REF] Kozma | Consensus formation on adaptive networks[END_REF]

's model, we choose to introduce in our model a non-strict update rule ensuring a non-zero probability for neighbours of non-close opinions to communicate. Specifically, we define the probability of convergence between two agents i and j: j (t) -o i (t)| is difference of opinion between the agents, d is the usual Deffuant threshold, and ω is a "leakage" parameter. For ω 1, our update rule is very similar to Deffuant's. For ω 1, p conv is finite and does not depend on ∆o hence all pairs of neighbors interact in the same way. Convergence means that the agents' opinions are updated according to

Table C .

 C 2: Community "ID Card". The community CN contains N = 3684 articles. Its average internal link weight is < ω in > 1/22. aa

	Keyword	prop	σ
	complex networks	0.53 260.804
	dynamics	0.17	48.214
	small-world networks	0.13 129.264
	model	0.11	23
	internet	0.1	96.383
	networks	0.08	41.746
	evolution	0.08	30.27
	scale-free networks	0.07	98.245
	systems	0.07	13.515
	organization	0.07	44.6
	synchronization	0.06	36.731
	topology	0.05	66.625
	metabolic networks	0.05	78.053
	web	0.04	70.114
	stability	0.04	14.258
	graphs	0.03	55.364
	random graphs	0.03	66.888
	small-world	0.03	67.309
	complex network	0.03	62.893
	community structure	0.03	37.757
	saccharomyces-cerevisiae	0.02	9.179
	social networks	0.02	56.672
	emergence	0.02	30.031
	percolation	0.02	38.158
	robustness	0.02	24.817
	Journal	prop	σ	Refs (Journals)	Times used
	PHYS REV E	0.331	119.35	PHYS REV LETT
	PHYSICA A	0.217	91.76	NATURE
	LECT NOTE COMPUT SCI	0.082	15.05	PHYS REV E 2
	PHYS REV LETT	0.067	37.27	SCIENCE
	EUR PHYS J B	0.065	64.21	P NATL ACAD SCI USA
	PROC NAT ACAD SCI USA	0.041	16.63	PHYSICA A
	INT J MOD PHYS C	0.035	39.6	REV MOD PHYS
	CHIN PHYS LETT	0.031	40.65	PHYS REV E
	CHAOS	0.029	28.95	EUR PHYS J B
	IEEE INT SYMP CIRC SYST PROC 0.024	17.26	SIAM REV
	NEW J PHYS	0.024	39.3	EUROPHYS LETT
	EUROPHYS LETT	0.024	27.81	J THEOR BIOL
	PHYS LETT A	0.024	21.77	PHYS REV E 1
	INT J BIFURCATION CHAOS	0.023	17.29	ADV PHYS
	J STAT MECH-THEORY EXP	0.023	38.98	NUCLEIC ACIDS RES

Table C .

 C 3: Community "ID Card". The community SOC contains N = 4447 articles. Its average internal link weight is < ω in > 1/199 aa Table C.4: Community "ID Card". The community ComputSystBio contains N = 1799 articles. Its average internal link weight is < ω in > 1/324 aa Table C.5: Community "ID Card". The community Transcriptomics Data Analysis (TDA) contains N = 628 articles. Its average internal link weight is < ω in > 1/43 aa

	Keyword Keyword Keyword		prop	prop σ prop	σ σ
	self-organized criticality gene-expression patterns	0.276 180.616 0.105 29.811 0.273 65.409
	model escherichia-coli self-organizing maps		0.114 0.09 31.696 0.216 99.058 26.379
	dynamics expression gene-expression		0.103 0.087 13.642 0.159 28.356 26.429
	evolution systems identification		0.066	0.075 7.592 0.116 17.682 29.45
	systems model microarray		0.066	0.060 6.579 0.108 79.859 8.954
	models activation classification		0.039 0.063 15.884 0.100 28.106 14.474
	fluctuations protein cancer		0.037 0.061 14.106 0.095 28.214 36.555
	turbulence complex gene expression		0.057	0.035 7.46 0.082 36.526 21.968
	self-organization phosphorylation saccharomyces-cerevisiae	0.034 0.056 23.345 0.068 13.212 4.983
	behavior signal-transduction cell-cycle		0.034 0.055 33.656 0.062 21.492 8.762
	avalanches networks prediction		0.034 0.052 17.788 0.060 16.642 64.80
	earthquakes systems biology expression		0.033 0.049 62.627 0.060	58.09 4.145
	noise cells gene-expression data		0.031 0.049 11.644 0.058 95.821 24.895
	transport transcription oligonucleotide arrays		0.046	0.029 18.39 0.058 85.248 15.886
	criticality dynamics discovery		0.043	0.026 3.358 0.054 47.311 47.168
	1/f noise rhythms microarray data		0.025 0.043 65.654 0.052 68.108 48.331
	deformation simulation cluster-analysis		0.024 0.04 10.691 0.051	28.72 67.97
	complexity binding clustering		0.039	0.024 9.445 0.051 29.864 3.959
	growth drosophila DNA microarray		0.021 0.035 20.722 0.049 66.328 0.808
	patterns flow robustness mechanism microarrays cDNA microarray Decade	N	0.033 0.032 Q f	0.021 0.020 25.4 9.972 0.046 48.629 6.377 9.583 0.044 60.323 C f (N f )	Q sf	C sf (N sf )	T hr
	field simulation system kinetics saccharomyces-cerevisiae receptor hybridation cDNA microarrays 1985-1994 20286 0.7421 12 (19814) 0.020 18.164 0.019 3.255 0.019 0.716 0.031 13.075 0.031 7.647 0.03 11.805 0.044 31.714 0.043 0.6822 43 (17262) 76.89 gene-expression patterns 0.039 73.138 1990-1999 62040 0.75 12 (61460) 0.7034 67 (59739)	100 100
	phase-transitions in-vivo DNA microarrays 1995-2004 109458 0.7592 14 (108739) 0.7586 82 (106753) 100 0.018 18.573 0.029 6.412 0.039 59.58
	Journal PHYS REV E Journal PROC NAT ACAD SCI USA 0.036 prop Journal BIOINFORMATICS 2000-2009 141098 0.7128 11 (139749) 0.6375 79 (135834) 300 prop σ 0.078 38.48 σ 13.86 Refs (Journals) J BIOL CHEM prop σ 0.057 39.49	Times used 4986
	PHYSICA A BIOPHYS J BMC BIOINFORMATICS	0.028	0.042 28.81 0.044	22.7 P NATL ACAD SCI USA 34.68	4928
	PHYS REV LETT J BIOL CHEM LECT NOTE COMPUT SCI	0.025	0.033 6.27 0.039	25.88 SCIENCE 2.12		4663
	PHYS PLASMAS J THEOR BIOL PHYSIOL GENOMICS	0.025	0.024 22.29 0.023	44.37 NATURE 34.87		4556
	PHYS REV B NATURE PROC NAT ACAD SCI USA	0.012	0.018 8.16 0.02	13.53 CELL 3.75			3051
	J GEOPHYS RES-SOLID EARTH LECT NOTE COMPUT SCI 0.012 IEEE IJCNN	0.016 -3.58 0.019	38.8 EMBO J 5.98		1485
	AIP CONF PROC PLOS COMPUT BIOL GENOME RES	0.011	0.013 18.17 0.011	9.14 J THEOR BIOL 13.64		1415
	TECTONOPHYSICS GENE DEVELOP J BIOMED INFORM	0.01	0.013 9.2 0.011	39.82 BIOPHYS J 23.57		1371
	PLASMA PHYS CONTROL FUSION 0.011 BIOINFORMATICS 0.01 10.42 J COMPUT BIOLOGY 0.009	33.05 MOL CELL BIOL 15.55	1209
	GEOPHYS RES LETT CURR BIOL P SOC PHOTO-OPT INSTRUM ENG 0.009 0.011 0.009 8.44	22.95 NEURON -2.07		996

Table D . 2 :

 D2 Quantitative characterization of the obtained community networks.

For a complete and detailed discussion on segregation indices, see for example[START_REF] Massey | Dimensions of Residential Segregation[END_REF],Reardon & Firebaugh (2004),[START_REF] Reardon | Measures of spatial segregation[END_REF].

A more obvious choice of chronological reference could be the number t of simple iterations (i.e. the number of attempted moves). Neither choice accounts for the proportion of accepted moves (whose cumulated value is τ /t), whose instantaneous value depends on the values of the various parameters and on the state of the system. Ideally, it may be interesting to follow this rate of "moving iterations" with the dynamic evolution of the city.

However, since some of the potentially new neighbors share almost the same neighborhood than voting co-proprietors, there are spatial correlations between the H potentially new neighbors. Hence the LC mechanism takes effectively into account more than h/2H of the affected agents.

Instead of assuming, as Schelling did, that the agents move to the nearest satisfactory position (the idea being that the cost of moving increases with distance), we suppose here that the distance between the current and envisaged locations of an agent does not intervene in his decision whether to move or not.

Games can be either ordinal or cardinal potential games. In cardinal games, the difference in individual payoffs for each player from individually choosing one's strategy ceteris paribus has to have the same value as the corresponding difference in value for the potential function. In ordinal games, only the signs of the differences have to be the same.

In the case of finite values of the noise level (T > 0), it can be demonstrated using standard tools of statistical physics that the states which are the more probable to appear are those which maximize F (x) + T S(x) where S(x) is an entropy-like global function taking into account the number of ways of locating Rq red agents and Gq green agents in each block q of the city(Grauwin et al., 2009a).

Refer to[START_REF] Grauwin | Dynamic models of residential segregation: brief review, analytical resolution and study of the introduction of coordination[END_REF] for the study of other utility functions.

Zhang (2004a)'s utility function corresponds to b = d = -1 and a ≥ -1, the utility also including a fixed income term which makes it positive. In Zhang (2004a)'s framework, the impact of unlike neighbors is not due to preferences, but to the impact of density on housing prices.

Note that this result is similar to the one obtained in the continuous neighborhood case as will be seen in section 2.5.1. See also[START_REF] Grauwin | Dynamic models of residential segregation: brief review, analytical resolution and study of the introduction of coordination[END_REF].

The limit value is not strictly equal to 1 because of the precise definition of our model: the argument of the utility function is the number of neighbors, which does not include the agent himself. In the limit H 1, m * converges toward 1.

And even though a red agent goes from time to time into the green area by mistake, he will have a strong incentive to return to the red area because of the asymmetry in the utility function, and he will do so very likely before a second red agent joins him in the green area.

Note however that the inexistence of a potential function does not preclude the convergence of the game to a stationary state.

Zhang (2004b) proposes a continuous neighborhood model without vacant cases which allows to derive a potential function for utility functions defined by two linear pieces.

This result illustrates a theorem presented in[START_REF] Ui | A Shapley value representation of potential games[END_REF], which extends the notion of Shapley value to non cooperative games such as ours.

For development on the level of the tax α necessary or sufficient to break undesired stationary configurations, seeGrauwin et al. (2009a).

Word of caution: in this chapter and in the following, we use the notation L (as link) to designate the potential function previously called F. In these two more 'physics-centered' chapters, we keep the notation F to designate an analogue the notion of free energy introduced in physics.

If the state function L exists, the relation ∆ui = ∆L requires only that it be defined up to a constant.

In genetic algorithms, fitness functions are used to determine the degree of optimality of a given solution (such as a virtual chromosome). The best solutions are then mixed to produce a new generation of more adapted solutions.

Beware of the restrictions imposed on the values of (RB, GB) and (RC , GC ) due to the overlapping of the neighborhoods of cells B and C.

Remerciements

Appendix A

Annex to Chapter 2 A.1 Proof of Proposition 1

In this section, we place ourselves in a bounded neighborhood description.

Let us first prove the first part of 1, that is that any aggregate function F = q∈Q F (R q , G q ) is a potential function that corresponds to (at least) one pair of utility functions (u R , u G ) of U.

Suppose that F = q∈Q F (R q , G q ) is a potential function of the game, where the intermediate function F is known. Let us assume that an agent is moving from a block 1, characterized by the numbers (R 1 , G 1 ) ∈ E H+1 of red and green agents who live in it, to a block 2 characterized similarly by the numbers (R 2 , G 2 ) ∈ E H of red and green agents living in it (since there must be at least one vacant location in block 2 for an agent to move in it, we necessarily have R 2 + G 2 < H + 1). By definition, the utility variation of a moving agent must be equal to the variation of F it induces. Hence :

-to cover the cases when the moving agent is a red one: for all (R 1 , G 1 )

-to cover the cases when the moving agent is a green one: for all (R 1 , G 1 )

Taking R 2 = G 2 = 0 in equations A.1 and A.2, one finds that the utility functions u R and u G verify for all (R, G) ∈ E H :

These relations define (up to a constant u(0, 0)) the utility functions the agents necessarily have if F = q∈Q F (R q , G q ) is a potential function of the game. It still remains to prove that this pair of utility functions belongs to the set U. According to relations A.3 and A.4, one has for all (R, G) ∈ E H :

Hence relation 2.15 holds, which means by definition that the pairs of utility functions (u R , u G ) defined by relations A.3 and A.4 belongs to U. Notice that in our demonstration no particular constraint has to be assumed on the form of function F . As a consequence, any aggregate function F = q∈Q F (R q , G q ) ∈ F is a potential function of the game as soon as the pair of agents' utility functions is chosen so that relations A.3 and A.4 hold.

Let us now prove the second part of proposition 1, which is that to any pair of utility functions (u R , u G ) of U corresponds a potential function of the form F = q∈Q F (R q , G q ). Let (u R , u G ) ∈ U be a pair of utility functions verifying condition 2.15. Suppose that F (0, 0), F (0, 1) and F (1, 0) are given and let us define recursively the function F on E H+1 by the following equations, verified for all (R, G) ∈ E H :

The most important thing to notice is that these two relations are consistent with each other thanks to condition 2.15 that links the two utility functions u R and u G . By summing Eq. A.5 on R and then Eq.A.6 on G, one finds the following expression for function F :

or conversely by summing Eq. A.6 on G then Eq.A.5 on R,

Hence, since F = q∈Q F (R q , G q ) one can obtain, after rearranging the different terms, a symmetric expression of the potential: F = |Q|F (0, 0) + N R F (1, 0) -F (0, 0) -u R (0, 0) + N G F (0, 1) -F (0, 0) -u G (0, 0)

u G (0, g -1) + u G (R, g -1) (A.9)

Since the potential can be chosen up to a constant, it is clear from the previous expression that the choice of F (0, 0), F (0, 1), F (1, 0), u R (0, 0) and u G (0, 0) does not really matter. This justifies our choice to put them to zero to simplify the generic expressions of the potential given in Eq. 2.17 and 2.18.

According to Eq A.7, F (R, G) can be interpreted as the sum of the settling utility of R red and G green agents, these agent settling one by one in an initially empty block, the red agents first and then the green ones. The same goes for Eq. A.8 while the green agents settle first, the red coming next. In fact, relation 2.15 ensures that the sum does not depend on the exact order with which the agents settle (see section 2.3.3 for more precisions). Hence F (R q , G q ) can be written as the mean of the settling utilities of the agents over all possible orders of settlement:

where α(R q , G q ) = (R q + G q )! is the number of settling orders of the R q + G q agent living in block q, α R (r, g) is the number of such orders in which a red agent settle after r -1 red and g green, in which case his utility is u R (r -1, g), and similarly α G (r, g) is the number of such orders in which a green agent settles after r red and g -1 green, in which case the utility of this agent is u R (r -1, g).

α R (r, g) is the product of:

• R q , the number of ways of choosing the r th red settling agent,

• Rq-1 r-1 Gq g , the number of ways of sharing out the R q -1 + G q other agentseither before or after this agent,

• (r + g -1)!, the number of ways of ordering the agents who settle before and

the number of ways of ordering the agents who settle after. α G (r, g) can be similarly computed. We thus end up with a new formula for F (R q , G q ):

(A.10)

A.2 Relation between the potential function F and the collective utility U

Let us suppose that (u R , u G ) ∈ U, and that the potential function of the system can be expressed as a linear function of the collective utility, ie F({R q , G q }) = λU ({R q , G q }) + µ. Since the potential function can be defined up to constant, we can take µ = 0.

Writing the utility functions under the form

introduced in Eq. 2.19 and 2.20, the relation of proportionality between the potential and the collective utility can be written as

Since this relation must hold for all {R q , G q }, it follows that that for all (R, G) ∈ E H , the following holds:

Taking successively G = 0 and R = 0 in that last equation provides three independent relations dissociating the three functions ξ R , ξ G and ξ:

) and b = ξ(0, 0). Starting from equations A.12 to A.14, APPENDIX A. ANNEX TO CHAPTER 2 190 it is straightforward to prove recursively that

Hence the agents' utility functions corresponds exactly to those introduced in Eq.

2.26:

The individual utilities are thus necessarily linear in the numbers of similar and dissimilar neighbors in case the potential function F is proportional to the collective utility U

A.3 Calculation of a potential function in Schelling case

Suppose that the agents compute their utility with Schelling utility function (which is equal to 1 if their fraction of similar neighbors is superior or equal to 0.5, and equal to 0 otherwise). This utility function can be expressed in terms of the number of red and green neighbors as follows:

where Θ is the Heaviside function defined by: Θ(x) = 0 if x < 0 and Θ(x) = 1 if x ≥ 0. Notice that in this example (and in this example only) the convention u(0, 0) + 0 used in proposition 1 is not respected. The form we choose to write Schelling utility function imposes u R (0, 0) = u G (0, 0) = 1. It is easy to figure out that this particular pair of utility functions respect condition 2.15, and is therefore in the set U. Indeed,

To compute a corresponding potential function, one can refer to the general form of Eq. A.9 (since we do not use the convention u(0, 0) = 0 in this particular example)

which can be written here as:

A.4 Potential and collective utility in the case of the asymmetrically peaked utility

Proof of equation 2.37

We have to derive the expression F (S) = S-1 s=0 ξ ap (s), where

In the same way,

A.5 Proof of Proposition 2

In this section, we place ourselves in a continuous neighborhood description.

Constraint on the form of the utility functions

Suppose that there exists a potential function F : X → R, and let u R : cells B and C):

Summing all these relations yields

If the values of (R B , G B ) and (R C , G C ) were independent, it would be straightforward to prove that for all values of (R,

We leave to the sagacity of the reader to verify that the restrictions on the values of (R B , G B ) and (R C , G C ) due to the overlapping of the neighborhoods of cells B and C

The same kind of reasoning can similarly prove that

Once again, one can check that while the values of (R B , G B ) and (R C , G C ) are not independent, the intuitive results holds, which is

To summarize, the existence of the potential function imposes the existence of three real constants (a, b, d) such that the utility functions take the bilinear form:

Reciprocal proof

Suppose that the utility of red and green agents are given by Eqs. A.23. Our goal is here to demonstrate that these utility function being given, there exist a potential function of the system.

Suppose that an agent moves from a neighborhood composed of R red and G green agents to a neighborhood composed of R red and G green agents. If the moving agent is red, then the variation of his utility can be written as

while the variation of the collective utility is:

which is the variation of the moving agent utility + G b -Gb which is the sum of the variation of the other green agents + R a -Ra which is the sum of the variation of the other red agents

Similarly, if the moving agent is green, the variation of his utility can be written as

while the variation of the collective utility is: Focusing on the large H case, the problem gets back to finding the set {ρ q } which maximize the potential F (x) = H q f (ρ q ) with the constraint q ρ q fixed. We are interested to know whether the stationary state is statistically homogeneous or inhomogeneous. Following standard physics textbooks methods, the homogeneous state at density ρ 0 is unstable against a phase separation if there exists two densities ρ 1 and ρ 2 such that

The parameter γ (0 < γ < 1) corresponds to the fraction of blocks that would have a density ρ 1 in the diphasic state, while a fraction 1 -γ would have a density ρ 2 . This condition simply means that the value of the sum q f (ρ q ) is higher for the diphasic state than for the homogeneous state, so that the diphasic state has a much larger probability to occur. Geometrically, the inequality (B.1) corresponds to requiring that f (ρ) is a non-concave function of ρ. The values of ρ 1 and ρ 2 are obtained by maximizing

) over all possible values of ρ 1 and ρ 2 , with γ determined by the

Further, the equilibrium coexistence points to a given temperature can be determined

B.2.2 Finite temperatures

Finally, we turn to the analysis of the model for finite values of T and show that the behavior of the model remains qualitatively similar to that obtained previously in the T → 0 limit. The high T case is the simplest to analyze. For 2T /(1

where it is regular. One can moreover verify that at the singular point

, there is a single phase of density ρ 0 .

In the opposite case 0 < T /(1 + α) < 1/2, the analysis is somewhat similar to the zero T limit. The function f is convex on the interval

and concave on the complementary interval. As f (ρ) has an infinite slope in ρ = 0 and ρ = 1, the densities ρ 1 and ρ 2 satisfy 0 < ρ 1 < 1/2 and 1/2 ≤ ρ 2 < 1. Assuming that For lower values of the tax, phase separation is a disadvantage.

ρ 2 = 1/2, the density ρ 1 is given by the implicit expression

Then the assumption ρ 2 = 1/2 is consistent as long as

), which can be rewritten as

where the function ϕ is defined by

As T is increased, all the diagram is affected by the entropic term. Compared to the T = 0 case, the main change at low T is the apparition of a second homogeneous phase for ρ 0 < 1/2. But whereas for ρ 0 > 1/2 homogeneity corresponds to the best interest of the agents, for ρ 0 < 1/2, collective utility is not maximized in an homogeneous city. This homogeneous domain is here purely induced by noise. Note that an increase in α tends to reduce this domain while it tends to increase the homogeneous domain for ρ 0 > 1/2.

Notations

In this section, describing a city inhabited by two types of agents (that we refer to as red and green agents), we will note:

Q the number of blocks the city is divided in, each block being composed of H cells;

x a configuration of the city, corresponding to the knowledge of the state (empty, red or green) of each cell;

n qr (x) and n qg (x) the numbers of red and green agents living in the block q; u(n qr /H) (resp u(n qg /H)) the utility of a red (resp green) agent living in block q, with u(0) = 0 by convention;

N 0 = q n q ≤ QH the total number of agents;

N R = q n qr the total number of red agents (idem for the green ones);

) the value of the "linking function" in configuration x. 0 ≤ α ≤ 1 the tax parameter.

Dynamic rule

At each iteration, one picks at random an agent and a vacant cell. The agent moves in this empty cell with a probability

where ∆u is the variation of utility which the chosen agent can achieve by moving, ∆U is the variation of global utility which would result from this same move and 0 ≤ α ≤ 1 is an "altruism" parameter (for α = 0 the move only depends on the egoistic interest of the agent, for α = 1 it only depends on the collective interest).

A potential function

Let us define two states x and y as immediately communicating states (ICS) if we can switch from state x to state y by moving one single agent. Whatever the form of the APPENDIX B. ANNEX TO CHAPTER 3 206 utility function u, one has for every move ∆u = ∆L. The transition probability from a configuration x to a configuration y in one iteration can thus be written:

= γ xy e ((1-α)L(y)+αU (y))/T e ((1-α)L(x)+αU (x))/T + e ((1-α)L(y)+αU (y))/T where γ xy takes into account the probability to pick the right agent and the right vacant cell that allow to pass from x to y: Since the function

is the unique normalized function that verifies for all x and y the detailed balance: There is

! ways of ordering n R undifferentiated red agents and n G undifferentiated green agents in H cells. Indeed, there is

ways of placing the agents' colors. So one can compute the stationary distribute function for the coarse-grained states {ρ q }:

where

The configurations that maximize the potential F (x) = q f (n R , n G , T ) are the more probable to come up. In the limit H/T → ∞, these configurations are even the only ones that will appear in the stationary states (since Π(x)/Π(y) = e H/T (F (x)-F (y)) → 0 for F (x) -F (y) < 0 and H/T → ∞).

Continuous limit

In the limit H → ∞, by keeping constant the mean density ρ 0 = N 0 /H and the density of each block ρ q = n q /H (ρ q hence becoming a continuous variable), one has thanks to Stirling's formula:

and the stationary distribution can be written as:

where the "block-potential" is

The problem hence gets back to find the set {ρ qR , ρ qG } which maximize the potential F = q f (ρ qR , ρ qG , T ) with the constraints q ρ qR = Qρ 0R and q ρ qG = Qρ 0G .

If one compares this result with the result of the one population model, it can be seen that for a zero temperature the 'two populations model' is obtained by summing 208 two 'one population models', one for each color. But at a non-zero temperature the

term links both populations.

B.3.2 Homogeneous-inhomogeneous transitions

The homogeneous phase may be unstable with respect to phase separation.

Let us split the system into two phases of densities ρ 1 = (ρ 1R , ρ 1G ) and ρ 2 = (ρ 2R , ρ 2G ).

The constraint that the overall densities of particles/agents are ρ 0 = (ρ 0R , ρ 0G ) is expressed by the lever rule:

where Q 1 and Q 2 are respectively the number of blocks of density ρ 1 and ρ 2 . The homogeneous phase is stable against phase separation if for all ρ 1 and ρ 2

Geometrically, this inequality corresponds to requiring that f (ρ) is a concave function.

When the concavity requirement is violated, phase separation will occur for certain values of ρ 0 . The equilibrium densities ρ 1 and ρ 2 are such that the line that joins the points (ρ 1 , f (ρ 1 )) and (ρ 2 ,f (ρ 2 )) is part of the concave hull of the function.

In the 2 populations model there is a possibility that the system is split into 3 phases of densities ρ 1 = (ρ 1R , ρ 1G ), ρ 2 = (ρ 2R , ρ 2G ) and ρ 3 = (ρ 3R , ρ 3G ). The constraint that the overall densities of particles/agents are ρ 0 = (ρ 0R , ρ 0G ) is now:

where Q 1 , Q 2 and Q 3 are respectively the number of blocks of density ρ 1 , ρ 2 and ρ 3 .

And the equilibrium densities ρ 1 , ρ 2 and ρ 3 are now such that the plane that joins the points (ρ 1 , f (ρ 1 )), (ρ 2 ,f (ρ 2 )) and (ρ 3 ,f (ρ 3 )) is part of the concave hull of the function.

For some values of the parameters there may even be 4 points of the same plane belonging to the f function and its concave hull. In this case there will be a continuum of possible values of Q 1 , Q 2 , Q 3 and Q 4 verifying the global density constraints.

and convex in ρ R ).

The concave hull of the function has a different form for different values of the parameters α and m:

• for α ≥ 1 3-2m the points 0, 1 2 , f (0, 1 2 ) and 1 2 , 0, f ( 1 2 , 0) belong to the concave hull whereas for α ≤ 1 3-2m they are replaced by the points 0, ρ 2 , f (0, ρ 2 ) and

1-m (see the resolution of the one population model).

2 ) belongs to the concave hull whereas for α < m 4-3m it does not. • α ≥ 1 3-2m (which will be case 1)

The number and composition of the phases depend on the global densities ρ 0 = (ρ 0R , ρ 0G ) (see figure B.7).

211

In part A of figure B.7, the system separates into 3 or 4 phases of densities (0, 0), (0, 1 2 ), ( 1 2 , 0) and

The system can build either 3 or 4 phases because red and green agents do not "see" each other: their utility is maximal when half of the block is filled with agents of their color, the other half being either empty or filled with agents of the other color.

In part B, the system separates into 2 phases of densities ( ρ 0R -ρ 0G 1-2ρ 0G , 0) and ( 1 2 , 1 2 ) with respective weights

And symmetrically in part C the system separates into 2 phases of densities (0, ρ 0G -ρ 0R 1-2ρ 0R ) and ( 12 , 1 2 ) with respective weights

Case 2

The number and composition of the phases depend again on the global densities as shown on figure B.8.

In part A of figure B.8, the system separates into 3 phases of densities (0, 0), (0, ρ 2 (α, m))

and (ρ 2 (α, m), 0) in respective quantities is a phase of half-red, half-green blocks and another phase containing the excess of the more numerous type of agents with a higher density (and thus an inferior utility).

For T > 0 At high temperatures, the entropic term of the f function is the leading term, and as it is a concave one, the function is concave everywhere : for any density ρ 0 = (ρ 0R , ρ 0G ), the system stays in an homogeneous phase because of the strong noise.

For intermediary values of the temperature, the system has a behavior between a noise driven one and the one it has at zero temperature, but we will not further study it here.

Appendix C

Annex

Complex Systems Science -An Historical Perspective

In this appendix devoted to the bibliometric study of Complex Systems Science (CSS), we explore the historic evolution of Complex Systems Science. We present some preliminary maps of CSS corresponding to different time periods and we build on the properties of bibliometric coupling to detect the chronological affiliation of communities.

D.1 Complex Systems History

D.1.1 Database

The "Complex Systems" database gathered from WoS contains in total 215 000 records of articles published from 1950 to 2009. The results presented in the last chapter were only based on data corresponding to articles published after 2000, ie in the most recent period. In this section, we present results based on the whole database. Its overall increase with time reflects the general increase of scientific production. A large jump in the number of published articles can be observed around 1990. While it might be tempting to interprete this jump as a historical event (a sudden interest for the Complex Systems science or a massive increase in the scientific production due to the wide circulation of computers), it is in fact merely a bias introduced by the WoS's extraction tools. Indeed, when a query is put in WoS, the Topic Keywords of the query are looked for in the titles, article's keywords and, in case of publication posterior to 1990, abstracts. This means that our query looking for specific Topic Keywords

224

(as defined in Table 5.5) reaches many more articles published after 1990, those which contain these Topic Keywords exclusively in their abstracts.

To study the historical evolution of the science of complex systems, we divided the records in several 10-years slices according to their publication year. For each decade, we build a network where the nodes correspond to the articles published in the corresponding period of time and where a link between two nodes indicates that the papers corresponding to these nodes share at least one reference. The weight of the link is taken as the BC cosine distance defined in Eq. 5.1. The general characteristics of these networks are displayed in Table D.1. For the first decades (roughly until 1985), the number of articles is rather low. The networks can be easily built and submitted to a manual analysis. For the last decades, the numbers of articles becomes very important, the mean density 2M/N (N -1) decreases with time while the mean distance < ω ij > -1 increases, a sign that the networks are on average more heterogeneous in recent periods. On the other side, the mean degree M/N of an article increases with the time period, a sign that the networks contain more homogeneous subparts. is the numbers of articles in our database, N is the number of article in the network (ie sharing at least one reference with at least an other articles of our basis), M is the number of BC links (hence 2M/N (N -1) is the density of number of links in the graph and M/N is the mean number of links in which an article takes part, its degree). The average < ω ij > is done on the N (N -1)/2 pairs of articles. It can be taken as a measure of a "bibliographic coupling" network inner-coherence, while < ω ij > -1 can be seen as a characteristic "bibliographic distance" of each network. Indeed, if the links' weights were homogeneously distributed, two randomly chosen articles would share one reference over < ω ij > -1 .

D.1.2 Chronologically successive maps

Methods

Starting from the last decades (1985-1995, 1990-1999, 1995-2004 and 2000-2009), we first obtain a network by applying the Louvain algorithm [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF]. This step gives a general perspective on the structuration and evolution of the composition of our database in terms of large scientific fields. We typically obtain a dozen large field communities in each decade (see Table D.2). In order to gain a better understanding on the composition of these fields and on the nature of their links, we apply the same two-steps procedure introduced last chapter. We group the papers in two hierarchical community networks for each decade, a rough one (field structuration) and a specific one (subfields). Applying the Louvain algorithm once to the entire network yields the field communities. The subfield communities are obtained by

• applying the Louvain algorithm to each field community

• checking if the obtain substructure of each field has is meaningful (internal modularity Q i ≥ 0.4) and whether each subfield check Eq. D.1 in the global subfield network. If these two conditions are not respected for a given field, it is kept as a whole in the subfield network. Table D.3: Fields' size N , inner coherence < ω > -1 and internal modularity Q i . Fields whose subfield structure was found to be unsignificative (roughly Q i < 0.2) are enlightened in colors. In all cases, the biological fields were gathered as a single field just before the computation of the subfield communities. Hence the lack of some values of internal modularity and the fact that these communities share the same color on Fig D .3. In the same way, the Quantum Chaos and Statistical Physics field were merged with the Dynamic Systems fields before the second partitions.

Results

Fig. D

.3 displays the largest field community networks obtained for the four successive and overlapping decades. We first note that these different networks show a remarkable continuity. At the center of these networks, we find theoretical domains: self-organized criticality, dynamical systems, complex networks and neural networks. These fields are linked to more experimental fields (materials science, biology or neurosciences) lying at the periphery of the networks. Among all these communities, two in particular stand out. First, the complex networks (CN) community, which appears only from the 1995-2004 decade since its main founding references (namely Albert & Barabasi, 2002;Barabasi & Albert, 1999;[START_REF] Watts | Collective dynamics of small-world networks[END_REF]Newman, 2003, see appendix B) were all published after 1995. This community has the strongest coherence : on average, the mean bibliographic coupling weight between two articles of this community is < ω > ∼ 1/20 (see Table D.3). This value means that two papers taken randomly from this community very often share a reference. This coherence remained stable while the number of articles increased from around 900 in the 1995-2004 decade to around 3700 the 2000's (see Table D.3). The self-organized criticality (SOC) community presents similar characteristics: its main founding references are well-defined (namely [START_REF] Bak | Self-organized criticality: an explanation of 1/f noise[END_REF][START_REF] Bak | Self-organized criticality[END_REF], see appendix B) and its coherence is among the strongest. However, the scientific production of this community has begun to decrease (around 4800 articles in the 1990-1999 decade vs around 4400 in the 1995-decade. This decrease is significant when compared to the general increase of scientific production. In the meantime, the average coherence decreased from < ω >∼ 1/40 in the 1985-1994 decade to < ω >∼ 1/200 in the 2000-2009 one (see Table D.3). Compared to complex networks, self-organized criticality seems to be declining as a scientific community.

A point worth noting is that while most communities are close to "standard" disciplines such as those of the Web of Science subject index, CN and SOC communities do not. This shows the importance of using bibliographic coupling to define communities instead of taking as starting points the Web of Science "subject categories".

We now come to the level of subfield communities. The subfield networks displayed Of course all these observations need to be deepened by a close historical analysis of the precise shared references between all these communities, the institutions and personal links at the origin of these evolutions.

Abstract

This thesis explores the problems raised by the aggregation of entities into a global, collective level, an old problem encountered in many fields of science. We work on three projects related to the aggregation problem in social systems, using tools derived from statistical physics, and more generally quantitative tools. Great care is taken to tackle the questions at the heart of these projects in a mutually beneficial way for both social and natural sciences. The second project is based on the exploration of huge databases on scientific literature (mostly Web of Science) to investigate the existence and evolution of paradigms or scientific institutions. We mostly use the old but quite unused bibliographic coupling (BC) approach, based on a normalized number of shared references, to measure relations between articles. Using standard techniques to group similar articles, we can define 'natural' communities characterized by their references. Thanks to a large database (141 098 records) of relevant articles, we used this approach to empirically study the 'complex systems' field. We show that the overall coherence of the field does not arise from a universal theory but rather from computational techniques and fruitful adaptations of the idea of self organization to specific systems. We also investigate the idea of 'trading zones', small communities creating an interface between disciplines around specific tools or concepts. We also apply our approach to develop a set of routines allowing to draw different maps of the research carried out in a scientific institution, specifically co-occurrence (of authors, keywords, institutions) maps and BC communities maps. We use the example of the ENS de Lyon to discuss why these maps may become a valuable tool for institutions' directors.

Finally, the third project deals with the emergence of 'institutions' or 'structures' in social systems. Our collaboration with a team of sociologists has lead us to question the assumption of a clear dichotomy between two 'levels', namely individuals and society.

Building on the social theory developed by Gabriel Tarde at the end of the 19th century, we explore different possibility to visualize (and conceptualize) the evolution of social phenomena without making a distinction between two levels. Bibliometric data are used as an example. We also propose an attempt to formalize Tarde's theory in the scope of an algorithmic model. The point is to show how one can obtain 'wholes' through the simplification of complex individuals. While our prototype model fulfil several of Tarde's precept, it raises many more questions. Finally, we focus on a single question raised by our colleagues sociologists: the existence of lasting structure from non lasting entities.

We build on the physicist's approach developed in opinion models. While most papers focus on stationary properties, we choose to build a model to investigate the dynamical properties of social structures which are always changing. The key ingredients of our model are the introduction of noise in the agents' interactions, a turnover in the population of agents and a generation effect, the agents taking into account their opinion and age difference in their interaction. The outcomes of our model display a rich phenomenology of group dynamics. Our point is not to produce realistic representations of reality, but much more to help the sociologists enrich their conceptualizations of social phenomena.

Keywords: social systems, collective phenomena, segregation, coordination, complex systems, maps of science, bibliographic coupling, Tarde, opinion model. aa