Imagine you are sitting in a room with a large number of people attending a conference and the organizers give you and all the other persons in the room a small piece of paper, asking each person to write down a number between 0 and 100. All the numbers will then be collected and a prize will be given to the person who will have written the closest number to half of the average of all the numbers. What number would you write on your piece of paper? Game theory [16] provides a powerful and elegant framework to predict the outcome of situations like the one described above. Intuitively speaking, in order to choose a number to write on her piece of paper, a person in the room could think as follows: Since numbers are constrained to be between 0 and 100, their average will be a number between 0 and 100 as well, so half of the average will be a number between 0 and 50; hence, if I am rational I would de nitely not write a number larger than 50. Now, if everyone in the room is rational and writes a number not larger than 50, then the average itself will be not larger than 50 and half of the average will be not larger than 25; so, if I am rational and I believe that all other people in the room are rational, I would not write a number larger than 25. If everyone writes a number not larger than 25, . . . A few more steps of reasoning along the above lines and we have the game theoretic prediction of the outcome: Every person in the room writes 0 on her piece of paper. This is indeed the unique Nash equilibrium [14] of that game. However, if you try it out in any real scenario, you will see by yourself how far from the truth is such a prediction. The main reason is that it relies on the very strong assumption that rationality is common knowledge [6] among the agents (everyone is rational, everyone knows that everyone is rational, everyone knows that everyone knows that everyone is rational, and so forth).
Several branches of game theory try to relax the rationality assumption in order
to get to more reliable predictions. For example, Evolutionary game theory [
A simple and elegant approach to model players with limited rationality in the
case of repeated games is the Logit dynamics, introduced in [
Once we model an evolving system of agents as an ergodic Markov chain, the
unique stationary distribution of the chain becomes a powerful solution concept
for the system, since it allows us to make predictions on its behavior in the
long run, regardless of the starting state. However, the strength of this solution
concept is also its weakness: The predictive appeal of the stationary distribution
essentially vanishes if the mixing time [
Metastability is a word that can have slightly di erent meanings in di
erent scienti c disciplines. Nevertheless, all the meanings are somehow related to
evolving systems hanging around \persistent" con gurations but out of their
main equilibrium. Our de nition in [
In [
Consider the following simple rules executed synchronously, in discrete rounds,
by the nodes of an undirected graph: Each node initially holds a value (say, a
rational number) and then, at each round, it updates its value to the average
of the values held by its neighbors. It comes as no surprise that, under mild
assumptions on the graph (namely, it has to be connected and non-bipartite) all
nodes will converge to the same value, in the long run. May be it is much less
obvious that, in its metastable regime, this simple dynamics can be e ectively
used to e ciently solve the community detection problem [
Let us consider a graph formed by two good expanders connected by a sparse cut. For the sake of concreteness and simplicity, let us assume we have a \very regular" graph G = (V; E) with an even number n of nodes partitioned in two blocks of equal size, V1 and V2, and that each node has exactly a neighbors in its own block and exactly b neighbors in the other block, for some positive integers a and b, with a b. Let 1 and 2 be the averages of the initial values of the nodes in V1 and V2, respectively. Intuitively speaking, by running the averaging dynamics on a graph like that the following happens: In a rst phase, the values of all nodes in V1 quickly converge to a value close to 1, while those of nodes in V2 to a value close to 2. After that initial phase, the system enters in a metastable regime in which all values slowly converge toward the global average ( 1 + 2)=2; if the two averages 1 and 2 are di erent, say 1 < 2, in this second phase the value of each node in V1 increases at every round and the value of each node in V2 decreases. Thus, if we augment the averaging dynamics with a \clustering criterion" asking each node to raise, at each round, a blue ag or a red ag depending on whether its value has increased or decreased from the last round, then as soon as the system enters the metastable regime, all nodes in one of the blocks raise the red ag and all nodes in the other block raise the blue one. We thus have a fully-distributed protocol that allows the nodes to perform a perfect reconstruction of the two clusters of the graph.
To make the intuitions in the above paragraph a bit more real, we can use some linear algebra: Let us name x(t) = (x(ut); u 2 V ) the vector where x(ut) is the value of node u at round t. It is easy to see that the averaging dynamics is de ned by the recursion x(t+1) = P x(t), where P = A=(a + b) and A is the adjacency matrix of the graph. The vector of values at round t is thus x(t) = P tx(0). Since P is a symmetric matrix with real entries, all its eigenvalues are real. Since P is stochastic (the entries of each row sum up to 1), all its eigenvalues are between 1 and 1 and vector 1 = (1; u 2 V ), i.e., the vector with all entries equal to 1, is an eigenvector with eigenvalue 1. Moreover, for our \very regular" graph G, the partition indicator vector = (1; u 2 V1; 1; u 2 V2), taking value +1 on all the nodes of one of the blocks and 1 on all the nodes of the other block, is also an eigenvector and its eigenvalue is (a b)=(a + b). Under the assumption a b, that formalizes the fact that the two blocks are internally well-connected with respect to the cut between them, (a b)=(a + b) is the second-largest eigenvalue, 2, of P . The vector of values at round t can thus be written as x(t) = 11 + 2 t2 + e(t), where 1 and 2 are suitable coe cients depending only on the initial values (namely, 1 is the global average ( 1 + 2)=2 of the initial values and 2 is half of the di erence of the initial averages ( 1 2)=2) and e(t) is a vector orthogonal to 1 and . When we consider the di erence between the vectors in two consecutive rounds, the component in the direction of 1 cancels, and what is left is x(t 1) x(t) = 2 t2 1(1 2) + e(t 1) e(t). Since e(t), for t = 0; 1; : : : , are vectors orthogonal to 1 and , the norm of e(t) goes to zero at least as fast as the third eigenvalue of P , t . Hence, if the 3 coe cient 2 is non-zero, after a number of rounds depending on 1=( 2 3) it holds that j 2 t2 1(1 2)j > je(t 1)(u) e(t)(u)j for all nodes u. This implies that, for each node u, the sign of x(ut 1) x(ut) is equal to the sign of 2 : In other words, it is positive for all the nodes in one of the blocks and negative for all the nodes in the other block. Finally, in order to ensure in a distributed way that 2 = ( 1 2)=2 is non-zero, we can use randomness : If each node chooses its initial value as +1 or 1 with probability 1=2, then the two initial averages di er for (1=pn) with high probability.
Evolving systems governed by simple local rules that produce observable global phenomena, can be fruitfully studied from a computational perspective. On the one hand, they seem suitable for modeling natural phenomena emerging in different elds (physics, economy, biology); on the other hand, they can be used as design principles and building blocks for lightweight distributed protocols for relevant computational tasks.
Randomness plays a fundamental role in this kind of processes, either in a Bayesian sense, to model the intrinsic uncertainty about the local rules executed by the agents of the system, or as a distributed symmetry-breaking tool.
The most interesting phenomena often cannot be studied by means of limiting behaviors and equilibria, because they appear at shorter time-scales, i.e., when systems are in their metastable phases.