Complexity - A Guided Tour Part 14

Recall from my discussion of Robby the Robot in chapter 9 that a strategy is a set of rules that gives, for any situation, the action one should take in that situation. For the Prisoner's Dilemma, a strategy consists of a rule for deciding whether to cooperate or defect on the next turn, depending on the opponent's behavior on previous turns.

The first tournament received fourteen submitted programs; the second tournament jumped to sixty-three programs. Each program played with every other program for 200 turns, collecting points according to the payoff matrix in figure 14.3. The programs had some memory-each program could store the results of at least some of its previous turns against each opponent. Some of the strategies submitted were rather complicated, using statistical techniques to characterize other players' "psychology." However, in both tournaments the winner (the strategy with the highest average score over games with all other players) was the simplest of the submitted strategies: t.i.t FOR TAT. This strategy, submitted by mathematician Anatol Rapoport, cooperates on the first turn and then, on subsequent turns, does whatever the opponent did for its move on the previous turn. That is, t.i.t FOR TAT offers cooperation and reciprocates it. But if the other player defects, t.i.t FOR TAT punishes that defection with a defection of its own, and continues the punishment until the other player begins cooperating again.

It is surprising that such a simple strategy could beat out all others, especially in light of the fact that the entrants in the second tournament already knew about t.i.t FOR TAT so could plan against it. However, out of the dozens of experts who partic.i.p.ated, no one was able to design a better strategy.

Axelrod drew some general conclusions from the results of these tournaments. He noted that all of the top scoring strategies have the attribute of being nice-that is, they are never the first one to defect. The lowest scoring of all the nice programs was the "least forgiving" one: it starts out by cooperating but if its opponent defects even once, it defects against that opponent on every turn from then on. This contrasts with t.i.t FOR TAT, which will punish an opponent's defection with a defection of its own, but will forgive that opponent by cooperating once the opponent starts to cooperate again.

Axelrod also noted that although the most successful strategies were nice and forgiving, they also were retaliatory-they punished defection soon after it occurred. t.i.t FOR TAT not only was nice, forgiving, and retaliatory, but it also had another important feature: clarity and predictability. An opponent can easily see what t.i.t FOR TAT's strategy is and thus predict how it would respond to any of the opponent's actions. Such predictability is important for fostering cooperation.

Interestingly, Axelrod followed up his tournaments by a set of experiments in which he used a genetic algorithm to evolve strategies for the Prisoner's Dilemma. The fitness of an evolving strategy is its score after playing many repeated games with the other evolving strategies in the population. The genetic algorithm evolved strategies with the same or similar behavior as t.i.t FOR TAT.

EXTENSIONS OF THE PRISONER'S DILEMMA

Axelrod's studies of the Prisoner's Dilemma made a big splash starting in the 1980s, particularly in the social sciences. People have studied all kinds of variations on the game-different payoff matrices, different number of players, multiplayer games in which players can decide whom to play with, and so on. Two of the most interesting variations experimented with adding social norms and spatial structure, respectively.

Adding Social Norms.

Axelrod experimented with adding norms to the Prisoner's Dilemma, where norms correspond to social censure (in the form of negative points) for defecting when others catch the defector in the act. In Axelrod's multiplayer game, every time a player defects, there is some probability that some other players will witness that defection. In addition to a strategy for playing a version of the Prisoner's Dilemma, each player also has a strategy for deciding whether to punish (subtract points from) a defector if the punisher witnesses the defection.

In particular, each player's strategies consist of two numbers: a probability of defecting (boldness) and a probability of punis.h.i.+ng a defection that the player witnesses (vengefulness). In the initial population of players, these probability values are a.s.signed at random to each individual.

At each generation, the population plays a round of the game: each player in the population plays a single game against all other players, and each time a player defects, there is some probability that the defection is witnessed by other population members. Each witness will punish the defector with a probability defined by the witness's vengefulness value.

At the end of each round, an evolutionary process takes place: a new population of players is created from parent strategies that are selected based on fitness (number of points earned). The parents create offspring that are mutated copies of themselves: each child can have slightly different boldness and vengefulness numbers than its parent. If the population starts out with most players' vengefulness set to zero (e.g., no social norms), then defectors will come to dominate the population. Axelrod initially expected to find that norms would facilitate the evolution of cooperation in the population-that is, vengefulness would evolve to counter boldness.

However, it turned out that norms alone were not enough for cooperation to emerge reliably. In a second experiment, Axelrod added metanorms, in which there were punishers to punish the nonpunishers, if you know what I mean. Sort of like people in the supermarket who give me disapproving looks when I don't discipline my children for chasing each other up the aisles and colliding with innocent shoppers. In my case the metanorm usually works. Axelrod also found that metanorms did the trick-if punishers of nonpunishers were around, the nonpunishers evolved to be more likely to punish, and the punished defectors evolved to be more likely to cooperate. In Axelrod's words, "Meta-norms can promote and sustain cooperation in a population."

Adding Spatial Structure.

The second extension that I find particularly interesting is the work done by mathematical biologist Martin Nowak and collaborators on adding spatial structure to the Prisoner's Dilemma. In Axelrod's original simulations, there was no notion of s.p.a.ce-it was equally likely for any player to encounter any other player, with no sense of distance between players.

Nowak suspected that placing players on a spatial lattice, on which the notion of neighbor is well defined, would have a strong effect on the evolution of cooperation. With his postdoctoral mentor Robert May (whom I mentioned in chapter 2 in the context of the logistic map), Nowak performed computer simulations in which the players were placed in a two-dimensional array, and each player played only with its nearest neighbors. This is ill.u.s.trated in figure 14.4, which shows a five by five grid with one player at each site (Nowak and May's arrays were considerably larger). Each player has the simplest of strategies-it has no memory of previous turns; it either always cooperates or always defects.

The model runs in discrete time steps. At each time step, each player plays a single Prisoner's Dilemma game against each of its eight nearest neighbors (like a cellular automaton, the grid wraps around at the edges) and its eight resulting scores are summed. This is followed by a selection step in which each player is replaced by the highest scoring player in its neighborhood (possibly itself); no mutation is done.

The motivation for this work was biological. As stated by Nowak and May, "We believe that deterministically generated spatial structure within populations may often be crucial for the evolution of cooperation, whether it be among molecules, cells, or organisms."

Nowak and May experimented by running this model with different initial configurations of cooperate and defect players and by varying the values in the payoff matrix. They found that depending on these settings, the spatial patterns of cooperate and defect players can either oscillate or be "chaotically changing," in which both cooperators and defectors coexist indefinitely. These results contrast with results from the nonspatial multiplayer Prisoner's Dilemma, in which, in the absence of meta-norms as discussed above, defectors take over the population. In Nowak and May's spatial case, cooperators can persist indefinitely without any special additions to the game, such as norms or metanorms.

FIGURE 14.4. Ill.u.s.tration of a spatial Prisoner's Dilemma game. Each player interacts only with its nearest neighbors-e.g., player P13 plays against, and competes for selection against, only the players in its neighborhood (shaded).

Nowak and May believed that their result ill.u.s.trated a feature of the real world-i.e., the existence of spatial neighborhoods fosters cooperation. In a commentary on this work, biologist Karl Sigmund put it this way: "That territoriality favours cooperation... is likely to remain valid for real-life communities."

Prospects of Modeling.

Computer simulations of idea models such as the Prisoner's Dilemma, when done well, can be a powerful addition to experimental science and mathematical theory. Such models are sometimes the only available means of investigating complex systems when actual experiments are not feasible and when the math gets too hard, which is the case for almost all of the systems we are most interested in. The most significant contribution of idea models such as the Prisoner's Dilemma is to provide a first hand-hold on a phenomenon-such as the evolution of cooperation-for which we don't yet have precise scientific terminology and well-defined concepts.

The Prisoner's Dilemma models play all the roles I listed above for idea models in science (and a.n.a.logous contributions could be listed from many other complex-systems modeling efforts as well): Show that a proposed mechanism for a phenomenon is plausible or implausible. For example, the various Prisoner's Dilemma and related models have shown what Thomas Hobbes might not have believed: that it is indeed possible for cooperation-albeit in an idealized form-to come about in leaderless populations of self-interested (but adaptive) individuals.

Explore the effects of variations on a simple model and prime one's intuitions about a complex phenomenon. The endless list of Prisoner's Dilemma variations that people have studied has revealed much about the conditions under which cooperation can and cannot arise. You might ask, for example, what happens if, on occasion, people who want to cooperate make a mistake that accidentally signals noncooperation-an unfortunate mistranslation into Russian of a U.S. president's comments, for instance? The Prisoner's Dilemma gives an arena in which the effects of miscommunications can be explored. John Holland has likened such models to "flight simulators" for testing one's ideas and for improving one's intuitions.

Inspire new technologies. Results from the Prisoner's Dilemma modeling literature-namely, the conditions needed for cooperation to arise and persist-have been used in proposals for improving peer-to-peer networks and preventing fraud in electronic commerce, to name but two applications.

Lead to mathematical theories. Several people have used the results from Prisoner's Dilemma computer simulations to formulate general mathematical theories about the conditions needed for cooperation. A recent example is work by Martin Nowak, in a paper called "Five Rules for the Evolution of Cooperation."

How should results from idea models such as the Prisoner's Dilemma be used to inform policy decisions, such as the foreign relations strategies of governments or responses to global warming? The potential of idea models in predicting the results of different policies makes such models attractive, and, indeed, the influence of the Prisoner's Dilemma and related models among policy a.n.a.lysts has been considerable.

As one example, New Energy Finance, a consulting firm specializing in solutions for global warming, recently put out a report called "How to Save the Planet: Be Nice, Retaliatory, Forgiving, and Clear." The report argues that the problem of responding to climate change is best seen as a multi-player repeated Prisoner's Dilemma in which countries can either cooperate (mitigate carbon output at some cost to their economies) or defect (do nothing, saving money in the short term). The game is repeated year after year as new agreements and treaties regulating carbon emissions are forged. The report recommends specific policies that countries and global organizations should adopt in order to implement the "nice, retaliatory, forgiving, and clear" characteristics Axelrod cited as requirements for success in the repeated Prisoner's Dilemma.

Similarly, the results of the norms and metanorms models-namely, that not only norms but also metanorms can be important for sustaining cooperation-has had impact on policy-making research regarding government response to terrorism, arms control, and environmental governance policies, among other areas. The results of Nowak and May's spatial Prisoner's Dilemma models have informed people's thinking about the role of s.p.a.ce and locality in fostering cooperation in areas ranging from the maintenance of biodiversity to the effectiveness of bacteria in producing new antibiotics. (See the notes for details on these various impacts.)

Computer Modeling Caveats.

All models are wrong, but some are useful.

-George Box and Norman Draper.

Indeed, the models I described above are highly simplified but have been useful for advancing science and policy in many contexts. They have led to new insights, new ways of thinking about complex systems, better models, and better understanding of how to build useful models. However, some very ambitious claims have been made about the models' results and how they apply in the real world. Therefore, the right thing for scientists to do is to carefully scrutinize the models and ask how general their results actually are. The best way to do that is to try to replicate those results.

In an experimental science such as astronomy or chemistry, every important experiment is replicated, meaning that a different group of scientists does the same experiment from scratch to see whether they get the same results as the original group. No experimental result is (or should be) believed if no other group can replicate it in this way. The inability of others to replicate results has been the death knell for uncountable scientific claims.

Computer models also need to be replicated-that is, independent groups need to construct the proposed computer model from scratch and see whether it produces the same results as those originally reported. Axelrod, an out-spoken advocate of this idea, writes: "Replication is one of the hallmarks of c.u.mulative science. It is needed to confirm whether the claimed results of a given simulation are reliable in the sense that they can be reproduced by someone starting from scratch. Without this confirmation, it is possible that some published results are simply mistaken due to programming errors, misrepresentation of what was actually simulated, or errors in a.n.a.lyzing or reporting the results. Replication can also be useful for testing the robustness of inferences from models."

Fortunately, many researchers have taken this advice to heart and have attempted to replicate some of the more famous Prisoner's Dilemma simulations. Several interesting and sometimes unexpected results have come out of these attempts.

In 1995, Bernardo Huberman and Natalie Glance re-implemented Nowak and May's spatial Prisoner's Dilemma model. Huberman and Glance ran a simulation with only one change. In the original model, at each time step all games between players in the lattice were played simultaneously, followed by the simultaneous selection in all neighborhoods of the fittest neighborhood player. (This required Nowak and May to simulate parallelism on their nonparallel computer.) Huberman and Glance instead allowed some of the games to be played asynchronously-that is, some group of neighboring players would play games and carry out selection, then another group of neighboring players would do the same, and so on. They found that this simple change, arguably making the model more realistic, would typically result in complete replacement of cooperators by defectors over the entire lattice. A similar result was obtained independently by Arijit Mukherji, Vijay Rajan, and James Slagle, who in addition showed that cooperation would die out in the presence of small errors or cheating (e.g., a cooperator accidentally or purposefully defecting). Nowak, May, and their collaborator Sebastian Bonhoeffor replied that these changes did indeed lead to the extinction of all cooperators for some payoff-matrix values, but for others, cooperators were able to stay in the population, at least for long periods.

In 2005 Jose Manuel Galan and Luis Izquierdo published results of their re-implementation of Axelrod's Norms and Metanorms models. Given the increase in computer power over the twenty years that had pa.s.sed since Axelrod's work, they were able to run the simulation for a much longer period and do a more thorough investigation of the effects of varying certain model details, such as the payoff matrix values, the probabilities for mutating offspring, and so on. Their results matched well with Axelrod's for some aspects of the simulation, but for others, the re-implementation produced quite different results. For example, they found that whereas metanorms can facilitate the evolution and persistence of cooperation in the short term, if the simulation is run for a long time, defectors end up taking over the population. They also found that the results were quite sensitive to the details of the model, such as the specific payoff values used.

What should we make of all this? I think the message is exactly as Box and Draper put it in the quotation I gave above: all models are wrong in some way, but some are very useful for beginning to address highly complex systems. Independent replication can uncover the hidden unrealistic a.s.sumptions and sensitivity to parameters that are part of any idealized model. And of course the replications themselves should be replicated, and so on, as is done in experimental science. Finally, modelers need above all to emphasize the limitations of their models, so that the results of such models are not misinterpreted, taken too literally, or hyped too much. I have used examples of models related to the Prisoner's Dilemma to ill.u.s.trate all these points, but my previous discussion could be equally applied to nearly all other simplified models of complex systems.

I will give the last word to physicist (and ahead-of-his-time model-building proponent) Phillip Anderson, from his 1977 n.o.bel Prize acceptance speech: The art of model-building is the exclusion of real but irrelevant parts of the problem, and entails hazards for the builder and the reader. The builder may leave out something genuinely relevant; the reader, armed with too sophisticated an experimental probe or too accurate a computation, may take literally a schematized model whose main aim is to be a demonstration of possibility.

PART IV.

Network Thinking.

In Ersilia, to establish the relations.h.i.+ps that sustain the city's life, the inhabitants stretch strings from the corners of the houses, white or black or gray or black-and-white according to whether they mark a relations.h.i.+p of blood, of trade, authority, agency. When the strings become so numerous that you can no longer pa.s.s among them, the inhabitants leave: the houses are dismantled; only the strings and their supports remain.

From a mountainside, camping with their household goods, Ersilia's refugees look at the labyrinth of taut strings and poles that rise in the plain. That is the city of Ersilia still, and they are nothing.

They rebuild Ersilia elsewhere. They weave a similar pattern of strings which they would like to be more complex and at the same time more regular than the other. Then they abandon it and take themselves and their houses still farther away.

Thus, when traveling in the territory of Ersilia, you come upon the ruins of abandoned cities, without the walls which do not last, without the bones of the dead which the wind rolls away: spiderwebs of intricate relations.h.i.+ps seeking a form.

-Italo Calvino, Invisible Cities (Trans. W. Weaver).

CHAPTER 15.

The Science of Networks.

Small Worlds.

I live in Portland, Oregon, whose metro area is home to over two million people. I teach at Portland State University, which has close to 25,000 students and over 1,200 faculty members. A few years back, my family had recently moved into a new house, somewhat far from campus, and I was chatting with our new next-door neighbor, Dorothy, a lawyer. I mentioned that I taught at Portland State. She said, "I wonder if you know my father. His name is George Lendaris." I was amazed. George Lendaris is one of the three or four faculty members at PSU, including myself, who work on artificial intelligence. Just the day before, I had been in a meeting with him to discuss a grant proposal we were collaborating on. Small world!

Virtually all of us have had this kind of "small world" experience, many much more dramatic than mine. My husband's best friend from high school turns out to be the first cousin of the guy who wrote the artificial intelligence textbook I use in my cla.s.s. The woman who lived three houses away from mine in Santa Fe turned out to be a good friend of my high-school English teacher in Los Angeles. I'm sure you can think of several experiences of your own like this.

How is it that such unexpected connections seem to happen as often as they do? In the 1950s, a Harvard University psychologist named Stanley Milgram wanted to answer this question by determining, on average, how many links it would take to get from any person to any other person in the United States. He designed an experiment in which ordinary people would attempt to relay a letter to a distant stranger by giving the letter to an acquaintance, having the acquaintance give the letter to one of his or her acquaintances, and so on, until the intended recipient was reached at the end of the chain.

Milgram recruited (from newspaper ads) a group of "starters" in Kansas and Nebraska, and gave each the name, occupation, and home city of a "target," a person unknown to the starter, to whom the letter was addressed. Two examples of Milgram's chosen targets were a stockbroker in Boston and the wife of a divinity student in nearby Cambridge. The starters were instructed to pa.s.s on the letter to someone they knew personally, asking that person to continue the chain. Each link in the chain was recorded on the letter; if and when a letter reached the target, Milgram counted the number of links it went through. Milgram wrote of one example: Four days after the folders were sent to a group of starting persons in Kansas, an instructor at the Episcopal Theological Seminary approached our target person on the street. "Alice," he said, thrusting a brown folder toward her, "this is for you." At first she thought he was simply returning a folder that had gone astray and had never gotten out of Cambridge, but when we looked at the roster, we found to our pleased surprise that the doc.u.ment had started with a wheat farmer in Kansas. He had pa.s.sed it on to an Episcopalian minister in his home town, who sent it to the minister who taught in Cambridge, who gave it to the target person. Altogether, the number of intermediate links between starting person and target amounted to two!

In his most famous study, Milgram found that, for the letters that made it to their target, the median number of intermediate acquaintances from starter to target was five. This result was widely quoted and is the source of the popular notion that people are linked by only "six degrees of separation."

Later work by psychologist Judith Kleinfeld has shown that the popular interpretation of Milgram's work was rather skewed-in fact, most of the letters from starters never made it to their targets, and in other studies by Milgram, the median number of intermediates for letters that did reach the targets was higher than five. However, the idea of a small world linked by six degrees of separation has remained as what may be an urban myth of our culture. As Kleinfeld points out, When people experience an unexpected social connection, the event is likely to be vivid and salient in a person's memory .... We have a poor mathematical, as well as a poor intuitive understanding of the nature of coincidence.

Stanley Milgram, 19331984. (Photograph by Eric Kroll, reprinted by permission of Mrs. Alexandra Milgram.).

So is it a small world or not? This question has recently received a lot of attention, not only for humans in the social realm, but also for other kinds of networks, ranging from the networks of metabolic and genetic regulation inside living cells to the explosively growing World Wide Web. Over the last decade questions about such networks have sparked a stampede of complex systems researchers to create what has been called the "new science of networks."

The New Science of Networks.

You've no doubt seen diagrams of networks like the one in figure 15.1. This one happens to be a map of the domestic flight routes of Continental Airlines. The dots (or nodes) represent cities and the lines (or links) represent flights between cities.

Airline route maps are an obvious example of the many natural, technological, and cultural phenomena that can usefully be described as networks. The brain is a huge network of neurons linked by synapses. The control of genetic activity in a cell is due to a complex network of genes linked by regulatory proteins. Social communities are networks in which the nodes are people (or organizations of people) between whom there are many different types of possible relations.h.i.+ps. The Internet and the World Wide Web are of course two very prominent networks in today's society. In the realm of national security, much effort has been put into identifying and a.n.a.lyzing possible "terrorist networks."

FIGURE 15.1. Slightly simplified route map of Continental Airlines. (From NASA Virtual Skies: [http://virtualskies.arc.nasa.gov/research/tutorial/tutorial2b.html].) Until very recently, network science was not seen as a field unto itself. Mathematicians studied abstract network structures in a field called "graph theory." Neuroscientists studied neural networks. Epidemiologists studied the transmission of diseases through networks of interacting people. Sociologists and social psychologists such as Milgram were interested in the structure of human social networks. Economists studied the behavior of economic networks, such as the spread of technological innovation in networks of businesses. Airline executives studied networks like the one in figure 15.1 in order to find a node-link structure that would optimize profits given certain constraints. These different groups worked pretty much independently, generally unaware of one another's research.

However, over the last decade or so, a growing group of applied mathematicians and physicists have become interested in developing a set of unifying principles governing networks of any sort in nature, society, and technology. The seeds of this upsurge of interest in general networks were planted by the publication of two important papers in the late 1990s: "Collective Dynamics of 'Small World Networks' " by Duncan Watts and Steven Strogatz, and "Emergence of Scaling in Random Networks" by Albert-Laszlo Barabasi and Reka Albert. These papers were published in the world's two top scientific journals, Nature and Science, respectively, and almost immediately got a lot of people really excited about this "new" field. Discoveries about networks started coming fast and furiously.

Duncan Watts (photograph courtesy of Duncan Watts).

The time and place was right for people to jump on this network-science rus.h.i.+ng locomotive. A study of common properties of networks across disciplines is only feasible with computers fast enough to study networks empirically-both in simulation and with ma.s.sive amounts of real-world data. By the 1990s, such work was possible. Moreover, the rising popularity of using the Internet for social, business, and scientific networking meant that large amounts of data were rapidly becoming available.

In addition, there was a large coterie of very smart physicists who had lost interest in the increasingly abstract nature of modern physics and were looking for something else to do. Networks, with their combination of pristine mathematical properties, complex dynamics, and real-world relevance, were the perfect vehicle. As Duncan Watts (who is an applied mathematician and sociologist) phrased it, "No one descends with such fury and in so great a number as a pack of hungry physicists, adrenalized by the scent of a new problem." All these smart people were trained with just the right mathematical techniques, as well as the ability to simplify complex problems without losing their essential features. Several of these physicists-turned-network-scientists have become major players in this field.

Steven Strogatz (photograph courtesy of Steven Strogatz).

Albert-Laszlo Barabasi (photograph courtesy of Albert-Laszlo Barabasi).

Perhaps most important, there was, among many scientists, a progressive realization that new ideas, new approaches-really, a new way of thinking-were direly needed to help make sense of the highly complex, intricately connected systems that increasingly affect human life and well-being. Albert-Laszlo Barabasi, among others, has labeled the resulting new approaches "network thinking," and proclaimed that "network thinking is poised to invade all domains of human activity and most fields of human inquiry."