Three's company when seeking unanimity
- Faculty of Mathematics, University of Vienna, Nordbergstrasse 15, 1090 Vienna, Austria; and International Institute for Applied Systems Analysis, A-2361 Laxenburg, Austria
Random searches are routinely used in many algorithms, for instance, when looking for the shortest path connecting 100 cities or for ordering genomes in a most-parsimonious descendency tree. In this issue of PNAS, Matsen and Nowak (1) use a random search for another type of problem, that of finding coherence rather than optimality. The task thus consists of reaching unanimity. The proposed solution is outrageously simple: Keep switching until you agree with two others, then stop. Under a wide set of conditions, this slapdash recipe works.
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 …
