  The tendency to align to others is inherent to social behavior, including in
animal groups, and flocking in particular. Here we introduce the Stochastic
Alignment Problem, aiming to study basic algorithmic aspects that govern
alignment processes in unreliable stochastic environments. Consider n birds
that aim to maintain a cohesive direction of flight. In each round, each bird
receives a noisy measurement of the average direction of others in the group,
and consequently updates its orientation. Then, before the next round begins,
the orientation is perturbed by random drift (modelling, e.g., the affects of
wind). We assume that both noise in measurements and drift follow Gaussian
distributions. Upon receiving a measurement, what should be the orientation
adjustment policy of birds if their goal is to minimize the average (or
maximal) expected deviation of a bird's direction from the average direction?
We prove that a distributed weighted-average algorithm, termed W , that at each
round balances between the current orientation of a bird and the measurement it
receives, maximizes the social welfare. Interestingly, the optimality of this
simple distributed algorithm holds even assuming that birds can freely
communicate to share their gathered knowledge regarding their past and current
measurements. We find this result surprising since it can be shown that birds
other than a given i can collectively gather information that is relevant to
bird i, yet not processed by it when running a weighted-average algorithm.
Intuitively, it seems that optimality is nevertheless achieved, since, when
running W , the birds other than i somehow manage to collectively process the
aforementioned information in a way that benefits bird i, by turning the
average direction towards it. Finally, we also consider the game-theoretic
framework, proving that W is the only weighted-average algorithm that is at
Nash equilibrium.
