Evolutionary games on complex networks : the emergence and maintenance of cooperation

Abstract The object of game theory lies in the analysis of situations where different social actors have conflicting requirements and where their individual decisions will all influence the global outcome. In this framework, several games have been invented to capture the essence of various dilemmas encountered in many common important socio-economic situations. Even though these games often succeed in helping us understand human or animal behavior in interactive settings, some experiments have shown that people tend to cooperate with each other in situations for which classical game theory strongly recommends them to do the exact opposite. Several mechanisms have been invoked to try to explain the emergence of this unexpected cooperative attitude. Among them, repeated interaction, reputation, and belonging to a recognizable group have often been mentioned. However, the work of Nowak and May (1992) showed that the simple fact of arranging the players according to a spatial structure and only allowing them to interact with their immediate neighbors is sufficient to sustain a certain amount of cooperation even when the game is played anonymously and without repetition. Nowak and May's study and much of the following work was based on regular structures such as two-dimensional grids. Axelrod et al. (2002) showed that by randomizing the choice of neighbors, i.e. by actually giving up a strictly local geographical structure, cooperation can still emerge, provided that the interaction patterns remain stable in time. This is a first step towards a social network structure. However, following pioneering work by sociologists in the sixties such as that of Milgram (1967), in the last few years it has become apparent that many social and biological interaction networks, and even some technological networks, have particular, and partly unexpected, properties that set them apart from regular or random graphs. Among other things, they usually display broad degree distributions, and show small-world topological structure. Roughly speaking, a small-world graph is a network where any individual is relatively close, in terms of social ties, to any other individual, a property also found in random graphs but not in regular lattices. However, in contrast with random graphs, small-world networks also have a certain amount of local structure, as measured, for instance, by a quantity called the clustering coefficient. In the same vein, many real conflicting situations in economy and sociology are not well described neither by a fixed geographical position of the individuals in a regular lattice, nor by a random graph. Furthermore, it is a known fact that network structure can highly influence dynamical phenomena such as the way diseases spread across a population and ideas or information get transmitted. Therefore, in the last decade, research attention has naturally shifted from random and regular graphs towards better models of social interaction structures. The primary goal of this work is to discover whether or not the underlying graph structure of real social networks could give explanations as to why one finds higher levels of cooperation in populations of human beings or animals than what is prescribed by classical game theory. To meet this objective, I start by thoroughly studying a real scientific coauthorship network and showing how it differs from biological or technological networks using divers statistical measurements. Furthermore, I extract and describe its community structure taking into account the intensity of a collaboration. Finally, I investigate the temporal evolution of the network, from its inception to its state at the time of the study in 2006, suggesting also an effective view of it as opposed to a historical one. Thereafter, I combine evolutionary game theory with several network models along with the studied coauthorship network in order to highlight which specific network properties foster cooperation and shed some light on the various mechanisms responsible for the maintenance of this same cooperation. I point out the fact that, to resist defection, cooperators take advantage, whenever possible, of the degree-heterogeneity of social networks and their underlying community structure. Finally, I show that cooperation level and stability depend not only on the game played, but also on the evolutionary dynamic rules used and the individual payoff calculations. Synopsis Le but de la théorie des jeux réside dans l'analyse de situations dans lesquelles différents acteurs sociaux, avec des objectifs souvent conflictuels, doivent individuellement prendre des décisions qui influenceront toutes le résultat global. Dans ce cadre, plusieurs jeux ont été inventés afin de saisir l'essence de divers dilemmes rencontrés dans d'importantes situations socio-économiques. Bien que ces jeux nous permettent souvent de comprendre le comportement d'êtres humains ou d'animaux en interactions, des expériences ont montré que les individus ont parfois tendance à coopérer dans des situations pour lesquelles la théorie classique des jeux prescrit de faire le contraire. Plusieurs mécanismes ont été invoqués pour tenter d'expliquer l'émergence de ce comportement coopératif inattendu. Parmi ceux-ci, la répétition des interactions, la réputation ou encore l'appartenance à des groupes reconnaissables ont souvent été mentionnés. Toutefois, les travaux de Nowak et May (1992) ont montré que le simple fait de disposer les joueurs selon une structure spatiale en leur permettant d'interagir uniquement avec leurs voisins directs est suffisant pour maintenir un certain niveau de coopération même si le jeu est joué de manière anonyme et sans répétitions. L'étude de Nowak et May, ainsi qu'un nombre substantiel de travaux qui ont suivi, étaient basés sur des structures régulières telles que des grilles à deux dimensions. Axelrod et al. (2002) ont montré qu'en randomisant le choix des voisins, i.e. en abandonnant une localisation géographique stricte, la coopération peut malgré tout émerger, pour autant que les schémas d'interactions restent stables au cours du temps. Ceci est un premier pas en direction d'une structure de réseau social. Toutefois, suite aux travaux précurseurs de sociologues des années soixante, tels que ceux de Milgram (1967), il est devenu clair ces dernières années qu'une grande partie des réseaux d'interactions sociaux et biologiques, et même quelques réseaux technologiques, possèdent des propriétés particulières, et partiellement inattendues, qui les distinguent de graphes réguliers ou aléatoires. Entre autres, ils affichent en général une distribution du degré relativement large ainsi qu'une structure de "petit-monde". Grossièrement parlant, un graphe "petit-monde" est un réseau où tout individu se trouve relativement près de tout autre individu en termes de distance sociale, une propriété également présente dans les graphes aléatoires mais absente des grilles régulières. Par contre, les réseaux "petit-monde" ont, contrairement aux graphes aléatoires, une certaine structure de localité, mesurée par exemple par une quantité appelée le "coefficient de clustering". Dans le même esprit, plusieurs situations réelles de conflit en économie et sociologie ne sont pas bien décrites ni par des positions géographiquement fixes des individus en grilles régulières, ni par des graphes aléatoires. De plus, il est bien connu que la structure même d'un réseau peut passablement influencer des phénomènes dynamiques tels que la manière qu'a une maladie de se répandre à travers une population, ou encore la façon dont des idées ou une information s'y propagent. Ainsi, durant cette dernière décennie, l'attention de la recherche s'est tout naturellement déplacée des graphes aléatoires et réguliers vers de meilleurs modèles de structure d'interactions sociales. L'objectif principal de ce travail est de découvrir si la structure sous-jacente de graphe de vrais réseaux sociaux peut fournir des explications quant aux raisons pour lesquelles on trouve, chez certains groupes d'êtres humains ou d'animaux, des niveaux de coopération supérieurs à ce qui est prescrit par la théorie classique des jeux. Dans l'optique d'atteindre ce but, je commence par étudier un véritable réseau de collaborations scientifiques et, en utilisant diverses mesures statistiques, je mets en évidence la manière dont il diffère de réseaux biologiques ou technologiques. De plus, j'extrais et je décris sa structure de communautés en tenant compte de l'intensité d'une collaboration. Finalement, j'examine l'évolution temporelle du réseau depuis son origine jusqu'à son état en 2006, date à laquelle l'étude a été effectuée, en suggérant également une vue effective du réseau par opposition à une vue historique. Par la suite, je combine la théorie évolutionnaire des jeux avec des réseaux comprenant plusieurs modèles et le réseau de collaboration susmentionné, afin de déterminer les propriétés structurelles utiles à la promotion de la coopération et les mécanismes responsables du maintien de celle-ci. Je mets en évidence le fait que, pour ne pas succomber à la défection, les coopérateurs exploitent dans la mesure du possible l'hétérogénéité des réseaux sociaux en termes de degré ainsi que la structure de communautés sous-jacente de ces mêmes réseaux. Finalement, je montre que le niveau de coopération et sa stabilité dépendent non seulement du jeu joué, mais aussi des règles de la dynamique évolutionnaire utilisées et du calcul du bénéfice d'un individu.

Comparing Multilevel Clustering Methods on Weighted Graphs : The Case of Worldwide Air Passenger Traffic 2000-2004

Specific properties emerge from the structure of large networks, such as that of worldwide air traffic, including a highly hierarchical node structure and multi-level small world sub-groups that strongly influence future dynamics. We have developed clustering methods to understand the form of these structures, to identify structural properties, and to evaluate the effects of these properties. Graph clustering methods are often constructed from different components: a metric, a clustering index, and a modularity measure to assess the quality of a clustering method. To understand the impact of each of these components on the clustering method, we explore and compare different combinations. These different combinations are used to compare multilevel clustering methods to delineate the effects of geographical distance, hubs, network densities, and bridges on worldwide air passenger traffic. The ultimate goal of this methodological research is to demonstrate evidence of combined effects in the development of an air traffic network. In fact, the network can be divided into different levels of âeurooecohesionâeuro, which can be qualified and measured by comparative studies (Newman, 2002; Guimera et al., 2005; Sales-Pardo et al., 2007).

Adolescents' beliefs about marijuana use: a comparison of regular users, past users and never/occasional users.

A questionnaire investigating adolescents' opinions and experiences regarding marijuana use was administered to 163 adolescents and young adults (96 boys and 67 girls) aged 13 to 20 (mean age = 16.8, s.d. = 1.5). Items referred to marijuana and other substances' dangerousness, representations regarding the positive and negative consequences of marijuana use. Responses were compared according to marijuana use status (classified into never/occasional use, current regular use and past regular use). Results show that adolescents' opinions differ according to their experience with marijuana use. Current regular users evaluate marijuana as less dangerous, but alcohol and heroin as more dangerous in comparison with never/occasional and past users. Current and past users are more likely to define marijuana as a medical drug and a plant used in agriculture, and less likely to define it as an illegal drug. Current and past users evaluate marijuana use as a way to cope with stress, to relax to a greater extent than do never/occasional users do. The latter attribute more negative consequences to marijuana use such as diminished driving ability and school performance and a pathway to hard drugs.

The forgotten face of regular physical exercise: a 'natural' anti-atherogenic activity.

Humans are not programmed to be inactive. The combination of both accelerated sedentary lifestyle and constant food availability disturbs ancient metabolic processes leading to excessive storage of energy in tissue, dyslipidaemia and insulin resistance. As a consequence, the prevalence of Type 2 diabetes, obesity and the metabolic syndrome has increased significantly over the last 30 years. A low level of physical activity and decreased daily energy expenditure contribute to the increased risk of cardiovascular morbidity and mortality following atherosclerotic vascular damage. Physical inactivity leads to the accumulation of visceral fat and consequently the activation of the oxidative stress/inflammation cascade, which promotes the development of atherosclerosis. Considering physical activity as a 'natural' programmed state, it is assumed that it possesses atheroprotective properties. Exercise prevents plaque development and induces the regression of coronary stenosis. Furthermore, experimental studies have revealed that exercise prevents the conversion of plaques into a vulnerable phenotype, thus preventing the appearance of fatal lesions. Exercise promotes atheroprotection possibly by reducing or preventing oxidative stress and inflammation through at least two distinct pathways. Exercise, through laminar shear stress activation, down-regulates endothelial AT1R (angiotensin II type 1 receptor) expression, leading to decreases in NADPH oxidase activity and superoxide anion production, which in turn decreases ROS (reactive oxygen species) generation, and preserves endothelial NO bioavailability and its protective anti-atherogenic effects. Contracting skeletal muscle now emerges as a new organ that releases anti-inflammatory cytokines, such as IL-6 (interleukin-6). IL-6 inhibits TNF-α (tumour necrosis factor-α) production in adipose tissue and macrophages. The down-regulation of TNF-α induced by skeletal-muscle-derived IL-6 may also participate in mediating the atheroprotective effect of physical activity.

Challenging the "inoffensiveness" of regular cannabis use by its associations with other current risky substance use--a census of 20-year-old Swiss men.

3,537 men enrolling in 2007 for mandatory army recruitment procedures were assessed for the co-occurrence of risky licit substance use among risky cannabis users. Risky cannabis use was defined as at least twice weekly; risky alcohol use as 6+ drinks more than once/monthly, or more than 20 drinks per week; and risky tobacco use as daily smoking. Ninety-five percent of all risky cannabis users reported other risky use. They began using cannabis earlier than did non-risky users, but age of onset was unrelated to other risky substance use. A pressing public health issue among cannabis users stems from risky licit substance use warranting preventive efforts within this age group.

The evolution of helping and harming on graphs: the return of the inclusive fitness effect.

Evolutionary graph theory has been proposed as providing new fundamental rules for the evolution of co-operation and altruism. But how do these results relate to those of inclusive fitness theory? Here, we carry out a retrospective analysis of the models for the evolution of helping on graphs of Ohtsuki et al. [Nature (2006) 441, 502] and Ohtsuki & Nowak [Proc. R. Soc. Lond. Ser. B Biol. Sci (2006) 273, 2249]. We show that it is possible to translate evolutionary graph theory models into classical kin selection models without disturbing at all the mathematics describing the net effect of selection on helping. Model analysis further demonstrates that costly helping evolves on graphs through limited dispersal and overlapping generations. These two factors are well known to promote relatedness between interacting individuals in spatially structured populations. By allowing more than one individual to live at each node of the graph and by allowing interactions to vary with the distance between nodes, our inclusive fitness model allows us to consider a wider range of biological scenarios leading to the evolution of both helping and harming behaviours on graphs.

The effects of dominance, regular inbreeding and sampling design on Q(ST), an estimator of population differentiation for quantitative traits.

To test whether quantitative traits are under directional or homogenizing selection, it is common practice to compare population differentiation estimates at molecular markers (F(ST)) and quantitative traits (Q(ST)). If the trait is neutral and its determinism is additive, then theory predicts that Q(ST) = F(ST), while Q(ST) > F(ST) is predicted under directional selection for different local optima, and Q(ST) < F(ST) is predicted under homogenizing selection. However, nonadditive effects can alter these predictions. Here, we investigate the influence of dominance on the relation between Q(ST) and F(ST) for neutral traits. Using analytical results and computer simulations, we show that dominance generally deflates Q(ST) relative to F(ST). Under inbreeding, the effect of dominance vanishes, and we show that for selfing species, a better estimate of Q(ST) is obtained from selfed families than from half-sib families. We also compare several sampling designs and find that it is always best to sample many populations (>20) with few families (five) rather than few populations with many families. Provided that estimates of Q(ST) are derived from individuals originating from many populations, we conclude that the pattern Q(ST) > F(ST), and hence the inference of directional selection for different local optima, is robust to the effect of nonadditive gene actions.

Effects of regular insulin or insulin LISPRO on glucose metabolism after an oral glucose load in patients with type 2 diabetes mellitus.

Seven obese Type 2 diabetic patients were studied for two 4-h periods after ingestion of a glucose load to determine the effects of preprandial subcutaneous injection of Insulin Lispro (5 min before the meal) or regular insulin (20 min before the meal) on glucose metabolism. Glucose production and utilisation were measured using a dual isotope method. After Lispro, the mean postprandial increase in plasma glucose was 29% lower and the increase in insulin concentration 25% higher than after regular insulin (p < 0.05). Suppression of endogenous glucose production was similar with both types of insulin. Thus, preprandial injection of Lispro reduced postprandial glucose increments in Type 2 diabetic patients as compared to regular insulin. This effect is best explained by the increased postprandial bioavailability of Lispro.

Comparison of cannabinoid concentrations in oral fluid and whole blood between occasional and regular cannabis smokers prior to and after smoking a cannabis joint.

A cross-over controlled administration study of smoked cannabis was carried out on occasional and heavy smokers. The participants smoked a joint (11 % Δ9-tetrahydrocannabinol (THC)) or a matching placebo on two different occasions. Whole blood (WB) and oral fluid (OF) samples were collected before and up to 3.5 h after smoking the joints. Pharmacokinetic analyses were obtained from these data. Questionnaires assessing the subjective effects were administered to the subjects during each session before and after the smoking time period. THC, 11-hydroxy-THC (11-OH-THC) and 11-nor-9-carboxy-THC (THCCOOH) were analyzed in the blood by gas chromatography or liquid chromatography (LC)-tandem mass spectrometry (MS/MS). The determination of THC, THCCOOH, cannabinol (CBN), and Δ9-tetrahydrocannabinolic acid A (THC-A) was carried out on OF only using LC-MS/MS. In line with the widely accepted assumption that cannabis smoking results in a strong contamination of the oral cavity, we found that THC, and also THC-A, shows a sharp, high concentration peak just after smoking, with a rapid decrease in these levels within 3 h. No obvious differences were found between both groups concerning THC median maximum concentrations measured either in blood or in OF; these levels were equal to 1,338 and 1,041 μg/L in OF and to 82 and 94 μg/L in WB for occasional and heavy smokers, respectively. The initial WB THCCOOH concentration was much higher in regular smokers than in occasional users. Compared with the occasional smokers, the sensation of confusion felt by the regular smokers was much less while the feeling of intoxication remained almost unchanged.

Challenging the "inoffensiveness" of regular cannabis use by its associations with other current risky substance use--a census of 20-year-old Swiss men.

3,537 men enrolling in 2007 for mandatory army recruitment procedures were assessed for the co-occurrence of risky licit substance use among risky cannabis users. Risky cannabis use was defined as at least twice weekly; risky alcohol use as 6+ drinks more than once/monthly, or more than 20 drinks per week; and risky tobacco use as daily smoking. Ninety-five percent of all risky cannabis users reported other risky use. They began using cannabis earlier than did non-risky users, but age of onset was unrelated to other risky substance use. A pressing public health issue among cannabis users stems from risky licit substance use warranting preventive efforts within this age group.

Artificial evolution on network structures : how time and space influence dynamics

Abstract The main objective of this work is to show how the choice of the temporal dimension and of the spatial structure of the population influences an artificial evolutionary process. In the field of Artificial Evolution we can observe a common trend in synchronously evolv¬ing panmictic populations, i.e., populations in which any individual can be recombined with any other individual. Already in the '90s, the works of Spiessens and Manderick, Sarma and De Jong, and Gorges-Schleuter have pointed out that, if a population is struc¬tured according to a mono- or bi-dimensional regular lattice, the evolutionary process shows a different dynamic with respect to the panmictic case. In particular, Sarma and De Jong have studied the selection pressure (i.e., the diffusion of a best individual when the only selection operator is active) induced by a regular bi-dimensional structure of the population, proposing a logistic modeling of the selection pressure curves. This model supposes that the diffusion of a best individual in a population follows an exponential law. We show that such a model is inadequate to describe the process, since the growth speed must be quadratic or sub-quadratic in the case of a bi-dimensional regular lattice. New linear and sub-quadratic models are proposed for modeling the selection pressure curves in, respectively, mono- and bi-dimensional regu¬lar structures. These models are extended to describe the process when asynchronous evolutions are employed. Different dynamics of the populations imply different search strategies of the resulting algorithm, when the evolutionary process is used to solve optimisation problems. A benchmark of both discrete and continuous test problems is used to study the search characteristics of the different topologies and updates of the populations. In the last decade, the pioneering studies of Watts and Strogatz have shown that most real networks, both in the biological and sociological worlds as well as in man-made structures, have mathematical properties that set them apart from regular and random structures. In particular, they introduced the concepts of small-world graphs, and they showed that this new family of structures has interesting computing capabilities. Populations structured according to these new topologies are proposed, and their evolutionary dynamics are studied and modeled. We also propose asynchronous evolutions for these structures, and the resulting evolutionary behaviors are investigated. Many man-made networks have grown, and are still growing incrementally, and explanations have been proposed for their actual shape, such as Albert and Barabasi's preferential attachment growth rule. However, many actual networks seem to have undergone some kind of Darwinian variation and selection. Thus, how these networks might have come to be selected is an interesting yet unanswered question. In the last part of this work, we show how a simple evolutionary algorithm can enable the emrgence o these kinds of structures for two prototypical problems of the automata networks world, the majority classification and the synchronisation problems. Synopsis L'objectif principal de ce travail est de montrer l'influence du choix de la dimension temporelle et de la structure spatiale d'une population sur un processus évolutionnaire artificiel. Dans le domaine de l'Evolution Artificielle on peut observer une tendence à évoluer d'une façon synchrone des populations panmictiques, où chaque individu peut être récombiné avec tout autre individu dans la population. Déjà dans les année '90, Spiessens et Manderick, Sarma et De Jong, et Gorges-Schleuter ont observé que, si une population possède une structure régulière mono- ou bi-dimensionnelle, le processus évolutionnaire montre une dynamique différente de celle d'une population panmictique. En particulier, Sarma et De Jong ont étudié la pression de sélection (c-à-d la diffusion d'un individu optimal quand seul l'opérateur de sélection est actif) induite par une structure régulière bi-dimensionnelle de la population, proposant une modélisation logistique des courbes de pression de sélection. Ce modèle suppose que la diffusion d'un individu optimal suit une loi exponentielle. On montre que ce modèle est inadéquat pour décrire ce phénomène, étant donné que la vitesse de croissance doit obéir à une loi quadratique ou sous-quadratique dans le cas d'une structure régulière bi-dimensionnelle. De nouveaux modèles linéaires et sous-quadratique sont proposés pour des structures mono- et bi-dimensionnelles. Ces modèles sont étendus pour décrire des processus évolutionnaires asynchrones. Différentes dynamiques de la population impliquent strategies différentes de recherche de l'algorithme résultant lorsque le processus évolutionnaire est utilisé pour résoudre des problèmes d'optimisation. Un ensemble de problèmes discrets et continus est utilisé pour étudier les charactéristiques de recherche des différentes topologies et mises à jour des populations. Ces dernières années, les études de Watts et Strogatz ont montré que beaucoup de réseaux, aussi bien dans les mondes biologiques et sociologiques que dans les structures produites par l'homme, ont des propriétés mathématiques qui les séparent à la fois des structures régulières et des structures aléatoires. En particulier, ils ont introduit la notion de graphe sm,all-world et ont montré que cette nouvelle famille de structures possède des intéressantes propriétés dynamiques. Des populations ayant ces nouvelles topologies sont proposés, et leurs dynamiques évolutionnaires sont étudiées et modélisées. Pour des populations ayant ces structures, des méthodes d'évolution asynchrone sont proposées, et la dynamique résultante est étudiée. Beaucoup de réseaux produits par l'homme se sont formés d'une façon incrémentale, et des explications pour leur forme actuelle ont été proposées, comme le preferential attachment de Albert et Barabàsi. Toutefois, beaucoup de réseaux existants doivent être le produit d'un processus de variation et sélection darwiniennes. Ainsi, la façon dont ces structures ont pu être sélectionnées est une question intéressante restée sans réponse. Dans la dernière partie de ce travail, on montre comment un simple processus évolutif artificiel permet à ce type de topologies d'émerger dans le cas de deux problèmes prototypiques des réseaux d'automates, les tâches de densité et de synchronisation.