Three's company when seeking unanimity

Searching a Majority

Imagine a platoon of paratroopers landing at night in a vast forest. They are scattered across the forest, and their first task is to unite. The plane that carried their means of communications is unaccountably lost. They have to grope for each other in the dark. Shouting is out of question, because the enemy might hear. How should they proceed? Look for their leader? The leader was on the plane that got lost. All soldiers are equal, and no distinction of rank will help them converge on one particular person.

The soldiers have to search not for one designated place or for one salient point, for instance, the tallest tree in the forest, but they have to search for each other. Moreover, their search ought not to take too long, lest the enemy counterattacks. In war, you have to be, as the confederate general Nathan Bedford Forrest used to say, “the firstest with the mostest.”

In the absence of any information, the soldiers have to engage in a random search. Such problems are usually described by means of a graph (2–4). The possible sites correspond to the vertices of the graph. Neighboring vertices are connected by edges. Soldiers move along the edges. It is so dark that they cannot mark the sites they have already visited or recognize edges they have used before. They are known, in a strange technical expression, as memoryless learners.

Barring exceptional cases, if the soldiers keep searching, they will sooner or later all come together by sheer luck. They should certainly not disperse again. Indeed, it is clear that the soldiers should stop searching as soon as they find themselves in a majority group and wait for the stragglers to come up. How large is the majority? Fifty percent of the total? Maybe the soldiers do not know the total. They should certainly stop searching when their group is large enough, because if they keep moving through the night they will scatter anew. When is the group large enough?

Matsen and Nowak (1) propose that the soldiers be given a simple order: Stop moving when you have found two buddies. Of course, this rule can fail. It could be that several groups of three or more soldiers form in the forest. In this case, union will not be achieved. But this happens only rarely. In most cases, the first group that happens to unite will remain the only group with more than two persons. The stragglers are more likely to reach it than to form another threesome. Thus there will be just one condensation kernel that grows and eventually absorbs the whole platoon.

The time to unite is essentially that for forming the initial cluster and is proportional to the square of the number of sites.

The recipe only works if the initial distribution is very sparse. If the wood were densely populated by paratroopers, they would soon have formed several groups of three and frozen. Thus the number of vertices should be much larger than the number of agents swarming over them. Also, the graph should be connected and fairly regular, meaning that the number of edges leading out from a vertex should not vary too much. If the forest, for instance, consisted of two separate patches, the soldiers could never unite, and if the two patches were only connected through one narrow alley, the rule would often fail; the soldiers would be more likely to form two distinct groups than to work their way in a random walk through the bottleneck. Matsen and Nowak (1) show that, under these conditions, the expected time to unite is essentially that for forming the initial cluster and is proportional to the square of the number of sites. The time for the stragglers to join the cluster is much smaller. For graphs that are very narrow, those that look like long ropes or rope ladders, for instance, the rule must be amended: Stop the search whenever you have met with three buddies rather than two.

Learning Coherence

The task of reaching coherence occurs frequently in biological contexts. Usually, signaling pathways are in place to allow for local coordination between cells or individuals (5). Birds use visual cues to move in a flock; social insects or amoeba lay tracks of scent, etc. The converse task, that of avoiding coherence, may also be of interest. According to the Red Queen hypothesis, the main reason for sex is to keep immune responses from becoming homogenous in a population, lest the pathogens adapt to a common target (6).

Coordination is relatively easy once a communication system is in place. But establishing the communication system in the first place is itself a coordination task that is considerably more difficult.

Matsen and Nowak (1) were led to their coherence learning model when trying to describe language acquisition. As with the paratroopers, the main task for the learners is to unite; there is little point in having a private language.

Coordinating communication systems before even having the means to communicate is a daunting task. The search for coherence takes place not in physical space but in an abstract space of possible grammars. Most people learn their language from their parents or from teachers, but there have been occasions when people from different origins were thrown together and had to reach understanding on their own (7). It turns out that adults in that case never manage anything better than some crude pidgin, a protolanguage lacking any grammar and allowing just the stringing together of two nouns. But their children develop pidgin into a creole, a full-blown language with a grammar of its own. How can they achieve linguistic coherence in the absence of a teacher? The rule suggested by Matsen and Nowak (1) is an attempt to explain such coherence.

Language-learning from peers, i.e., without role models, has become a stylized fact. Children from immigrants learn the new language not from their parents but from the other children in the neighborhood. Hard and fast evidence for the emergence of a new language in a peer group is scarce. According to unreliable reports, three rulers (Pharaoh Psamtik, Emperor Frederick II, and King James IV) have attempted the experiment of raising isolated groups of children by deaf and mute foster parents in ill-guided attempts to find out the true language of man (8). Strangely, a mirror image of such an experiment provides, today, the most convincing evidence for the emergence of a new grammar within a peer group. In this unintended experiment, not the foster parents but the children were deaf and mute. In 1979, Nicaraguan authorities planned to send such children to deaf schools to teach them to lip read. The attempt had little success, but the children developed, on their own, a new, grammatically sophisticated sign language that was eventually picked up by their teachers (9, 10, 11). Other examples for coherence learning in peer groups include the emergence of scientific jargon in a new discipline or the adoption of new expressions among school children.

Groping Through Cyberspace

The issue addressed by Matsen and Nowak (1) is not limited to traditional linguistics. The search for coherence is an essential aspect in the emergence of multiagent systems and distributed artificial intelligence. Massively parallel computing is turning into a key technology (12, 13). This development is fostered by the growth of the Internet as an open environment for software and by the spread of machine-independent reprogramming languages, such as Java. Millions of computers are connected with each other, often in haphazard ways, and are required to behave coherently in the absence of any global control. In multiagent systems, they engage in grid computing, distributed problem solving, information gathering, or collaboration in e-offices or e-science. The demands of these tasks lead to formidable coordination problems related to task control, initializing, or load sharing. These problems have to be solved by autonomous and often heterogeneous modules with limited viewpoints and by using decentralized data (14–16). The modules in multiagent systems must communicate in a peer-to-peer fashion and learn from each other the formats, languages, and protocols to use. Furthermore, they have to achieve software standardization on their own, without instructions from a higher level and through an undirected search in the space of all possible solutions.

What Matsen and Nowak (1) propose is a particularly simple type of reinforcement learning. As soon as the agents are satisfied, they terminate their random search. Economists know this behavior as “satisficing” (a term introduced by Nobel prize-winning economist Herbert Simon) (17, 18). Among agents having only a localized knowledge of the environment, searching for improvement can lead to costly detours and requires considerable cognitive effort. In critical situations, fire-fighters, emergency surgeons, or paratroopers do not engage in the luxury of weighing several alternatives: Each proceeds with the first feasible option that comes to his or her mind. For boundedly rational subjects, optimizing is often too costly, so satisficing remains the right way to proceed. The important thing, then, is to choose the right aspiration level, i.e., when to say that enough is enough. What is so surprising in the random search for coherence is how modest that aspiration level can be.