The Role of Clustering on the Emergence of Efficient Social Conventions

1 Introduction

Social conventions, according to [Ullmann-Margalit, 1977], are a special type of norms related to coordination problems, that is, those regularities of behavior which are a result of being a solution of a recurrent coordination problem, which with time, turn normative. The emergence and stabilization of norms, including social conventions, is one of the fundamental problems of social sciences [Bendor and Swistak, 2001]. Intuitively, a social convention might be regarded as any rule of behavior or a behavioral constraint [Walker and Wooldridge, 1995]. A convention simpli�es people's decision making problem by dictating how to act in certain situations. Therefore, social conventions help to reduce complexity and uncertainty, particularly when the environment is open and dynamic. From this perspective it is obvious that mechanisms underlying the emergence of social conventions are of great interest for Distributed Arti�cial Intelligence.

∗This work was supported in part by EuropeAid @LIS TechNET project ALA2002/049-055/2209

†This work was supported in part by the Catalan Autonomous Government Project e-Catalunya

[Shoham and Tennenholtz, 1992] addressed the question whether and how the emergence of conventions is possible from decentralized, local interaction, as opposed to conventions designed and enforced a priori by a central authority. Shoham demonstrated that self-coordination based on a simple local optimization rule can emerge from initial disorder. Following Shoham's, many researchers have studied and improved his seminal work, proposing other strategies rather than HCR [Walker and Wooldridge, 1995], studying the time needed before the convention is established [Kittock, 1993], adding complex interaction patterns among agents [Delgado, 2002], and many others.

However, an important question remains open, when two potential different conventions exist which one will be established at the end? This question is not applicable to the original work of [Shoham and Tennenholtz, 1992], since the game was a pure coordination game, where no action paretodominates the other. Nevertheless, the question applies to all coordination games where one action is more ef�cient than the other. The discussion in social sciences gives no clear answer to why and under what conditions ef�cient conventions may prevail. As [Bendor and Swistak, 2001] point out, there are at least two con�icting positions in sociology, the strong functionalism thesis and the rational choice view. Strong functionalism claims that norms and conventions exist because they are functional for the group, that is, they yield optimal collective outcomes. According to this perspective, the system should always end up in an ef�cient convention. However, the functionalist approach has been criticized for its lack of a microfoundation. Adherents of the rational choice view on norms argue that individuals adopt norms only when it serves their self-interest to do so. This includes the possibility that mechanisms such as social control may stabilize conventions that are an individually ef�cient response to the given constraints, but are socially inef�cient.

In section 2 we describe our model. In section 3 we describe the experimental results and analyze the necessary conditions to converge to the optimal convention. In section 4 we analyze the time ef�ciency of the emergence of conventions. In section 5 we integrate and analyze experimentally optimization and imitation partially competing decision mechanisms in the model. Finally, main results are summed up in section 6.

2 Formal Model

We follow the conceptual framework introduced by [Shoham and Tennenholtz, 1992], and the extension proposed by [Delgado, 2002] that introduced complex networks as the underlying topology. .

2.1 The Coordination Game

A set of N agents must choose to play one of two possible actions: either A or B. Accordingly to its current action, or state, an agent interact with its neighbors receiving an outcome de�ned in payoff matrix G.

The payoff matrix G de�nes a 2-person 2-choice symmetric coordination game provided that x > v and y > u. The condition on the entries of G makes clear that to play the same action is the best choice. It is trivial to demonstrate that the game G has two nash-equilibrium, both agents playing either A or B. Most previous work focused in the study of pure coordination games: where x = y = +1,v = u = -1 [Walker and Wooldridge, 1995; Kittock, 1993; Shoham and Tennenholtz, 1997; Delgado, 2002]. In our approach we move beyond this work and allow for coordination games with equilibrium differing in social ef�ciency (i.e. x > y).

For simplicity we assume that coordination on action A is at least as pro�table as coordination on action B: x ≥ y. Thus, game G is de�ned as follows: v = u = -1, y = +1, and x = α provided that α ≥ 1. When α > 1, coordination in B is a sub-optimal solution since there exists a paretoef�cient solution that pareto-dominates B, which is, coordination in action A.

2.2 Action Selection Rule and Dynamics

Our MAS is composed of N agents that interact only with its neighbors in the social network, playing the game G once per interaction. Every agent, say the kth, has memory Mk that records the M last interactions of agent k. The value of the position i of the memory Mk is the tuple 〈aik , pik , ti 〉, where aik stands for the action played by k, pik stands for the payoff received after playing action aik , and ti denotes the time the interaction took place. The initial action of the agents is set randomly with a probability rB , which is the density of agents playing action B in the beginning.

Following [Shoham and Tennenholtz, 1992] we will use the Highest Cumulative Reward (HCR) action selection rule. Intuitively HCR says: if the accumulated payoff obtained from playing A is bigger than that from playing B then keep on A, otherwise change to action B. The HCR rule is very appropriate since it provides: 1) Locality: the selection function only depends on the agent's personal history. No global knowledge of the system is required, not even the payoff matrix of the game. 2) Adaptability: the agent learns from its experience without assuming cognitive capabilities. These characteristics are very important in MAS.

The dynamics of the system are as follows. At each time step t, an agent k is randomly activated. Once the agent is activated, it plays the game G with an agent randomly chosen from k's neighborhood, say agent l. The result of the interaction is stored into agent k's memory Mk, removing the oldest entry if necessary. Finally, agent k must decide whether to change its action or not. To do so it uses the Highest Cumulative Reward rule. Agent k will compute the payoff received for using action S on the last M activations: P k S = ∑i:aik=S pik , where S = {A|B}. Agent k will switch to action S if P k S > P k S . Agent l also carries out the memory storage and the action updating while the rest of agents remain still. The system ends once all agents play either action A or B, which means, that a convention on either A or B have been established.

2.3 Underlying Topology

To model qualitatively different interaction structures, we use several graph models that recently have been shown to have profoundly different effects on cooperation and diffusion dynamics in MAS [Watts and Strogatz, 1998; Albert and Barab·asi, 2002; Delgado, 2002]. The chosen graphs are: a) Random graphs: R〈k〉 N , where N is the number of nodes, and 〈k〉 is the average connectivity, that is, the average size of node's neighborhood. Random graphs have a clustering coef�cient that tends to zero. The average path length grows logarithmically in function of N, the number of nodes. b) Regular graphs: C kN , regular graphs display an extremely high clustering coef�cient, while its average path length and diameter grows linearly. Which means, for big graphs the average path length is very long, which does not agree with empirically studied networks. However, regular graphs display the close-knit property due to its high clustering coef�cient, which does agree with empirical studies. c) Smallworld graphs: W 〈k〉,p N , these are highly-clustered graphs (like regular graphs) with small average path length (like random graphs). This is the small-world property. We chose the [Watts and Strogatz, 1998] model as model of small-world graphs, where p is the rewiring probability. d) Scale-free graphs: S 〈k〉,-γ N , these are graphs with a connectivity distribution P(k) of the form P(k) ∝ k-γ . The connectivity degree, the number of neighbors of a node, decays as a potential law. This favors the so-called fat-tail phenomena; few nodes with an extreme high connectivity. We chose the [Barab·asi and Albert, 1999] model as a model of scale-free graph.

Recent studies on empirical networks show that neither regular nor random graphs appear in nature. Noticing this, [Delgado, 2002] studied the effect of complex networks (small-world and scale-free networks) on the emergence of coordination and found that this class of networks were as ef�cient as the complete graph in terms of time to reach a convention, O(NlogN) compared to O(N 3 ) from regular graphs, already shown by [Kittock, 1993]. It is important to stress that many empirical social networks such as the collaboration network among actors, the co-authorship network of researchers on mathematics, the researchers on neuroscience and many others are classi�ed as scale-free networks. However, for these empirical social networks the clustering coef�- cient found is very high: 0.79, 0.59, 0.76 respectively. Let us show the clustering coef�cient of graphs we will use in the experiments: C 10 1000=0.666, W <10>,0.1 1000 =0.492, S <10>,-3 1000 = 0.0433 and R<10> 1000 =0.0081. Notice that empirical social networks are much more clustered than the scale-free networks yield by the [Barab·asi and Albert, 1999] model. But we still use this model since scale-free models are focused in reproducing the connectivity degree rather than clustering. This fact must be kept in mind when analyzing the results and conclusions. For a comprehensive survey in complex networks see [Albert and Barab·asi, 2002].

3 HCR-Model Experimental Results

We use a graph classi�cation based on the clustering coef�- cient, regular and small-world graphs will be called highlyclustered graphs, and scale-free and random graphs will be called low-clustered graphs. For the sake of clarity we did not include results on random graphs in the �gures, since they behave like scale-free graphs.

Let us stress which are the key manipulations in the parameters of our model. We systematically variate the proportion of agents who initially adopt the convention B (rB), the ef�ciency gap α between the two conventions, and �nally, the type of network, in particular its clustering coef�cient, that de�nes the agent's neighborhood.

Another thing to mention before getting into the details is that there are two clear phases: 1) all the replications converging to A, and 2) all the replications converging to B. There is as well a space between these two phases where the system converges, with some replications to A and some to B, which we call transitional space, that is wider or narrower depending on the underlying topology and α. There is a critical point r∗B that sets the boundaries between the two phases; and the transitional space may be de�ned with an ε, such that the result is: r∗B ±ε.

Now, let us comment the results of the experiments on the HCR model. It is helpful to �rst consider the case where both conventions are equally ef�cient (α = 1), which is the case of a pure coordination game. The results for this case are displayed in sub-�gure 2.a. When the initial number of agents playing B is less than the half of the population, that is, rB < 12 , the system ends up establishing the convention on B. And, when rB > 1 2 the convention on A is established. The sub�gure shows in particular that this result is widely independent of the network topology. It also shows that the transitional space is very narrow except for the regular graphs.

This pattern changes when convention differ in ef�ciency. Sub-�gures 2.b and 2.c show the case where the payoff for action A exceeds the payoff for B (α > 1). To understand the results, consider an example. Let 34 of the population follow the actionB, and 14 follow the actionA. In this case, although B is the initially chosen action for most of the agents, coordination in A is more ef�cient since it yields a better payoff. Thus, which will be the �nal convention agreed by the whole population? The answer depends on 1) how much better off, more ef�cient, is the action A over B, denoted by α. And 2) the underlying topology. If α = 3 2 (sub-�gure 2.b) the �nal convention will be B when the underlying topology corresponds to a random or scale-free graph, A when having a regular graph, and can be both when having a small-world graph. By increasing the ef�ciency of coordination on A to α = 2 (sub-�gure 2.c) both small-world and regular graph converge to convention A, whereas random and scale-free graph still converge to convention B. The explanation behind the result is striking, low-clustered graphs seems very sensitive to the initial population density, whereas highly-clustered graphs behave in the opposite way, they are more sensitive to the ef�ciency of a particular action.

The conclusion derived from these results can be summed up as follows: low-clustered agent communities where a convention already exists will not be infected by a set of agents who play a new action, even though it is more ef�cient. Conversely, highly-clustered agent communites can be infected by a new action if the new action is more ef�cient, replacing the current convention for the convention on the ef�cient action.

Therefore, highly-clustered agent communities are more innovative, or adaptive, since a new action can be spread and �nally established as a convention. The drawback would be that this community would be unstable due to its receptiveness to new action, and in the transient time needed to reach a stable new convention no coordination will exist. In contrast, low-clustered agent communities are very stable since the infection with a new convention is unlikely to happen, but on the other hand they are reluctant to adopt new actions even though they are more ef�cient, thus, becoming very conservative and static communities. We must remark that studies on empirical social networks have shown that these networks are very clustered [Albert and Barab·asi, 2002].

We do not provide a proof of the system's convergence. Nevertheless, throughout all the simulation runs, with their corresponding replications, the system has always converged to a convention with an upper bound of O(N 3 ).

On �gure 3 (left), α is set to 1, therefore both conventions are equally ef�cient. It can we observed that the regular graph takes much longer to converge than the rest of graphs, which is completely consistent with the �ndings of [Kittock, 1993] and [Delgado, 2002]. Notice the existence of peaks in rB = 12 in all the graphs except regular. These peaks are close to the critical point r∗B = 12 where the transition takes place. This is a typical behavior, when the system is close to a transition boundary it takes longer to converge [Yeomans, 1992]. The regular graph, however, is a particular case since it shows a plateau rather than a peak. This is due to its wide transitional state, in which different replications of the same setting can converge to different conventions.

On �gure 3 (right) the convention A is more ef�cient that convention B, since playing action A yields payoff α = 2, when playing action B yields a payoff 1. In this case the plateau of the regular graph does not appear because its transitional space narrowed as shown in �gure 2.c. Thus, we see only the peaks in rB where the transition takes place r∗B = {.6, .85, .90} for scale-free, small-world, and regular graphs respectively, which correspond to the transitions observed in �gure 2.c. Again, we observe that the convergence is more inef�cient in time when the initial rB is close to r∗B . It is important to remark that the regular graph has improved its ef�ciency in reaching the convention, that is, it is more ef�cient than the small-world graph when α = 2. As was shown by [Young, 1999], convergence to a risk-dominant equilibrium, which in our case corresponds to the paretoef�cient one, is surprisingly rapid provided a close-knit (clustered) graph. The scale-free graph is always the most ef�cient graph in terms of convergence no matter α, however, scalefree graphs do not allow convergence to the ef�cient convention unless the initial number of agents playing A is very big, 40% compared to the 15% needed with a small-world graph, with α set to 2).

4 Analytical Model

First of all, we replace the role of past interactions stored in agent i's memory (Mi) by the current state of agent i's neighbors; notice that in our model we set the memory size to the average connectivity, M = 〈k〉. Instead of applying the HCR-rule over Mi we will transform it as follows: Let us take kS as the number of neighbors in the same state as agent i, and kS the number of neighbors in the opposite state. Therefore, the update is performed if kS > φkS, where φ is the payoff yield by the payoff matrix G when playing (S, S). Therefore, the switch from playing A to play B is done when kB > αkA, since G(A,A) = α. Similarly, the switch from playing B to play A is done when kA > kB, since G(B,B) = 1. The probability of updating the state is de�ned by equation 1, we decided to introduce some stochasticity to compensate the fact that now the update is calculated by the current state of the neighbors instead of by the interactions, as the HCR-rule does.

We will use what in physics is called a mean-�eld argument [Pastor-Satorras and Vespignani, 2001]. Let NB(t) be the number of agents playing action B at time t, and ρ(t) = NA(t) N be the density of agents playing B. A �rst approach is to assume the following homogeneity condition: for every agent with k neighbors, the number of neighbors in state B is kB(t) ≃ kρ(t). This condition is completely ful�lled for random graphs, and approximately ful�lled for scale-free and small-world graphs (when p → 1). Nevertheless, this homogeneity condition is not ful�lled for regular and for small-world graphs for low values of p. What breaks the homogeneity is the clustering coef�cient, for low-clustered graphs this condition holds since the global density of agents in state S corresponds to the proportion of neighbors in state S. Intuitively, the clustering coef�cient can be de�ned as the probability that a node i and a node j have a link provided that node l has a link to both i and j. Thus, when clustering tends to 0 the node's neighborhood is a good sample of the graph. However, when clustering coef�cient is high the node's neighborhood is not a sample of the graph, since its neighbors form a clique, a close-knit group. Therefore, we propose a new homogeneity condition that takes clustering (cc) into account. Let us de�ne cc as the clustering coef�- cient, provided that cc is the probability of agent l's neighbors being also neighbors, (1 - cc)k is the number of neighbors which are not in the l's clique, and to whom the previous homogeneity condition holds. Therefore, for an agent playing A with k neighbors, the number of neighbors in the opposite state (B) is kA ≃ (1 - cc)kρ(t), which is the cc-biasedhomogeneity condition.

Now we can write an equation for the evolution of ρ(t). First, notice that the variation of ρ(t) after a small time interval ∆t is proportional to ∆t, that is, ρ(t + ∆t) = ρ(t) + ∂ρ(t) ∂t ∆t+O(∆t2 ). Then, we can neglect the O(∆t2 ) term (since we perform a continuum approximation ∆t → 0) and compute the variation of ρ(t) as the balance between the agents switching from action A to B and the agents switching from action B to A. On one hand, the fraction of agents in A (that is, 1 - ρ(t)) that change to state B in a time interval ∆t is the product (1 - ρ(t))f(ρ(t))∆t, provided ∆t is small enough; on the other hand, the fraction of agents that switch from action B to A in ∆t is ρ(t)f(1 - ρ(t))∆t, also for small

∆t. Thus after ∆t → 0, the mean-�eld equation for ρ(t) can be written as

After substitution of fβ,φ to which the cc-biasedhomogeneity condition has been applied. And setting β = 〈k〉 and φ = (S, S) the equation reads

We want to study the stable �xed points of 3 since these will give us information on the �nal state of the system. Thus we must �nd the solutions of ∂ρ ∂t = 0. As we can see in 4, stable �xed points are ρ∗ ∼ 0, and ρ∗ ∼ 1 (these have been computed numerically) and the unstable �xed-point lies in (0, 1). In table 1 we display the unstable �xed points of the density equation, which are possible critical points of the HCR model provided our assumptions (see above) are correct. Furthermore, in table 1 we �nd a comparison between the analytical unstable �xed points and those critical points coming from the simulation of the HCR model. Notice that the plausibility of the simplifying assumptions behind our analytical model is supported by the agreement between analytical and experimental results (remind that rB was sampled with a resolution of .05).

Figure 4 shows the variation in ρ, △ ∂ρ ∂t , for different α and cc. We can see the effect of α enlarging the basin of attraction of convention A. On the other hand cc has the effect of reducing the amount of variation due to the effects of the cc-biased-homogeneity condition. Consequently, the time elapsed to reach a convention will be longer, and �uctuations in initial conditions will have a bigger impact. As a matter of fact, the experimental results on the HCR model show us these two consequences apply for highly-clustered graphs such as the regular graph. The convergence time is much higher compared to non-clustered graphs. And the transitional space, where the system can converge either in B or in A for the same initial parameters, is wider.

5 The Role of Imitation

In this section we will modify the model based of the HCRrule introducing an imitation propensity iS , which is the probability that, after a dyadic interaction where at least one agent was playing action S, both agents end up playing action B regardless of the HCR action updating rule. By introducing an imitation propensity we model the effect of having an attractive action which more likely to be chosen. Imitation is considered as the key factor of the adoption of norms, and by extension, conventions. How does the existence of an attractive action affect the �nal convention reached by the agents? And what if the attractive action happens to be sub-optimal? In our model coordination on action A is most ef�cient solution (if α > 1), however, action B (if iB > 0) might become a better replicator since it can be adopted by imitation as well as adopted by the learning process (HCR-rule).

The effect of iB heavily depends on the clustering of the underlying topology. For instance, when α = 2 and iB = .4 the clustered communities adopts the attractive convention (B) over the ef�cient one (A) regardless of the initial density (rB), while non-clustered communities will still adopt A provided rB < .25. Therefore, it might be derived that non-clustered communites are more resilient against attractive conventions in favor of ef�cient conventions. This result would seem to contradict the previous claim, that clustered communites are better off in converging to the ef�cient convention. However, when iB is small enough, for example when iB = .1 the opposite effect is observed, clustered communities keep on converging to the ef�cient convention regardless of the initial density of agents. This two-fold behavior is perfectly clear in the case of the regular graph (left column of �gure 5). There is a threshold i∗B under which the system ends up in the ef�cient convention, and over which the system ends up in the attractive convention. For example i∗B = .2 when α = 2 and the underlying topology is the regular graph. Notice, that this threshold is not found in the case of the small-world graph whose clustering coef�cient is high, although not so high as the case of the regular graph. However, even without the threshold we observe a similar behavior than in the regular graph although more progressive. If we compare it against the behavior of low-clustered graphs, we �nd again that the system is more resilient to the attractive action invasion for low values of iB. For high values, on the contrary, the system is very receptive to an invasion of agents playing the attractive action. We must state that the model is interesting for small values of iB, for high values of iB the dichotomy of the agent to choose between the ef�cient or the attractive action dissapear and becomes an epidemic spread model [Pastor-Satorras and Vespignani, 2001].

6 Concluding Remarks

Our research aimed to identify conditions under which local interactions in a multi agent community can give rise to an ef�cient convention. We have shown that the key factor is the clustering of the underlying agent's social network. When communities are highly-clustered the system converges to the pareto-ef�cient action even though the initial population choosing that action was clearly a minority. This suggests that the ef�cient convention is a stable convention because it cannot be invaded by a set of agents playing another suboptimal action. However, a sub-optimal convention can be replaced by a set of agent playing an action that yields a better payoff. Accordingly, when the clustering coef�cient is high the system always converges to the most ef�cient convention and this convention is stable. On the other hand when clustering tends to zero the adopted convention depends solely on the density of agents following an action. If the majority of agents play the sub-optimal action the inef�cient convention will be established, and it will be stable. To back up our �ndings, we provided an analytical approximation that reproduces the results observed in our model based in the HCRrule. To do so, we had to introduce a new homogeneity condition which let us work in clustered graphs, where the classical mean-�eld homogeneity condition is not met.

In accordance with the strong functionalism thesis from classical sociology, we found that in certain graphs the agent system was capable to �nd and maintain the optimum in the stable state. However, this only applies to highly-clustered communities, which resemble many empirical social networks. At the same time, our model also corresponds in two respects to the view that rational choice theorists in sociology take on social norms. First, we have shown that global ef�ciency arises from individual goal oriented actions. Second, we found that under certain conditions optimizing individual actions fail to generate socially ef�cient outcomes, a problem that is central to the contemporary discussion about the emergence of conventions and norms.

To conclude, our results seem to correspond more with a rational choice on norms than with the strong functionalism thesis. We have shown that socially optimal conventions can arise from individual optimization, but there is no guarantee that this happens. In this sense, our model matches well the ample evidence of examples of suboptimal conventions, for example in market processes. We believe that a part of the explanation for this may lie in the competition between optimizing and imitation that we have addressed with our model. We have shown that imitation processes make it possible for a sub-optimal yet attractive action to overthrow the ef�cient action, and become stable, provided that its attractiveness is high enough to be worthy of imitation.