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 definitely 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 [15] applies the game theoretic framework to repeated games in biological contexts and introduces new solution concepts (evolutionary stable strategies); Behavioral game theory [9] proposes a more experimental approach: Observe the behavior of real players and appropriately extend the theory to give explanation to the outcomes.

A simple and elegant approach to model players with limited rationality in the case of repeated games is the Logit dynamics, introduced in [8] and inspired by statistical mechanics: Starting from some initial strategy profile, at each round a player is selected uniformly at random and she updates her current strategy according to a probability distribution biased toward strategies promising higher payoffs. More formally, let n be the number of players, for i = 1, . . . , n let S i be the set of strategies for player i and let u i :

is the current profile of strategies and player i is selected for the update, then she will play strategy y ∈ S i with probability proportional to e βui(x−i,y) , where (x −i , y) is the vector obtained from x by replacing the i-th entry x i with y and β 0 is a parameter measuring the rationality level of the players (it is indeed easy to see that, for β = 0 players play one of their strategies uniformly at random, i.e., they have no rationality at all, while for β → ∞ players tend to best respond to the current strategies of the other players, i.e., they are fully rational ). Logit dynamics defines an ergodic Markov chain over the space of strategy profiles (more precisely, a family of ergodic Markov chains indexed by β) whose unique stationary distribution π β we proposed [5] as the equilibrium solution concept for the game. The "prediction" of such a solution concept is thus that, for any subset A ⊆ S 1 × • • • × S n of the state space, the fraction of times that the system spends in A is given by its stationary probability π β (A), in the long run. This is certainly a more rough prediction than that of a Nash equilibrium but it is likely much more realistic in several cases (as much as a statement like "The next economic crisis will happen in 2059" cannot be considered a serious prediction today, while a statement like "We should expect at least two global economic crises for each century" is certainly weaker but also much more credible while still containing some non-negligible information).

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 [13] (the time it takes the chain to get close to its stationary distribution, starting at an arbitrary state) is too long with respect to the time-scale we are interested in. In [2,3] we classified some classes of strategic games with respect to their Logit dynamics' mixing time, distinguishing between polynomial and exponential (in the number of players) mixing. For the games whose Logit dynamics has exponential mixing time, in order to be able to make predictions at polynomial time-scales, in [4] we introduced a generalization of the concept of stationary distribution for a Markov chain and we called it metastable probability distribution.

Metastability is a word that can have slightly different meanings in different scientific disciplines. Nevertheless, all the meanings are somehow related to evolving systems hanging around "persistent" configurations but out of their main equilibrium. Our definition in [4] is no exception: Roughly speaking, we define a probability distribution µ to be metastable for a Markov chain with transition matrix P , if µP is close (with respect to an appropriate distance function) to µ. Among all possible metastable distributions, the interesting ones are those quickly reached from some subset of the state space. As a simple example, consider the following process: Start with a sequence of n bits (x 1 . . . , x n ) ∈ {0, 1} n ; at each round pick one index i ∈ [n] uniformly at random and replace x i with either 0 or 1 with probability 1/2; stop when you reach either the sequence with all zeros 0 = (0, . . . , 0) or the sequence with all ones 1 = (1, . . . , 1). This is a lazy random walk on the hypercube (see, e.g., [10]) modified by making 0 and 1 absorbing states. Clearly, starting from any state x ∈ {0, 1} n , eventually the process will end up in one of the two absorbing states. However, for every initial state x = 0, 1, the process will run for an exponential number of rounds, in expectation, before being absorbed; can't we say anything on the distribution xP t at a shorter time-scale? Yes, indeed. It is easy to see that, after t = Θ(n log n) rounds, xP t will get close to the uniform distribution U ∼ {0, 1} n , and it will stay close to U for an exponential number of rounds.

In [4] we introduced and studied metastable probability distributions as solution concepts for strategic games. However, the usefulness of looking at the "metastable phase" of evolving systems goes beyond the domains of game theory and Markov chains. In the next section we briefly describe an example of a simple dynamics whose metastable phase analysis allowed us to solve an intriguing computational task in a distributed way [7].

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 effectively used to efficiently solve the community detection problem [12,11,1] in a fullydistributed way.

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, V 1 and V 2 , 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 V 1 and V 2 , respectively. Intuitively speaking, by running the averaging dynamics on a graph like that the following happens: In a first phase, the values of all nodes in V 1 quickly converge to a value close to µ 1 , while those of nodes in V 2 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 different, say µ 1 < µ 2 , in this second phase the value of each node in V 1 increases at every round and the value of each node in V 2 decreases. Thus, if we augment the averaging dynamics with a "clustering criterion" asking each node to raise, at each round, a blue flag or a red flag 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 flag 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 (t) u , u ∈ V ) the vector where x (t) u is the value of node u at round t. It is easy to see that the averaging dynamics is defined 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 t x (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 ∈ 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 ∈ V 1 ; −1, u ∈ V 2 ), 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

, where α 1 and α 2 are suitable coefficients 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 difference of the initial averages (µ 1 − µ 2 )/2) and e (t) is a vector orthogonal to 1 and χ. When we consider the difference 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 λ t−1 2 (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 3 . Hence, if the coefficient α 2 is non-zero, after a number of rounds depending on 1/(λ 2 − λ 3 ) it holds that |α 2 λ t−1 2 (1 − λ 2 )| > |e (t−1) (u) − e (t) (u)| for all nodes u. This implies that, for each node u, the sign of x

u 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 differ for Θ(1/ √ n) 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 fields (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.