Manuel Förster
email: manuel.forster@malix.univ-paris1.fr

Michel Grabisch

Agnieszka Rusinowska

Ordered Weighted Averaging in Social Networks †

Keywords: JEL classification: C7, D7, D85 Social network, influence, convergence, speed of convergence, consensus, ordered weighted averaging operator, fuzzy linguistic quantifier

We study a stochastic model of influence where agents have yes-no inclinations on some issue, and opinions may change due to mutual influence among the agents. Each agent independently aggregates the opinions of the other agents and possibly herself. We study influence processes modelled by ordered weighted averaging operators. This allows to study situations where the influence process resembles a majority vote, which are not covered by the classical approach of weighted averaging aggregation. We provide an analysis of the speed of convergence and the probabilities of absorption by different terminal classes. We find a necessary and sufficient condition for convergence to consensus and characterize terminal states. Our results can also be used to understand more general situations, where ordered weighted averaging operators are only used to some extend. Furthermore, we apply our results to fuzzy linguistic quantifiers.

Introduction

In the present work we study an important and widespread phenomenon which affects many aspects of human life -the phenomenon of influence. Being undoubtedly present, e.g., in economic, social and political behaviors, influence frequently appears as a dynamic process. Since social networks play a crucial role in the formation of opinions and the diffusion of information, it is not surprising that numerous scientific works investigate different dynamic models of influence in social networks. In what follows we mention only some works related to this paper, and for an overview of the vast literature on influence we refer, e.g., to [START_REF] Jackson | Social and Economic Networks[END_REF].

The seminal model of opinion and consensus formation is due to [START_REF] Degroot | Reaching a consensus[END_REF], where the opinion of an agent is a number in [0, 1] and she aggregates the opinions (beliefs) of other agents through a weighted arithmetic mean. The interaction among agents is captured by the social influence matrix. Several scholars have analyzed the DeGroot framework and proposed different variations of it, in which the updating of opinions can vary in time and along circumstances. However, most of the influence models usually assume a convex combination as the way of aggregating opinions. [START_REF] Golub | Naïve learning in social networks and the wisdom of crowds[END_REF] examine convergence of the social influence matrix and reaching a consensus, and the speed of convergence of beliefs, among other things. [START_REF] Demarzo | Persuasion bias, social influence, and unidimensional opinions[END_REF] consider a model where an agent may place more or less weight on her own belief over time. Another framework related to the DeGroot model is presented in [START_REF] Asavathiratham | The influence model: A tractable representation for the dynamics of networked Markov chains[END_REF]. [START_REF] Büchel | The dynamics of continuous cultural traits in social networks[END_REF] introduce a generalization of the DeGroot model by studying the transmission of cultural traits from one generation to the next one. [START_REF] Büchel | Opinion dynamics under conformity[END_REF] analyze an influence model in which agents may misrepresent their opinion in a conforming or counter-conforming way. Calvó-Armengol and [START_REF] Calvó-Armengol | Like father, like son: social network externalities and parent-child correlation in behavior[END_REF] study an overlapping-generations model in which agents, that represent some dynasties forming a community, take yes-no actions.

Also [START_REF] López-Pintado | Diffusion in complex social networks[END_REF], 2010), and López-Pintado and Watts (2008) investigate influence networks and the role of social influence in determining distinct collective outcomes. Related works can also be found in articles by van den Brink and his co-authors, see, e.g., [START_REF] Van Den Brink | Measuring domination in directed networks[END_REF]; [START_REF] Borm | An iterative procedure for evaluating digraph competitions[END_REF]. A different approach to influence, i.e., a method based on simulations, is presented in [START_REF] Mäs | The diversity puzzle. ICS dissertation series[END_REF]. [START_REF] Morris | Contagion[END_REF] analyzes the phenomenon of contagion which occurs if an action can spread from a finite set of individuals to the whole population.

Another stream of related literature concerns models of Bayesian and observational learning where agents observe choices over time and update their beliefs accordingly, see, e.g., [START_REF] Banerjee | A simple model of herd behavior[END_REF], [START_REF] Ellison | Learning, local interaction, and coordination[END_REF], Bala andGoyal (1998, 2001), [START_REF] Gale | Bayesian learning in social networks[END_REF] and [START_REF] Banerjee | Word-of-mouth learning[END_REF]. A model of strategic influence is studied in [START_REF] Galeotti | Influencing the influencers: a theory of strategic diffusion[END_REF]. [START_REF] Mueller-Frank | A fixed point convergence theorem in Euclidean spaces and its application to non-Bayesian learning in social networks[END_REF] considers continuous aggregation functions with a special property called "constricting" and studies convergence applied to non-Bayesian learning in social networks. Grabisch andRusinowska (2010, 2011a) investigate a one-step deterministic model of influence, where agents have yes-no inclinations on a certain issue and their opinions may change due to mutual influence among the agents. [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] extend it to a dynamic stochastic model based on aggregation functions. Each agent independently aggregates the opinions of the other agents and possibly herself. Since any aggregation function is allowed when updating the opinions, the framework covers numerous existing models of opinion formation. The only restrictions come from the definition of an aggregation function, i.e., boundary conditions and nondecreasingness. The latter condition implies that only a kind of positive influence can be covered by the model. [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] provide a general analysis of convergence in the aggregation model and find all terminal classes and states.

In the present paper we study this influence model based on aggregation functions and continue the analysis done in [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF]. More precisely, we examine a particular way of aggregating the opinions and investigate influence processes modelled by ordered weighted averaging operators (ordered weighted averages), commonly called OWA operators and introduced in [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF]. Roughly speaking, OWA operators are similar to the ordinary weighted averages, with the essential difference that weights are not attached to agents, but to the ranks of the agents in the input vector. As a consequence, OWA operators are in general nonlinear, and include as particular cases the median, the minimum and the maximum, as well as the (unweighted) arithmetic mean. More importantly, OWA operators can model fuzzy linguistic quantifiers introduced in [START_REF] Zadeh | A computational approach to fuzzy quantifiers in natural language[END_REF], also called soft quantifiers. Typical examples of such quantifiers are expressions like "almost all", "most", "many" or "at least a few"; see [START_REF] Yager | The Ordered Weighted Averaging Operators[END_REF]. OWA operators have been widely applied, in particular, to multi-criteria decision-making. [START_REF] Jiang | Application of fuzzy measures in multicriteria evaluation in GIS[END_REF], for instance, apply OWA operators to geographical multi-criteria evaluation, and [START_REF] Malczewski | Exploring multicriteria decision strategies in GIS with linguistic quantifiers: A case study of residential quality evaluation[END_REF] present a fuzzy linguistic quantifier extension of OWA in geographical multi-criteria evaluation.

Using ordered weighted averages in (social) networks is quite new, although some scholars have already initiated such an application; see [START_REF] Cornelis | Ordered weighted averaging approaches for aggregating gradual trust and distrust[END_REF] who apply OWA operators to trust networks. To the best of our knowledge, ordered weighted averages have not been used in influence networks yet, although applying OWA operators to the analysis of influence has undoubtedly several advantages. In particular, it allows to study situations where the influence process resembles a majority vote, which are not covered by the classical (commonly used) approach of weighted averaging aggregation. By using OWA operators we can analyze situations in which only the number of agents that share the same opinion matters for the influence process. In other words, models in which all agents use OWA operators for aggregating opinions are anonymous. By applying our results on OWA operators to fuzzy linguistic quantifiers we can analyze soft majority and soft minority in voting. For instance, we can study situations in which an agent changes her opinion if "most" or "many" or "at least a few" of the agents say "yes".

In the face of such a high applicability of OWA operators, in the present paper we aim at providing a detailed analysis for aggregation models with these operators. Moreover, some new results on the general setup of [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] are delivered.

The main objectives of the paper and its theoretical results are the following:

-Analyzing the speed of convergence and the probabilities of absorption by different terminal classes in the general model (Propositions 1 and 2) and in anonymous models (Corollaries 1 and 2).

-Finding a necessary and sufficient condition for a coalition to be yesinfluential or no-influential (Proposition 4) in the model with OWA operators.

-Characterizing terminal states in the model with OWA operators (Proposition 5).

-Finding a necessary and sufficient condition for convergence to consensus in the model with OWA operators (Theorem 2, Corollary 4).

-Finding a sufficient condition for convergence to consensus in the model with OWA-decomposable aggregation functions, i.e., in more general situations where ordered weighted averaging operators are only used to some extent (Corollary 5).

-Finding a sufficient condition for convergence to consensus in a model where agents use regular quantifiers and some are allowed to deviate from such a quantifier (Proposition 6, Remark 3).

-Characterizing terminal states in a model where agents use regular quantifiers (Proposition 7).

We illustrate our results by considering several examples, e.g., the model of Confucian society, majority voting, and mass psychology (also called herding behavior). The remainder of the paper is organized as follows. In Section 2 we present the model and basic definitions. In Section 3 the speed of convergence and the absorption probabilities are studied. Section 4 concerns the convergence analysis in the aggregation model with OWA operators. In Section 5 we apply our results on ordered weighted averages to fuzzy linguistic quantifiers. Section 6 contains some concluding remarks. The longer proofs of some of our results are presented in the Appendix.

Model and Notation

Let N := {1, . . . , n}, n ≥ 2, be the set of agents that have to make a yes-no decision on some issue. Each agent i ∈ N has an initial opinion x i ∈ {0, 1} (called inclination) on the issue, where "yes" is coded as 1.1 During the influence process, agents may change their opinion due to mutual influence among the agents.

Definition 1 (Aggregation function). An n-place aggregation function is any mapping

A : [0, 1] n → [0, 1] satisfying (i) A(0, . . . , 0) = 0, A(1, . . . , 1) = 1 (boundary conditions) and (ii) if x ≤ x ′ then A(x) ≤ A(x ′ ) (nondecreasingness).
To each agent i we assign an aggregation function A i that determines the way she reacts to the opinions of the other agents and herself. Note that by using these functions we model positive influence only. Our aggregation model A = (A 1 , . . . , A n ) t is stochastic, the outcome of one step of influence for each agent is her probability to say "yes". The aggregation functions our paper is mainly concerned with are ordered weighted averaging operators or simply ordered weighted averages. This class of aggregation functions was first introduced by [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF].

Definition 2 (Ordered weighted average). We say that an n-place aggregation function A is an ordered weighted average A = OWA w with weight vector2 w, if

A(x) = n k=1 w k x (k) for all x ∈ [0, 1] n , where x (1) ≥ x (2) ≥ . . . ≥ x (n) are the ordered components of x.
Let us denote by 1 S the characteristic vector of S ⊆ N, i.e., (1 S ) j = 1 if j ∈ S and (1 S ) j = 0 otherwise. If 1 S represents the current opinions of the agents, then we say that the model is in state or coalition S. We sometimes denote a coalition S = {i, j, k} simply by ijk and its cardinality or size by s. The definition of an aggregation function ensures that the two consensus states -the yes-consensus {N} where all agents say "yes" and the no-consensus {∅} where all agents say "no" -are fixed points of the aggregation model A = (A 1 , . . . , A n ) t . We call them trivial terminal classes. In general, a terminal class is defined as follows:

Definition 3 (Terminal class). A terminal class is a collection of states C ⊆ 2 N that forms a strongly connected and closed component, i.e., for all S, T ∈ C, there exists a path3 from S to T and there is no path from S to T if S ∈ C, T / ∈ C.

We can decompose the state space into disjoint terminal classes -also called absorbing classes -C 1 , . . . , C l ⊆ 2 N , for some l ≥ 2, and a set of transient states

T = 2 N \( l k=1 C k ).
For convenience, we denote by C ∪ := l k=1 C k the set of all states within terminal classes. Let us now define the notion of an influential agent [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF].

Definition 4 (Influential agent). (i) An agent j ∈ N is yes-influential on i ∈ N if A i (1 {j} ) > 0. (ii) An agent j ∈ N is no-influential on i ∈ N if A i (1 N \{j} ) < 1.
The idea is that j is yes-(or no-)influential on i if j's opinion to say "yes" (or "no") matters for i in the sense that there is a positive probability that i follows the opinion that is solely held by j. Analogously to influential agents, we can define influential coalitions [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF].

Definition 5 (Influential coalition). (i) A nonempty coalition S ⊆ N is yes-influential on i ∈ N if A i (1 S ) > 0. It is minimal yes-influential if additionally A i (1 S ′ ) = 0 for all S ′ S. (ii) A nonempty coalition S ⊆ N is no-influential on i ∈ N if A i (1 N \S ) < 1. It is minimal no-influential if additionally A i (1 N \S ′ ) = 1 for all S ′ S.
Making the assumption that the probabilities of saying "yes" are independent among agents4 and only depend on the current state, we can represent our aggregation model by a time-homogeneous Markov chain with transition matrix B = (b S,T ) S,T ⊆N , where

b S,T = Π i∈T A i (1 S )Π i / ∈T (1 -A i (1 S )).
Note that for each coalition S ⊆ N, the transition probabilities to coalitions T ⊆ N are represented by a certain row of B. The m-th power of a matrix, e.g., B = (b S,T ) S,T ⊆N , is denoted by B m = (b S,T (m)) S,T ⊆N . Moreover, let {X k } k∈N be a homogeneous Markov chain and (Ω, F , P) a probability space corresponding to B, i.e.,

P(X k+1 = T |X k = S) = b S,T for all k ∈ N, S, T ⊆ N.
Note that this Markov chain is neither irreducible nor recurrent since it has at least two terminal classes -also called communication classes.

We first study the speed of convergence -also called time before absorption -of the influence process to terminal classes. Secondly, we investigate the probabilities of convergence to each of the consensus states and possibly other terminal classes -we call them absorption probabilities. We provide an analysis for the general setup of [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF] and for anonymous models, which particularly cover the case where all agents use ordered weighted averages. The concept of anonymity allows to reduce the computational demand a lot in many situations.

Before we study the convergence to terminal classes, we have a look at the possible types of these classes. Grabisch and Rusinowska show that there are three different types of terminal classes in the general model.

Theorem 1 [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF]. In an aggregation model with aggregation functions A 1 , . . . , A n , terminal classes are

(i) either singletons {S}, S ⊆ N, (ii) cycles of nonempty sets {S 1 , . . . , S k } of any length 2 ≤ k ≤ n
⌊n/2⌋ (and therefore they are periodic of period k) with the condition that all sets are pairwise incomparable (by inclusion) or (iii) collections R of nonempty sets with the property that

R = R 1 ∪• • •∪R p ,
where each subcollection R j is an interval {S ∈ 2 N | S j ⊆ S ⊆ S j ∪K j }, with S j = ∅, S j ∪ K j = N, and at least one K j is nonempty.

To terminal classes of the first type we usually refer to as terminal states, to the second type as cyclic terminal classes and to the last type as regular terminal classes.

Suppose that B is obtained from an aggregation model A 1 , . . . , A n and that there is at least one transient state, i.e., T = ∅. We assume that the process starts from one of these states, that is, we take some S ∈ T as the initial coalition. Note that since the set of transient states is finite, we have convergence to the terminal classes almost surely. We say that the influence process B converges to the terminal classes after m steps of influence if {X m-1 ∈ T , X m / ∈ T }. Thus, the speed of convergence is the time it takes for the process to leave the set of transient states. 5 To measure it, we use stopping times and rely on results provided in [START_REF] Brémaud | Markov Chains[END_REF]. Let τ S be a stopping time such that {τ S = m} if we have convergence to the terminal classes after m steps of influence when S is the initial coalition, i.e.,

{τ S = m} = {X m / ∈ T , X m-1 ∈ T |X 0 = S}.
Our aim is to determine the distribution of the speed of convergence, given by the distribution of τ S . It turns out that the latter is solely determined by the transition probabilities within the set of transient states.

Proposition 1. Suppose B is obtained from an aggregation model with aggregation functions A 1 , . . . , A n . If S ∈ T is the initial coalition, then

P(τ S > m) = T ∈T q S,T (m), where Q = B| T . Furthermore, E[τ S ] = ∞ m=0 T ∈T q S,T (m) < +∞.
Proof. The first part follows from [START_REF] Brémaud | Markov Chains[END_REF]. For the expected value of τ S , first note that it only takes nonnegative integer values. The first equality of the following computation follows from this fact, whereas the third equality and the inequality follow since T is finite and Proposition 2. Suppose B is obtained from an aggregation model with aggregation functions A 1 , . . . , A n . If S ∈ T is the initial coalition, then we get for the absorption probabilities:

Q is strictly sub-stochastic, i.e., ∞ m=0 Q m < +∞. 6 E[τ S ] = ∞ m=0 P(τ S > m) = ∞ m=0 T ∈T q S,T (m) = T ∈T ∞ m=0 q S,T (m) < +∞.
P(τ k S < ∞) = g S, C k , for k = 1, . . . , l, where (g S,C ) S∈T ,C∈{ C 1 ,..., C l } := F D.
This completes the analysis of the general case. Let us now turn to anonymous models.

Definition 6 (Anonymity). (i) We say that an n-place aggregation function A is anonymous if for all x ∈ [0, 1] n and any permutation σ :

N → N, A(x 1 , . . . , x n ) = A(x σ(1) , . . . , x σ(n) ).
(ii) Suppose B is obtained from an aggregation model with aggregation functions A 1 , . . . , A n . We say that the model is anonymous if for all s, t ∈ {0, 1, . . . , n},

T ⊆N: |T |=t b S,T = T ⊆N:
|T |=t b S ′ ,T for all S, S ′ ⊆ N of size s.

For an agent using an anonymous aggregation function, only the size of the current coalition matters. Similarly, in models that satisfy anonymity, only the size of the current coalition matters for the further influence process.

Proposition 3. An aggregation model with anonymous aggregation functions

A 1 , . . . , A n is anonymous.

Note that the converse does not hold, a model can be anonymous although not all agents use anonymous aggregation functions. Anonymous models are particularly interesting since ordered weighted averages are anonymous and hence also models where agents use them.

Remark 1. Aggregation models with aggregation functions

A i = OWA w i , i ∈ N, are anonymous.
Assume now that the aggregation model is anonymous. Then, we can reduce the 2 n × 2 n transition matrix B to an (n + 1) × (n + 1) matrix B a = (b a s,t ) s,t∈{0,1,...,n} , where b a s,t := T ⊆N:

|T |=t b S,T , for any S ⊆ N of size s, are the transition probabilities from coalitions of size s to coalitions of size t. However, note that the gain in computational tractability -the dimensions of the transition matrix grow only linearly instead of exponentially with the number of agents -comes at the cost of losing track of the transition probabilities to certain states. We define an anonymous terminal class as C a := {s ∈ {0, 1, . . . , n}|∃ S ∈ C such that |S| = s}. Similarly, we define T a := {s ∈ {0, 1, . . . , n}|S ∈ T if |S| = s} and use a stopping time τ s when the initial coalition is of size s ∈ T a . Otherwise the notation carries over straightforwardly from the general case. Note that anonymous terminal classes are extended by states of the same size as states within the original class. This comes without loss of generality regarding absorption probabilities: if the influence process is in a state that was not part of the original class, it will converge to that class immediately due to anonymity. This also justifies not considering such states as possible initial states. However, the speed of convergence will be distorted in case it is possible that the process arrives at a state which is only part of the anonymous terminal class and not of the original class. We call such a model distorted. In this case, we need to use the original model to compute the speed of convergence. Models that only have singleton terminal classes are not distorted, though.

Corollary 1. Suppose B a is obtained from an anonymous aggregation model with aggregation functions A 1 , . . . , A n that is not distorted. If s ∈ T a is the size of the initial coalition, then

P(τ s > m) = t∈T a q a s,t (m) and E[τ s ] = ∞ m=0 t∈T a q a s,t (m) < +∞.
As already said, the result on absorption probabilities for anonymous models is straightforward.

Corollary 2. Suppose B a is obtained from an anonymous aggregation model with aggregation functions A 1 , . . . , A n . If s ∈ T a is the size of the initial coalition, then we get for the absorption probabilities:

P(τ k s < ∞) = g a s, C a k , for k = 1, . . . , l.
The initial coalition S ∈ T (or its size s) in the results above can as well be seen as a coalition (or its size) at some stage of the influence process before entering a terminal class. This finishes our analysis of the speed of convergence and absorption probabilities.8 To illustrate the results, let us consider the model of a Confucian society studied by [START_REF] Hu | On authority distributions in organizations: equilibrium[END_REF] and Grabisch and Rusinowska (2011a).

Example 1 (Confucian society). Consider a four member Confucian society N = {1, 2, 3, 4} that consists of the king (agent 1), the man (2), the wife (3) and the child (4). There are three principles in the decision-making process:

(i) The man follows the king;

(ii) the wife and the child follow the man;

(iii) the king should respect his people.

From the principles (i) and (ii), we get the following aggregation model:

Conf 2 (x) = x 1 , Conf 3 (x) = Conf 4 (x) = x 2 .
We can interpret the principle (iii) in different ways. If the inclination of the king is "yes", then his decision could be "yes" if either (a) at least one of his people has the inclination to say "yes", (b) at least two of his people have the inclination to say "yes" (majority) or (c) all of his people have the inclination to say "yes" (unanimity).

If his inclination is "no", then he could change his opinion and say "yes" if either (a) at least two of his people have the inclination to say "yes" (majority), (b) all of his people have the inclination to say "yes" (unanimity) or he could (c) stick to his inclination and say "no".

We consider a stochastic version where in each case the king chooses one of the three interpretations with equal probability. This leads to the following aggregation function of the king:

Conf 1 (x) = 1 3 (x (2) + x (3) + x (4) ).
The king is yes-and no-influential on the man, and so is the man on the wife and the child. Moreover, coalitions of size two or more are yes-and no-influential and all agents are no-influential on the king. This model corresponds to the following digraph of the Markov chain: Note that there are only the trivial terminal classes and that the model does not satisfy anonymity. 9 The convergence to the terminal classes is immediate if initially only the wife or the child said "yes". We also see that the convergence is rather fast if initially only the king, only the man or both the wife and the child said "yes". It is slow if initially only the king or the man said "no". If initially only one agent or both the wife and the child said "yes", then there is convergence to the no-consensus for sure. For most coalitions, it is much more likely to reach the no-consensus. Only if initially at least the king and the man said "yes", there is a high probability to reach the yes-consensus. These findings reflect the intuition that the king and the man are somehow more powerful than the wife and the child in the Confucian society (see Table 1).

Convergence and Ordered Weighted Averages

In aggregation models where the influence process is determined by ordered weighted averages, it could be that the agents finally reach a consensus for sure. Or it could as well be possible to end in some other terminal class, e.g., 9 Both can be easily seen from the digraph. For anonymity, it is enough to observe that the probabilities to reach the no-consensus are different for coalitions {1} and {3}. a state where the society is split up. Our aim is to investigate conditions for these outcomes. We also relax our setup and study the case where agents use ordered weighted averages only to some extend. As we already know, models where agents use ordered weighted averages are anonymous. In particular, this means that whether a yes-or no-consensus (or none of them) is finally reached does not depend on which agents initially said "yes", it just depends on how many did so. To give some intuition, let us consider a simple example presented in [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF], where the influence process resembles a majority voting.

Example 2 (Majority). A straightforward way of making a decision is based on majority voting. If the majority of the agents says "yes", then all agents agree to say "yes" after mutual influence and otherwise, they agree to say "no". We can model simple majorities as well as situations where far more than half of the agents are needed to reach the yes-consensus. Let m ∈ {⌊ n 2 ⌋ + 1, . . . , n}. Then, the majority aggregation model is given by

Maj [m] i (x) := x (m) for all i ∈ N.
All agents use an ordered weighted average where w m = 1. Obviously, the convergence to consensus is immediate.

Not surprisingly, the influence of a coalition indeed solely depends on the number of individuals involved.

Proposition 4. Consider an aggregation model with aggregation functions

A i = OWA w i , i ∈ N. (i) A coalition of size 0 < s ≤ n is yes-influential on i ∈ N if and only if min{k ∈ N|w i k > 0} ≤ s. It

is minimal yes-influential on i if and only if equality holds. (ii) A coalition of size

0 < s ≤ n is no-influential on i ∈ N if and only if max{k ∈ N|w i k > 0} ≥ n + 1 -s. It

is minimal no-influential on i if and only if equality holds.

Proof. Let S ⊆ N have size 0 < s ≤ n and be yes-influential on i ∈ N, i.e.,

A i (1 S ) = s k=1 w i k > 0 ⇔ min{k ∈ N|w i k > 0} ≤ s.
Suppose moreover that S is minimal yes-influential on i, i.e.,

A i (1 S ) = s k=1 w i k > 0 and A i (1 S ′ ) = s ′ k=1 w i k = 0 for all S ′ S ⇔ min{k ∈ N|w i k > 0} = s.
The second part is analogous.

The result on influential agents follows immediately.

Corollary 3. Consider an aggregation model with aggregation functions

A i = OWA w i , i ∈ N.
(i) All agents j ∈ N are yes-influential on i ∈ N if and only if w i 1 > 0.

(ii) All agents j ∈ N are no-influential on i ∈ N if and only if w i n > 0.

16 Documents de Travail du Centre d'Economie de la Sorbonne -2012.56

Note that this means that either all agents are yes-(or no-)influential on some agent i ∈ N or none. Next, we study non-trivial terminal classes. We characterize terminal states and show that there cannot be a cycle.

Proposition 5. Consider an aggregation model with aggregation functions

A i = OWA w i , i ∈ N.
(i) A state S ⊆ N of size s is a terminal state if and only if s k=1 w i k = 1 for all i ∈ S and s k=1 w i k = 0 otherwise.

(ii) There does not exist any cycle.

Proof. The first part is obvious. For the second part, assume that there is a cycle {S 1 , . . . , S k } of length 2 ≤ k ≤ n ⌊n/2⌋ . This implies that there exists l ∈ {1, . . . , k} such that s l ≤ s l+1 , where S k+1 ≡ S 1 . Thus,

s l j=1 w i j = 1 for all i ∈ S l+1
and hence S l+1 ⊆ S l+2 , which is a contradiction to pairwise incomparability by inclusion (see Theorem 1 (ii)).

For regular terminal classes, note that an agent i ∈ N such that w i 1 = 1 blocks a no-consensus and an agent j ∈ N such that w j n = 1 blocks a yesconsensus -given that the process has not yet arrived at a consensus. Therefore, since there cannot be any cycle, these two conditions, while ensuring that there is no other terminal state, gives us a regular terminal class.

Example 3 (Regular terminal class). Consider an aggregation model with aggregation functions

A i = OWA w i , i ∈ N = {1, 2, 3}.
Let agent 1 block a no-consensus and agent 3 block a yes-consensus, i.e., w

1 1 = w 3 3 = 1. Furthermore, choose w 2 1 = w 2 3 = 1 2 . Then {{1}, {1, 2}} is a regular terminal class. We have A(1 {1} ) = A(1 {1,2} ) = (1 1 2 0) t .
It is left to find conditions that avoid both non-trivial terminal states and regular terminal classes and hence ensure that the society ends up in a consensus. The following result characterizes the non-existence of non-trivial terminal classes. The idea is that for reaching a consensus, there must be some threshold such that whenever the size of the coalition is at least equal to this threshold, there is some probability that after mutual influence, more people will say "yes". And whenever the size is below this threshold, there is some probability that after mutual influence, more people will say "no".

Theorem 2. Consider an aggregation model with aggregation functions A i = OWA w i , i ∈ N. Then, there are no other terminal classes than the trivial terminal classes if and only if there exists k ∈ {1, . . . , n} such that both: (i) For all k = k, . . . , n -1, there are distinct agents i 1 , . . . , i k+1 ∈ N such that k j=1 w i l j > 0 for all l = 1, . . . , k + 1.

(ii) For all k = 1, . . . , k -1, there are distinct agents i 1 , . . . , i n-k+1 ∈ N such that

k j=1 w i l j < 1 for all l = 1, . . . , n -k + 1.
The proof is in the appendix. Note that Theorem 2 implies a straightforward -but very strict -sufficient condition:

Remark 2. Consider an aggregation model with aggregation functions A i = OWA w i , i ∈ N. Then, there are no other terminal classes than the trivial terminal classes if w i 1 > 0 for all i ∈ N ( k = 1), or w i n > 0 for all i ∈ N ( k = n).

We get a more intuitive formulation of Theorem 2 by using influential coalitions.

Corollary 4. Consider an aggregation model with aggregation functions

A i = OWA w i , i ∈ N.
Then, there are no other terminal classes than the trivial terminal classes if and only if there exists k ∈ {1, . . . , n} such that both: (i) For all k = k, . . . , n -1, there are k + 1 distinct agents such that coalitions of size k are yes-influential on each of them.

(ii) For all k = 1, . . . , k -1, there are nk + 1 distinct agents such that coalitions of size nk are no-influential on each of them.

In more general situations, the agents' behavior might only partly be determined by ordered weighted averages.

Definition 7 (OWA-decomposable aggregation function). We say that an n-place aggregation function A is OWA w -decomposable, if there exists λ ∈ (0, 1] and an n-place aggregation function

A ′ such that A = λOWA w + (1 -λ)A ′ .
Such aggregation functions do exist since convex combinations of aggregation functions are again aggregation functions. Note that a model where agents use these functions is not anonymous in general, though. However, the sufficiency part of Theorem 2 also holds if agents use such decomposable aggregation functions.10 Corollary 5. Consider an aggregation model with OWA w i -decomposable aggregation functions A i , i ∈ N. Then, there are no other terminal classes than the trivial terminal classes if there exists k ∈ {1, . . . , n} such that both: (i) For all k = k, . . . , n -1, there are distinct agents i 1 , . . . , i k+1 ∈ N such that k j=1 w i l j > 0 for all l = 1, . . . , k + 1.

(ii) For all k = 1, . . . , k -1, there are distinct agents i 1 , . . . , i n-k+1 ∈ N such that k j=1 w i l j < 1 for all l = 1, . . . , nk + 1.

To illustrate this result, we consider the phenomenon of mass psychology, also called herding behavior, given in [START_REF] Grabisch | A model of influence based on aggregation functions[END_REF].

Example 4 (Mass psychology). Mass psychology or herding behavior means that if at least a certain number m ∈ {⌊ n 2 ⌋ + 1, . . . , n} of agents share the same opinion, then these agents attract others, who had a different opinion before. We assume that an agent changes her opinion in this case with probability λ ∈ (0, 1]. In particular, we consider n = 3 agents and a threshold of m = 2. This means whenever only two agents are of the same opinion, the third one might change her opinion. This corresponds to the following mass psychology aggregation model:

Mass [2] i (x) = λx (2) + (1 -λ)x i for all i ∈ N.
This aggregation function is OWA w -decomposable, with w 2 = 1 and by Corollary 5, taking k = 2, the group eventually reaches a consensus. Furthermore, agents are yes-and no-influential on themselves and coalitions of size two or more are yes-and no-influential on all agents. The model gives the following digraph of the Markov chain:

∅ 1 2 3 12 13 23 N λ 1 -λ λ 1 -λ λ 1 -λ 1 -λ λ 1 -λ λ 1 -λ λ
Although the aggregation functions are not anonymous, the model is so. We get for any initial coalition of size 1 ≤ s ≤ 2:

P(τ s > m) = (1 -λ) m and E[τ s ] = 1 λ .
So, the speed of convergence hinges on λ, the probability that an agent follows the herd. If it is small, the process can take a long time. If initially two agents said "yes", the process terminates in the yes-consensus and otherwise, it terminates in the no-consensus. This example shows that OWA-decomposable aggregation functions allow -differently from ordered weighted averages -to account for the own opinion of an agent.

Applications to fuzzy linguistic quantifiers

Instead of being sharp edged, the threshold of an agent initially saying "no" for changing her opinion might be rather "soft". For instance, she could change her opinion if "most of the agents say 'yes' ". This is called a soft majority and phrases like "most" or "many" are so-called fuzzy linguistic quantifiers. Furthermore, soft minorities are also possible, e.g., "at least a few of the agents say 'yes' ". Our aim is to apply our findings on ordered weighted averages to fuzzy linguistic quantifiers. Mathematically, we define them by a function which maps the agents' proportion that says "yes" to the degree to which the quantifier is satisfied. 11

Definition 8 (Fuzzy linguistic quantifier). A fuzzy linguistic quantifier Q is defined by a nondecreasing function

µ Q : [0, 1] → [0, 1] such that µ Q (0) = 0 and µ Q (1) = 1.
Furthermore, we say that the quantifier is regular if the function is strictly increasing on some interval (c, c) ⊆ [0, 1] and otherwise constant.

Fuzzy linguistic quantifiers like "most" are ambiguous in the sense that it is not clear how to define them exactly mathematically. For example, one could well discuss which proportion of the agents should say "yes" for the quantifier "most" to be fully satisfied. Nevertheless, let us give some typical examples. 12 Example 5 (Typical quantifiers). We define (iv) Q af = "at least a few" by

(i) Q aa = "almost all" by µ Qaa (x) :=    1, if x ≥ 9 10 5 2 x -5 4 , if 1 2 < x < 9 10 0, otherwise , (ii) Q mo = "most" by µ Qmo (x) :=    1, if x ≥ 4 5 5 2 x -1, if 2 5 < x < 4 5 0, otherwise , (iii) Q ma = "many" by µ Qma (x) :=    1, if x ≥ 3 5 5 2 x -1 2 , if 1 5 < x < 3
µ Q af (x) := 1, if x ≥ 3 10 10 3 x, otherwise .
Note that these quantifiers are regular. For every quantifier, there exists a corresponding ordered weighted average in the sense that it represents the quantifier. 13 We can find its weights as follows.

Lemma 1 [START_REF] Yager | On ordered weighted averaging aggregation operators in multicriteria decisionmaking[END_REF]. Let Q be a fuzzy linguistic quantifier defined by µ Q . Then, the weights of its corresponding ordered weighted average OWA Q are given by

w k = µ Q k n -µ Q k -1 n , for k = 1, . . . , n.
This allows us to apply our results to regular quantifiers. We find that if all agents use such a quantifier, then under some similarity condition, the group will finally reach a consensus. Moreover, we show that the result still holds if some agents deviate to a quantifier that is not similar in that sense. In the following, we denote the quantifier of an agent i by Q i . (iii) Suppose min i∈N c i > 0 and max i∈N ci < 1, then the result in part (i) of the Proposition still holds if k < ⌈min p cp n⌉ agents i p 1 , . . . , , i p k deviate to regular quantifiers Q p and k ′ < ⌈(1max q c q )n⌉ agents i q 1 , . . . , i q k ′ deviate to regular quantifiers Q q such that cp < min i∈N c i and c q > max i∈N ci for all p = p 1 , . . . , p k and q = q 1 , . . . , q k ′ .

Proposition 6. Consider an aggregation model with aggregation functions

A i = OWA Q i , i ∈ N. (i) If Q i is regular for all i ∈ N and ∩ i∈N (c i , ci ) = ∅,
We can also characterize terminal states in a model where agents use regular quantifiers.

Proposition 7. Consider an aggregation model with aggregation functions

A i = OWA Q i , i ∈ N. If Q i is regular for all i ∈ N,
w i k = 0 otherwise ⇔µ Q i (s/n) = 1 for all i ∈ S and µ Q i (s/n) = 0 otherwise ⇔ max i∈S ci ≤ s n ≤ min i∈N \S c i .
To provide some intuition, let us come back to Example 5 and look at the implications our findings have on the quantifiers defined therein.

Example 5 (Typical quantifiers, continued). Consider an aggregation model with aggregation functions

A i = OWA Q i , i ∈ N. (i) If Q i ∈ {Q aa , Q mo , Q ma } for all i ∈ N,
or Q mo . (iii) A state S ⊆ N of size s is a terminal state if Q i = Q af for all i ∈ S, Q i = Q aa (Q i ∈ {Q aa , Q mo }) otherwise and 3 10 ≤ s n ≤ 1 2 (≤ 2 5 ).
It is left to provide concrete examples where agents use these quantifiers. We give an example where agents finally reach a consensus as well as one where this might not be the case.

Example 6 (Typical quantifiers in a four-agents-society). Consider an aggregation model with aggregation functions

A i = OWA Q i , i ∈ N = {1, 2, 3, 4}.
(i) Let each quantifier that we introduced be used by one agent, i.e.,

Q 1 = Q aa , Q 2 = Q mo , Q 3 = Q ma and Q 4 = Q af .
By Example 5 (i), there are only the trivial terminal classes. If initially only one or two agents said "yes", the convergence can take quite long since the first two agents are likely to hold a different opinion than the fourth agent after mutual influence. However, we see that the group tends to converge to the yes-consensus for most initial coalitions. This is because the "at least a few" quantifier kind of blocks the no-consensus (see Table 2).

(ii) Let two agents use the "almost all" quantifier and the other two the "at least a few" quantifier, i.e.,

Q 1 = Q 2 = Q aa and Q 3 = Q 4 = Q af .
By Example 5 (iii), S = {3, 4} is a terminal state, where the last two agents say "yes" and the others say "no". If initially only one agent said "yes", it is very likely that the society is split up eventually. If instead three agents said "yes", the group tends to converge to the yesconsensus. Overall, the convergence is fast (see We chose only the two extreme quantifiers in the second part because otherwise the group would reach a consensus although the condition in Example 5 (i) was violated. The reason is that the number of agents is small in the Example, the conditions on the deviating agents in Proposition 6 somehow get "closer to necessity" when n increases. In other words, reaching a consensus seems to be easier in our model for smaller groups.

Conclusion

We study a stochastic model of influence where agents aggregate opinions using ordered weighted averaging operators. These models are anonymous in the sense that only the number of agents sharing the same opinion matters. We analyse the speed of convergence to terminal classes as well as absorption probabilities of different classes. For anonymous models and in particular our setup, the computational demand is much lower than for general aggregation models. We show that cyclic terminal classes cannot exist and characterize terminal states. We provide a necessary and sufficient condition for convergence to consensus. It turns out that this is a condition on the influence that coalitions have on agents. We also extend our model to more general situations, where influence is determined by convex combinations of ordered weighted averages and general aggregation functions. Our previous condition is still sufficient for convergence to consensus in this generalized setting. Furthermore, we apply our results to fuzzy linguistic quantifiers and show that if agents use similar quantifiers and not too many agents deviate, the society will eventually reach a consensus.

A Appendix

A.1 Proof of Theorem 2 First, suppose that there exists k ∈ {1, . . . , n} such that (i) and (ii) hold. Let us take any coalition S N of size s ≥ k and show that it is possible to reach the yes-consensus, which implies that S is not part of a terminal class. By choice of S, it is sufficient to show that there is a positive probability that after mutual influence, the size of the coalition has strictly increased. That is, it is sufficient to show that there exists a coalition S ′ ⊆ N of size s ′ > s, such that A i (1 S ) > 0 for all agents i ∈ S ′ . Set k := s, then by condition (i), there are distinct agents i 1 , . . . , i k+1 ∈ N such that

A i l (1 S ) = k j=1 w i l j > 0 for all l = 1, . . . , k + 1,
i.e., setting S ′ := {i 1 , . . . , i k+1 } finishes this part. Analogously, we can show by condition (ii) that for any nonempty S ⊆ N of size s < k it is possible to reach the no-consensus. Hence, there are only the trivial terminal classes. Now, suppose to the contrary that for all k ∈ {1, . . . , n} either (i) or (ii) does not hold. Note that in order to establish that there exists a non-trivial terminal class, it is sufficient to show that there are k * , k * ∈ {1, . . . , n -1}, k * ≤ k * , such that for all S ⊆ N of size s = k * ,

A i (1 S ) < 1 for at most n -k * distinct agents i ∈ N (C * [k * ])
and for all S ⊆ N of size s = k * ,

A i (1 S ) > 0 for at most k * distinct agents i ∈ N. (C * [k * ]) Indeed, condition C * [k * ]
says that it is not possible to reach a coalition with less than k * agents starting from a coalition with at least k * agents. Similarly, condition C * [k * ] says that it is not possible to reach a coalition with more than k * agents starting from a coalition with at most k * agents.14 Therefore, it is not possible to reach the trivial terminal states from any coalition S of size k * ≤ s ≤ k * , which proves the existence of a non-trivial terminal class.

Let now k = 1. Then, clearly condition (ii) is satisfied and thus condition (i) cannot be satisfied by assumption. Hence, there exists k * ∈ {1, . . . , n -1} such that there are at most k * distinct agents i 1 , . . . , i k * such that (1) If k * = k * , then we are done.

(2) If k * > k * , then let k = k * . By assumption, either (i) or (ii) does not hold.

(2.1) If (i) does not hold, then there exists k * * ∈ {k * , . . . , n -1} such that there are at most k * * distinct agents i 1 , . . . , i k * * such that A.2 Proof of Proposition 6 (i) By assumption, there exists c ∈ ∩ i∈N (c i , ci ). Let us define k := min{k ∈ N| k n > c}, then clearly k-1 n ≤ c. We show that conditions (i) and (ii) of Theorem 2 are satisfied for k. Since for all i ∈ N, µ Q i is nondecreasing and, in particular, strictly increasing on the open ball B ǫ (c) around c for some ǫ > 0, we get by Lemma 1 that

w i k = µ Q k n -µ Q k -1 n ≥ µ Q k n -µ Q (c) > 0 for all i ∈ N.
This implies that for all k = k, . . . , n -1, Thus, (i) and (ii) of Theorem 2 are satisfied for k if |D| ⌈c d n⌉, which finishes the proof.

(iii) Analogous to the second part.

  The next step is to look at the absorption probabilities of certain terminal classes. Define by D = (d S,T ) S∈T ,T ∈C ∪ := (b S,T ) S∈T ,T ∈C ∪ the matrix of transition probabilities from transient states to states within terminal classes. We can decompose D into matrices D k := (d S,T ) S∈T ,T ∈C k of transition probabilities from transient states to states within a certain terminal class. For our analysis, it does not matter at which state the influence process enters a terminal class and hence we can reduce the matrix D by considering a terminal class C k simply as a terminal state C k . The transition probabilities from transient states to a terminal class C k are then given by the vector D k := T ∈C k d S,T S∈T . Let us denote the matrix of transition probabilities from transient states to the terminal classes by D := ( D 1 : • • • : D l ) and define F := (I -Q) -1 . 7 Furthermore, denote by τ k S a stopping time such that {τ k S = m} if we have absorption by the terminal class C k after m steps of influence when starting in state S. The following result immediately follows from Brémaud (1999).

13

  Documents de Travail du Centre d'Economie de la Sorbonne -2012.56

  12 cf.[START_REF] Yager | The Ordered Weighted Averaging Operators[END_REF] 21 Documents de Travail du Centre d'Economie de laSorbonne -2012.56

  j > 0 for l = 1, . . . , k * . This implies that condition (i) is not satisfied for k = 1, . . . , k * . If k * ≥ 2 and additionally condition (ii) was not satisfied for some k ∈ {2, . . . , k * }, we were done since then there would exist k * ∈ {1, . . . , k * -1} such that there are at most nk * distinct agents i 1 , . . . , i n-k * such that k * j=1 w i l j < 1 for l = 1, . . . , nk * , i.e., (C * [k * ]) and (C * [k * ]) were satisfied for k * ≤ k * . Therefore, suppose w.l.o.g. that condition (ii) is satisfied for all k = 1, . . . , k * . ( * ) For k = n, clearly condition (i) is satisfied and thus condition (ii) cannot be satisfied. Hence, using ( * ), there exists k * ∈ {k * , . . . , n-1} such that there are at most nk * distinct agents i 1 , . . . , i n-k * such that k * j=1 w i l j < 1 for l = 1, . . . , nk * , i.e., (C * [k * ]) and (C * [k * ]) are satisfied. We now proceed by case distinction:

  j > 0 for l = 1, . . . , k * * , i.e. (C * [k * ]) and (C * [k * * ]) are satisfied for k * ≤ k * * and hence we are done.

  (2.2) If (ii) does not hold, then, using ( * ), there exists k * * ∈ {k * , . . . , k * -1} such that there are at most nk * * distinct agents i 1 , . . . , i n-k * * such that k * * j=1 w i l j < 1 for l = 1, . . . , nk * * , i.e., (C * [k * * ]) is satisfied. If k * * = k * , then we are done, otherwise we can repeat this procedure using k * * instead of k * . Since k * * k * , we find k * * = k * after a finite number of repetitions, which finishes the proof.

  i k > 0 for all i ∈ N and for all k = 1, . . . , k -1, w i k < 1 for all i ∈ N, i.e., (i) and (ii) of Theorem 2 are satisfied for k, which finishes the first part.(ii) Suppose min i∈N c i > 0 and denote by D ⊆ N the set of agents that deviate to the quantifier Q d . Similar to the first part, there exists c ∈ ∩ i∈N \D (c i , ci ) and we can define k := min{k ∈ N| k n > c}. This implies that for all k = k, . . . , n -1, have by assumption µ Q d ( k/n) = 1, which implies w i j = 0 for all j = k + 1, . . . , n and i ∈ D. Thus, for all k = k, . . . , n -1 > 0 for all i ∈ D, i.e., in combination with ( * ), condition (i) of Theorem 2 is satisfied for k. It is left to check condition (ii). Define for i ∈ D,k := max{k ∈ N|w i k > 0} = min{k ∈ N|k/n ≥ cd } ≤ k. Hence, for k = 1, . . . , k -1, k j=1 w i j < 1 for all i ∈ D. If k = k, condition (ii)is -in combination with ( * * ) -satisfied for k and any D ⊆ N. Otherwise, we have k < k and then, for k = k, . . . , k -1, all i ∈ D. This implies in combination with ( * * ) that condition (ii) is only satisfied if max k= k,..., k-1 (nk + 1) = n -k + 1 agents do not deviate, i.e., |D| ≤ n -(n -k + 1) = k -1 ⇔ |D| k ⇔ |D| ⌈c d n⌉.

14

  Documents de Travail du Centre d'Economie de la Sorbonne -2012.56

	P(τ S > m) 1 1 1 .33 .33 .04 < 10 -2 < 10 -3 3 5 10 15 25	E[τ S ] P(τ N S < ∞) 4.5 0
	2	1 .33 .11 .04 < 10 -2 < 10 -3	3.5	0
	3	0	0	0	0	0	0	1	0
	4	0	0	0	0	0	0	1	0
	12	.67 .52 .32 .08	.01	< 10 -3 4.53	.47
	13	1 .44 .36 .06	.01	< 10 -3 4.84	.16
	14	1 .44 .36 .06	.01	< 10 -3 4.84	.16
	23	1 .48 .23 .06	.01	< 10 -3 4.39	.11
	24	1 .48 .23 .06	.01	< 10 -3 4.39	.11
	34	.33 .33 .11 .01 < 10 -2 < 10 -3	2.5	0
	123	.33 .26 .16 .04 < 10 -2 < 10 -3 2.76	.74
	124	.33 .26 .16 .04 < 10 -2 < 10 -3 2.76	.74
	134	1 .56 .39 .07	.02	< 10 -3 5.18	.32
	234	1 .63 .34 .08	.02	< 10 -3 5.29	.21

Table 1 :

 1 Speed of convergence and absorption probabilities in the Confucian society (Example 1).

  then there are no other terminal classes than the trivial terminal classes.(ii) Suppose min i∈N c i > 0, then the result in (i) still holds if less than ⌈c d n⌉ agents deviate to a regular quantifierQ d such that cd < min i∈N c i . (iii) Suppose max i∈N ci < 1, then the result in (i) still holds if less than ⌈(1c d )n⌉ agents deviate to a regular quantifier Q d such that max i∈N ci < c d .The proof is in the appendix. Note that the deviating agents can in fact also use different quantifiers, as follows.Remark 3. (i) Suppose min i∈N c i > 0, then the result in part (i) of the Proposition still holds if k < ⌈min d cd n⌉ agents i d 1 , . . . , i d k deviate to regular quantifiers Q d such that cd < min i∈N c i for all d = d 1 , . . . , d k . (ii) Suppose max i∈N ci < 1, then the result in part (i) of the Proposition still holds if k < ⌈(1max d c d )n⌉ agents i d 1 , . . . , i d k deviate to regular quantifiers Q d such that c d > max i∈N ci for all d = d 1 , . . . , d k .

  then a state S ⊆ N of size s is a terminal state if and only if

	max i∈S ci ≤	s n	≤ min i∈N \S	c i .
	Proof. Suppose S ⊆ N of size s is a terminal state. By Proposition 5, we
	know that this is equivalent to
	s		s
	w i k = 1 for all i ∈ S and
	k=1		k=1

  then there are no other terminal classes than the trivial terminal classes. The result still holds if less than ⌈ 3 10 n⌉ agents deviate toQ af . (ii) If Q i ∈ {Q ma , Q af } for all i ∈ N,then there are no other terminal classes than the trivial terminal classes. The result still holds if less than ⌈ 1 2 n⌉ agents deviate, each of them either to Q aa

Table 3

 3

	). Note that for

Table 2 :

 2 Speed of convergence and absorption probabilities in Example 6 (i).

	P(τ s > m) 1 1 .28 .02 < 10 -2 < 10 -5 1.38 3 5 10 E[τ s ] P(τ N s < ∞) P(τ ∅ s < ∞) 0 .04
	3	.47 .10	.02	< 10 -3 1.88	.74	0

Table 3 :

 3 Speed of convergence and absorption probabilities in Example 6 (ii).

Documents de Travail du Centre d'Economie de la Sorbonne -2012.56

Note that the model can be easily generalized to the case where agents have inclinations that are tendencies x i ∈ [0, 1] to say "yes". These tendencies generate a probability distribution of initial states. Our results still hold in this setting.

A vector w ∈ [0, 1] n is a weight vector if n i=1 w i = 1.

We say that there is a path from S to T if there is K ∈ N and states S = S 1 , S 2 , . . . , S K-1 , S K = T such that A i (S k ) > 0 for all i ∈ S k+1 and A i (S k ) < 1 otherwise, for all k = 1, . . . , K -1.6Documents de Travail du Centre d'Economie de laSorbonne -2012.56

This assumption is not limitative, and correlated opinions may be considered as well. In the latter case, only the next equation giving b S,T will differ.

Note that we do not consider the speed of convergence to certain terminal classes since its expected value will be infinite if there is a positive probability that this may not happen. Instead, we consider later on the absorption probabilities of certain terminal classes.

cf.[START_REF] Brémaud | Markov Chains[END_REF]. Of course, it is understood that the right member is a matrix whose entries are all +∞. 9 Documents de Travail du Centre d'Economie de laSorbonne -2012.56

Note that for absorbing Markov chains the matrix F always exists since Q m → 0 for m → ∞. 10 Documents de Travail du Centre d'Economie de la Sorbonne -2012.56

Of course, we could also discuss the convergence after the process has entered a terminal class. This is obvious at least for singleton and cyclic terminal classes, though. For the latter, there is clearly no convergence to a stationary distribution. Furthermore, it holds that regular classes are convergent if and only if their corresponding transition matrix is aperiodic.12 Documents de Travail du Centre d'Economie de laSorbonne -2012.56

It is clear that in general, the necessity part does not hold since convergence to consensus may as well be (partly) ensured by the other component.

Note that this is due to our definition. The conditions in Definition 8 ensure that there exists such an ordered weighted average. In general, one can define quantifiers also by other functions, cf.[START_REF] Zadeh | A computational approach to fuzzy quantifiers in natural language[END_REF].

Note that monotonicity of the aggregation function implies that (C * [k * ]) also holds if we replace S by a coalition S ′ ⊆ N of size s ′ > k * . Analogously for (C * [k * ]). 29 Documents de Travail du Centre d'Economie de la Sorbonne -2012.56

† This research project is supported by the Doctoral Programme EDE-EM ("European Doctorate in Economics -Erasmus Mundus") of the European Union, and by the National Agency for Research (Agence Nationale de la Recherche, reference: ANR-09-BLAN-0321-01), which are gratefully acknowledged.


Bilel Saadallah

Abdelkader Lahmadi

Olivier Festor

CCNx in Every Sensor

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

CCNx in Every Sensor

Bilel SAADALLAH, Abdelkader LAHMADI, Olivier FESTOR Interested in getting the code, please contact: abdelkader.lahmadi@loria.fr

Context and Motivation

Experiment & Results

Topology

Parameters

• Available content at each node N i : temperature, humidity, battery, light, RSSI, ETX

• 180 seconds between two collection requests to every node

••

  Growth Develop a fully operational CCN communication stack • Adjust CCN messages and optimize Interest for reused data collection • Overcome the IEEE 802.15.4 frame size limit (102 bytes for payload) Management applications adaptation • Collect desired management content • Monitoring-oriented naming scheme • Apply in-network processing functions for data aggregation • Minimize communication overhead • Improve delivery speed and reduce congestion Approach Contiki Operating System: http://www.contiki-os.org/ • The Open Source Operating System for the Internet of Things • Contiki allows tiny, battery-operated low-power systems communicate with the Internet • Providing several communication stacks CCNx Stack in Contiki • Implements CCN processing functions, message forwarding and data caching • Manages event posting to processes • CCN Driver: handles message exchange with the lower layer • Hierarchical names with components of arbitrary lengths • Names in URI representation • Content storage at intermediate nodes Message Adaptation • Simplify Interest and Content Object messages Summary • C language CCNx stack in Contiki

Round 2nd Round 3rd Round

	Node 1	250	250	250
	Node 2	328	258	250
	Node 3	250	258	258
	Node 4	328	258	258
	Node 5	328	265	258
	Node 6	461	265	258
	Node 7	461	258	258
	Node 8	461	258	258
	Node 9	328	258	258

• Interest with prefix /COLLECT/Ni to collect data from node i • Content updated every 70 seconds at each node N i Delivery Delays Delay (ms) 1st


Andrea Crisanti
email: andrea.crisanti@phys.uniroma1.it

Cirano De Dominicis
email: cirano.de-dominicis@cea.fr

The Sherrington-Kirkpatrick model near Tc and near T=0

Keywords: disordered systems, Ising models, statistical mechanics spin glass

Some recent results concerning the Sherrington-Kirkpatrick model are reported. For T near the critical temperature Tc, the replica free energy of the Sherrington-Kirkpatrick model is taken as the starting point of an expansion in powers of

The expansion is kept up to 4-th order in δQ where a Parisi solution Q ab = Q(x) emerges, but only if one remains close enough to Tc.

For T near zero we show how to separate contributions from x ≪ T ≪ 1 where the Hessian maintains the standard structure of Parisi Replica Symmetry Breaking with bands of eigenvalues bounded below by zero modes. For T ≪ x ≤ 1 the bands collapse and only two eigenvalues, a null one and a positive one, are found. In this region the solution stands in what can be called a droplet-like regime.

Introduction

The Sherrington-Kirkpatrick (SK) model [1,2], introduced in the middle of 70's as a mean-field model for spin glasses, has played and important role besides the study of spin glasses. The search for its solution in the low temperature phase, the spin glass (SG) phase, has lead to the introduction and development of tools such as the Replica Method and the concept of Replica Symmetry Breaking, that have found applications in a variety of other fields of the complex-system world, just to cite a few, neural networks, combinatorial optimization and glassy physics.

The signature of the SG state is the presence of a large number of degenerate, locally stable states. When the system is driven into the SG phase, the spins almost freeze and fluctuate along local fixed directions. Thus, similar to what happens in the low temperature phase of a ferromagnet, the thermal average of a single spin does not vanishes in the SG phase. Yet, at difference with a ferromagnet, the local directions may change from spin to spin without any special rule, that is in a random way. Therefore the SG phase is not characterized by a long range ordering. Also, since each spin can choose among different local directions, the SG phase is actually made by a large number of degenerate locally stable states. If we take a shot of one of such SG state, we shall discover that it is not distinguishable from a paramagnetic, i.e., disordered state. Thus we can think of the SG phase made by a large set of almost frozen paramagnetic (disordered) states.

Direct consequence of such a scenario is that identical ideal replicas of the system, indistinguishable in the paramagnetic phase, when driven into the SG phase may end up into different SG states and, hence, becoming distinguishable. The symmetry among replicas is then broken.

The solution of the SK model which accounts for this scenario was found at the end of the 70's, and it is now know as the "Parisi Solution" [3,4]. Since then many of its properties have been studied and understood. Some questions, however, are still open, among them its validity for finite dimensional systems. Despite the subtleties, and mathematical ambiguities, of the replica method, see e.g. [5], it is now accepted that the Parisi Solution is correct for the mean-field SK model. For finite dimensional systems it is less clear and a different scenario, the droplet picture, an essentially replica symmetric description, as been put forward. The connection between the two is still not fully understood.

In this paper we shall discuss SK model replica symmetry breaking solutions close to the replica symmetric one, that is obtained by expanding about the replica symmetric solution. The interest for these solutions is twofold: from one side one can investigate the set up of the replica symmetry breaking in the SG phase. The study of these solutions is also relevant for the definition of a field theory description of the SG phase that could be used to investigate the crossover from mean-field to the finite dimensional systems.

In the last part of the paper we shall briefly discuss the solution of the SK model in the limit T ≪ 1, where an (almost) replica symmetric description arises.

The SK model and the SK-solution

The Sherrington-Kirkpatrick (SK) model in absence of external fields is defined by the Hamiltonian [1,2]

H = - 1 2 1,N i =j J ij σ i σ j (1)
where σ = ±1 are Ising spins and the symmetric couplings J ij are i.i.d. quenched Gaussian random variables of zero mean and variance equal to 1/N . All pairs of spins (i, j) interacts, and the scaling of the variance ensures a well defined thermodynamic limit as N → ∞.

The thermodynamic properties of the model are obtained from the free energy (density) -βN f J = ln Z J , where β = 1/T is the inverse temperature. In disordered systems Z J , and hence f J , is a random quantity. We must therefore average the free energy f J over the disorder. To overcome the difficulties of averaging a logarithm, the average over the disorder is computed using the so-called replica trick. This procedure is essentially the identity

-βN f = [ln Z] J = lim n→0 [Z n ] J -1 n , (2)
where the square brackets denote disorder average, and f the disorder averaged free energy density. For an integer n, Z n may be expressed as Z n = n a=1 Z a , and may be interpreted as the partition function of n identical, non-interacting, replicas of the real systems. Averaging Z n for integer n over disorder introduces an effective interaction between replicas. Performing the average, and introducing the auxiliary symmetric replica overlap matrix Q ab = 1 N i σ ia σ ib , with a = b, the disordered averaged replica partition function can be written as [2]:

[Z n ] J = a<b N β 2 2π dQ ab e N L[Q] (3)
with the effective Lagrangian (density)

L[Q] = - β 2 4 ab Q 2 ab + Ω[Q] -n β 2 4 (4) Ω[Q] = ln Tr σa exp β 2 2 ab Q ab σ a σ b (5)
The last term in (4) follows from the definition Q aa = 1. The normalization factor in (3) gives a sub-leading contributions for N → ∞ and is omitted in the following.

In the thermodynamic limit, N → ∞, the integral over Q ab in ( 3) is evaluated at the stationary point,

∂ ∂ Q ab L[Q] = 0, a < b, (6)
that leads to the self-consistent equation for Q ab :

Q ab = Tr σ σ a σ b exp β 2 2 ab Q ab Tr σ exp β 2 2 ab Q ab σ a σ b = σ a σ b , a = b. (7)
The replica free energy density then reads:

-nβ f (n) = L[Q], (8)
and the average free energy f is recovered as the limit n → 0 of f (n).

To solve the self-consistent stationary point equation (7) an assumption on the structure of the overlap matrix Q ab must be done. As the n replicas of the real system are identical, one may reasonably assume that the solution should be symmetric under the exchange of any pair of replicas. Based on this, SK in their original work assumed [2]

Q ab = δ ab + q (1 -δ ab ) ( 9
)
where q is the overlap between any pair of different replicas. This form of Q ab is what it is now known as the Replica Symmetric (RS) Ansatz. The physical meaning of q is

q = σ i 2 J ( 10
)
where • • • denotes here thermal average for fixed disorder. In absence of an external field the local direction of σ i is random, and depends on the disorder realization, and hence [ σ i ] J = 0. Therefore a nonzero q indicates local magnetic order, without a long range ordering. Substitution of Ansatz ( 9) into the stationary point equation ( 7), or into eqs. ( 4), ( 5) and ( 6), leads in the n → 0 limit to the self-consistent equation

q = +∞ -∞ dz √ 2πq e -z 2 /2q tanh 2 (βz), (11)
that, besides the paramagnetic solution q = 0, admits for T < T c = 1 a non-trivial q = 0 solution. The order parameter q(T ) is a decreasing function of temperature, that is equal to 1 at T = 0 and vanishes for T → T - c . An explicit solution of ( 11) may be obtained by expanding near the points T = 0 and T = 1. One then finds that q vanishes as T c -T as the critical temperature T c is approached from below, while 1 -q(T ) ∼ T as T → 0.

This solution yields, however, an unphysical negative zero temperature entropy [2]. The analysis of the stability of the stationary point also reveals that the RS stationary point becomes unstable as n → 0 for all temperatures T < T c [6].

The failure of the RS Ansatz has a physical origin. Below the critical temperature T c the phase space of the SK model breaks down into a large, yet non extensive, number of degenerate locally stable states in which the system freezes. The symmetry under replica exchange is then spontaneously broken, and the overlap matrix becomes a non-trivial function of the replica indexes. Following the parameterization introduced by Parisi [3,4], the overlap matrix Q ab for R steps of replica permutation symmetry breaking -called RSB solution-is divided along the diagonal into successive boxes of decreasing size p r , with p 0 = n and p R+1 = 1, and elements given by:

Q ab ≡ Q a∩b=r = Q r , r = 0, • • • , R + 1 (12) with 1 = Q R+1 ≥ Q R ≥ • • • ≥ Q 1 > Q 0 .
In this notation r = a ∩ b denotes the overlap between the replicas a and b, and means that a and b belong to the same box of size p r but to two distinct boxes of size p r+1 < p r . The solution of the stationary point equation can be obtained for any value of R [3,4,7]. The case R = 0 gives trivially back the RS solution. It turns out that a physically acceptable solution for the SK model is obtained only by letting R → ∞, that is by allowing for an infinite number of possible spontaneous breaking of the replica permutation symmetry. The solution is called full replica symmetry breaking (FRSB), or infinity-RSB solution (∞-RSB) to stress the limit R → ∞. In this limit Q r -Q r-1 → 0, r = 0, . . . , R, and the matrix Q ab is described by a continuous, non-decreasing function Q(x) parameterized by a variable x. The meaning of x may depend on the parameterization used. In the Parisi scheme x ∈ [0, 1] and measures the probability for a pair of replicas to have an overlap not larger than Q(x) [8]. The FRSB equations can be solved in the full low temperature phase [9][10][11][12][13][14][15]. In Fig. 1 we show the form of Q(x) obtained from the numerical solution of the FRSB equation [From Ref. [10]].

Expansion around the RS solution

From the analysis of the replica symmetry breaking solution at small finite replica number n, Kondor [16] has found that below, but close to, the critical temperature T c the instability of the RS solution appears at the finite value n = n s (T ) < 1. For n ≥ n s (T ) the free energy f (n) coincides with f SK (n) from the RS solution, while for 0 ≤ n ≤ n s (T ) it is given by f FRSB (n) from the FRSB solution. The crossover is rather smooth since f SK (n) and f FRSB (n), along with their first two derivatives, coincide at n s (T ). To investigate the nature of the replica symmetry breaking in the low temperature phase one can then expand Q ab around the RS solution.

One then considers an overlap matrix Q ab of the form, see eq. ( 9),

Q ab = Q RS ab + q ab = δ ab + q (1 -δ ab ) + q ab ( 13
)
where q is given by the SK Replica Symmetric solution (11) and q ab is the deviation from the Replica Symmetric solution. Inserting this form of Q ab into (4), and expanding the functional Ω[Q] in powers of q ab , yields:

-nβf = -nβf SK - β 2 2 q ab q ab - β 2 4 ab q 2 ab + k≥1 1 k! β 2 2 k ab q ab σ a σ b k c + O(n 2 ) ( 14
)
where the subscript "c" indicates that only connected contributions must be considered, i.e., only the terms that cannot be written as the product of two or more independent sums. All others give contributions of O(n 2 ), or higher. The first contribution, f SK , is the SK free energy

-βf SK = β 2 4 q 2 - β 2 2 q + ln cosh(βz) + ln 2 + O(n) (15)
where the overbar denotes the average over the Gaussian variable z: Whit this notation the RS solution (11) takes the compact form

g(z) = +∞ -∞ dz √ 2πq e -z 2 /2q g(z). (16)
q = θ 2 , θ ≡ tanh(βz). ( 17
)
Expanding the cumulants in eq. ( 14) up to order O(q 4 ab ) included, the lowest term needed to break replica symmetry, one obtains [17] -nβf = -nβf SK + 1 4T 4 M abc q ac q cb + N ab q 2 ab + 1 6(2T 2 ) 3 P abcd q ac q cd q db + Q abcd q ad q bd q cd + R abc q 2 ac q cb +J ab q 3 ab + K abc q ac q cb q ba + 1 24(2T 2 ) 4 -A abcde q ae q be q ce q de + B abcd q ac q 2 cd q db (18)

-B abcde q ac q dc q ce q eb + C abc q ac q 2 cb q ba -C abcd q ac q ad q dc q cb +4D abc q 3 ac q cb -3D abcd q 2 ab q bc q bd + E abcde q ab q bc q cd q de -2E abcd q ab q bc q 2 cd + F abcd q ab q bc q cd q da + G ab

q 4 ab -H abc q 2 ac q 2 cb +O(n 2 )
where

M = 2 θ 2 (1 -θ 2 ), N = (1 -θ 2 ) 2 -T 2 . ( 19
)
P = 24 θ 2 (1 -θ 2 ) 2 , Q = -16 θ 4 (1 -θ 2 ), R = -48 θ 2 (1 -θ 2 ) 2 , (20)
J = 16 θ 2 (1 -θ 2 ) 2 , K = 8 (1 -θ 2 ) 3 (21)
A = 32 θ 4 (1 -3θ 2 )(1 -θ 2 ), B = 384 θ 4 (1 -θ 2 ) 2 , C = 384 θ 2 (1 -θ 2 ) 3 , (22)
D = 64 θ 2 (1 -3θ 2 )(1 -θ 2 ) 2 , E = 192 θ 2 (1 -θ 2 ) 2 , F = 48 (1 -θ 2 ) 4 , (23)
G = 32 (1 -3θ 2 ) 2 (1 -θ 2 ) 2 , H = 96 (1 -3θ 2 )(1 -θ 2 ) 3 . (24)
The equation for q ab follows from the stationarity condition (∂/∂q ab )f = 0 applied to the replica free energy functional (18). In the limit R → ∞ this becomes an integro-differential equation for q(x), whose solution is

q(x) = Γ x -s (x -s) 2 + ∆ -a -bS 1 , 0 ≤ x ≤ x c , (25)
and q(x) = q(x c ) for x c ≤ x < 1. The parameters a, b, s and ∆ are functions of the coefficients of the expansion (18), and hence of T , while Γ, S 1 and x c must be determined selfconsistently. For details we refer to Ref. [17]. It turns out that below the temperature T = 0.549 . . . no physical solution with q(x) = 0 is exists and only the SK solution Q(x) = q survives. Figure 2 shows the solution Q(x) = q + q(x) for T = 0.9. Near the critical temperature T c = 1 the solution can be expanded in powers of τ = T c -T ≪ 1. The first terms of the expansion of q(x) for 0 ≤ x ≤ x c read

q(x) = x √ 4 + 6x 2 + 1 - 4 √ 2 (2 + 3x 2 ) 3/2 + 3x(2 + x 2 ) √ 2(2 + 3x 2 ) 3/2 τ 1 3(2 + 3x 3 ) 5/2 64 √ 2 -236 √ 2x + 312 √ 2x 2 -138 √ 2x 3 -81 √ 2x 5 -56 2 + 3x 2 -168x 2 2 + 3x 2 -126x 4 2 + 3x 2 τ 2 +O(τ 3 ), (26)
while for the breaking point x c one has From these expressions, and the expansion of the RS solution q close to T c , follows

x c = 2τ -4τ 2 +
Q(0) = q + q(0) = 56 3 τ 3 - 220 3 τ 4 + 3968 9 τ 5 + O(τ 6 ) (28) Q(x c ) = q + q(x c ) = τ + τ 2 -τ 3 + 5 2 τ 4 - 413 90 τ 5 + O(τ 6 ). ( 29
)
A peculiarity of this FRSB solution is that Q(x) does not vanishes at x = 0, as Fig. 2 clearly shows. Q(x = 0) only vanishes at T c , and grows as (T c -T ) 3 , see eq. ( 28), below it. The reason for such a behaviour is that the FRSB "opens" around the RS solution Q RS (x) = q. As the temperature decreases the RS solution q grows from zero and drags Q(x = 0) to finite values. At T = 0.618 . . . the value of Q(x = 0) eventually overcomes that of q.

In the absence of external fields that break the up/down symmetry Q(x = 0) must vanish. The finite value of Q(x = 0) then indicates that more terms in the expansion ( 14) must be retained in order to balance the drag from q. Alternatively a null value of Q(x = 0) can be recovered by taking q = 0, which eliminates the drag from the beginning. Physically this means by performing the expansion around the paramagnetic solution. In this case, however, the FRSB solution exists in a narrower region, 0.9148 . . . ≤ T ≤ 1, close to the critical temperature.

We note that the choice q = 0 was used to derive the so called Truncated Model [3,18] largely used to study the low temperature phase of the SK model. This model is based on an expansion that retains only the main mathematical structure of the expansion of the replicated free energy in powers of Q ab near T c , where |Q ab | ≪ 1, but, similar to the Landau Lagrangian, with arbitrary coefficients. The mapping between the expansion (18) with q = 0 and the Truncated Model is 5 w and G = 32T 7 u with arbitrary u and w. In this case, if w and u are temperature independent, the FRSB solution exists only down to T trm = 1 -w 2 /4u.

F = H = 0, N = 2T 3 (1 -τ ), K = 8T

Solution near T = 0

In the previous Section we have seen that the RS solution can be taken as a starting point for a development of the FRSB solution for T c -T ≪ 1. As the temperature becomes significantly lower than T c the expansion looses physical meaning and more and more terms are needed into the expansion to extend its validity. Due to the particular structure of the expansion, in powers of β, it is likely that an infinite subset of terms should be considered to tackle with very low temperatures.

Surprisingly a Replica Symmetric description appears at T → 0. Indeed as the temperature is lowered towards T = 0 the probability that Q ab ≤ q c (T ) = O(1) remains finite, viz. x c ≃ 0.524 . . . as T → 0 [10,19] . At the same time the probability of finding overlaps Q ab significantly smaller than q c (T ) = O(1) vanishes with T . Then, since Q(x = 0) = 0, for T ≪ 1 the order parameter function Q(x) undergoes an abrupt and rapid change of O(1) in a tiny boundary layer of thickness δ ∼ T close to x = 0, while it is slowly varying for δ ≪ x ≤ x c , as depicted in Fig. 3. In the limit T → 0 the thickness δ ∼ T → 0, and the order parameter function becomes discontinuous at x = 0.

Uniform approximate solutions valid for T ≪ 1 can be constructed by studying the problem separately inside (inner region) and outside (outer region) the boundary layer. The inner solution for Q(x) was first computed by Sommers and Dupont [9], and recently extensively studied by Oppermann, Sherrington and Schmidt [13][14][15]. It turns out that as T → 0 the inner solution Q(a) remains a smooth function the inner variable a = x/T , needed to blow up the inner region, varying between 0, for a = 0, and q c (T ) ∼ 1, for a ≫ 1. The outer solution was studied by Pankov [12], who found that in the outer region one has

Q(x) ∼ 1 -c(βx) -2 , T ≪ x ≪ x c and T → 0 (30)
where c = 0.4108 . . . and x c ≃ x c (T = 0) = 0.524 . . .. This behaviour of Q(x) has strong consequences on other relevant quantities and, also, on the structure of the eigenvalue spectrum of the Hessian of the fluctuations governing the stability of the stationary point. For what concerns the stability one finds [7,20] that in the region x ≤ δ ∼ T , where Q(x) varies rapidly from 0 up to q c ≃ 1, the spectrum of the Hessian of the fluctuations maintains the complex structure of the FRSB solution found close to T c [21]. That is a Replicon band whose lowest eigenvalues are zero modes, and a Longitudinal-Anomalous band of positive masses.

In the region T ≪ x ≤ x c , the eigenvalue spectrum has a completely different aspect. The bands observed in the FRSB regime collapse and only two distinct eigenvalues are found: a null one and a positive one [20]. This ensures that the FRSB solution remains stable down to zero temperature. We note that zero modes arise from the Replicon geometry, with Ward-Takahashi identities protecting them [22], and arises also from the Longitudinal-Anomalous geometry, without protection of the Ward-Takahashi identities. It is worth to observe that the stability analysis of the RS solution also leads to two eigenvalues, one of which is zero to the lowest order in T c -T (and negative to higher order) and a positive one [6].

From the expression (30) it follows that the variation of Q(x) in the outer region, 2 , rather weak for T → 0. Thus in this region, that covers the overwhelming part of the interval 0 < x < 1 for T → 0, we have a marginally stable (almost) Replica Symmetric solution, that become a genuine Replica Symmetric solution for T → 0, with self-averaging trivially restored. In this paper we have reported some recent results on the solution of the SK model. In particular we have considered two different issues. In the first part we discussed the analysis of the Replica Symmetry Breaking done through an expansion around the Replica Symmetric solution. In the second part we examined the properties of the solution in the limit of vanishing temperature. The expansion of the replica free energy functional around the RS solution, truncated to the fourth order in q ab = Q ab -Q RS ab , leads to a FRSB solution with a continuous order parameter Q(x) below the critical temperature T c = 1. The solution, however, exists only in the range 0.549 . . . ≤ T ≤ T c . Moreover the value of Q(x = 0) is finite and vanishes only for T → T - c with the third power of the temperature difference. A null Q(x = 0) can be recovered by expanding about the (replica symmetric) paramagnetic solution q = 0. In this case, however, the FRSB solution exists only close to T c = 1, in the narrower interval 0.915 . . .

T ≪ x ≤ x c , is [Q(x c ) -Q(x)]/Q(x) ∼ c(T /x)
≤ T ≤ T c = 1.
For what concerns the stability we believe that the solution form the expansion around the paramagnetic solution q = 0 has the same stability properties in the most dangerous sector, i.e., in the Replicon subspace by virtue of the Ward-Takahashi identities [22], of the Truncated Model. We believe that this feature remains true for the expansion around the SK solution as well [23]. Thus the FRSB, where it does exist, is marginally stable with null Replicon eigenvalues.

Finite RSB solutions, or even RS solution q ab = q (1-δ ab ), may also exists. These may exists for all temperatures below T c , or only in a limited range of temperature. In either case all these solutions are unstable, with negative Replicon eigenvalues.

The main limitation of the expansions discussed here is the limited range of temperatures where the FRSB solution exists. To extend the range one should retain more terms in the expansion. This will also cure the finite value of Q(x = 0). Due to the particular structure of the expansion, in powers of β, it is likely that an infinite subset of terms should be considered to extend the validity of the expansion to very low temperatures. If one is interested into these temperatures different approaches, e.g., that proposed in Ref. [24] based upon an expansion around a spherical approximation that leads instead to an expansion in T , may be more suitable.

The striking property of the solution of the SK model for T ≪ 1 is the presence of two well distinct regions where the order parameter function Q(x) behaves differently. In the first region, close to x = 0, Q(x) varies rapidly from Q(x = 0) = 0 to Q(x) ∼ q c = O(1) for x ∼ T . In this region, that contains (almost) the whole variation of Q(x), the solution maintains the structure of the FRSB solution found for higher temperature and close to T c , including the complex Hessian spectrum, even in the limit T → 0. For this reason this region was called the RSB-like regime.

In the second region, for T ≪ x ≤ x c ≃= 0.575 . . ., Q(x) is a very slow varying function of x, the variation being indeed of the order [Q(x c ) -Q(x)]/Q(x) = O (T /x) 2 . Here the bands observed in Hessian spectrum for the RSB regime disappear, and only two distinct eigenvalues are found: a null one and a positive one, ensuring the stability of the FRSB solution down to T → 0. In this region, that covers the overwhelming part of the interval 0 < x < 1 for T ≪ 1, the solution strongly resembles a stable RS solution typical of a droplet description. For this reason this region was called droplet-like regime.

In the limit T → 0 the domain of the RSB-like regime shrinks to zero, and only the droplet-like part of the solution remains. It is then tempting to interpret this as a zero temperature transition/crossover from a FRSB solution to a droplet scenario. We stress, however, that while these results strongly suggest a transition or crossover between RSB and droplet descriptions in spin glasses, to have a better understanding of the behavior of finite dimensional systems loop corrections to the mean-field propagators must be considered [START_REF] Bray | Heidelberg Colloquium on Glassy dynamics and optimizations[END_REF]. Work in this direction is in progress.

Figure 1 .

 1 Figure 1. Q(x) as function of x for various temperatures. From bottom to top T = 0.95 to T = 0.30 in step of 0.05 [From Ref. [10]].

Figure 2 .

 2 Figure 2. Q(x) versus x at temperature T = 0.9. The horizontal dashed line shows the SK solution Q(x) = q. For this temperature we have xc = 0.168846 . . ., Q(xc) = 0.109238 . . . Q(0) = 0.013570 . . . and q = 0.102701 . . ..

Figure 3 .

 3 Figure 3. Shape of Q(x) as function of x for T ≪ 1. The shaded ares shows the extent of the layer of thickness δ ∼ T where the larger variation of Q(x) is concentrated.

http://mc.manuscriptcentral.com/pm-pml Philosophical Magazine & Philosophical Magazine Letters