  Social computation, whether in the form of searches performed by swarms of
agents or collective predictions of markets, often supplies remarkably good
solutions to complex problems. In many examples, individuals trying to solve a
problem locally can aggregate their information and work together to arrive at
a superior global solution. This suggests that there may be general principles
of information aggregation and coordination that can transcend particular
applications. Here we show that the general structure of this problem can be
cast in terms of information theory and derive mathematical conditions that
lead to optimal multi-agent searches. Specifically, we illustrate the problem
in terms of local search algorithms for autonomous agents looking for the
spatial location of a stochastic source. We explore the types of search
problems, defined in terms of the statistical properties of the source and the
nature of measurements at each agent, for which coordination among multiple
searchers yields an advantage beyond that gained by having the same number of
independent searchers. We show that effective coordination corresponds to
synergy and that ineffective coordination corresponds to independence as
defined using information theory. We classify explicit types of sources in
terms of their potential for synergy. We show that sources that emit
uncorrelated signals provide no opportunity for synergetic coordination while
sources that emit signals that are correlated in some way, do allow for strong
synergy between searchers. These general considerations are crucial for
designing optimal algorithms for particular search problems in real world
settings.
