A Model for Collective Strategy Diffusion in Agent Social Law Evolution

1 Introduction

Coordination is the key to develop realistic multiagent systems [Kraus, 1997][Jiang & Jiang, 2005]. The concept of artificial social system is presented by [Shoham and Tennenholtz, 1995]; their basic idea was to add a mechanism, called a social law, into the system to realize coordination among agents. Each agent initially has its own strategy, and the different strategies may produce conflict. Therefore, to realize a harmonious agent system, we will need to endow a set of social laws that can be accepted by most agents. A set of social laws represents restrictions on final agent strategies. Previous work on artificial social systems [Shoham & Tennenholtz, 1997] [Shoham and Tennenholtz,1995] [Fitoussi and Tennenholtz, 2000] [Boella and van der Torre, 2005] made no systematic analyses on the evolution of social laws from individual social strategies, and the social laws were created off-line. Therefore, the social laws described in previous work are always fixed, and so fail to yield dynamic agent systems.

This paper presents that social laws aren't fixed over the system's lifetime. A social law represents an island of stability and can be overwhelmed and replaced. In the framework presented by this paper, agents start with their individual social strategies; the social strategies can diffuse and be accepted in part or in full by others. The emergence of a new dominant social strategy represents the emergence of a new social law.

We initiated a study on how to evolve individual social strategies to global social law through hierarchical agent diffusion [Jiang and Ishida, 2006][Jiang and Ishida, 2007]. In our original model, each agent has its own social strategies at the first stage of the system; for simplicity we restrict the discussion to just one action/belief. Further, we assume that the agents possess "social rank" and the ranks are known by all agents. As the system runs, the strategies of superior agents will tend to diffuse (be adopted by or accepted by) the junior agents. Given the right conditions and enough time, a global social law may be finally established. A simple example is given below:

Two businessmen enter the same conference room. One starts to smoke but the other complains. Upon learning that the smoker has a higher position in the same company, the complainer changes his strategy of "smoking is not permitted" to "go ahead." This means that the social law in the conference room has become "smoking is permitted". [Scenario 1: diffusion by rank]

Only the diffusion of the social strategies of superior agents to junior agents was considered in [Jiang and Ishida, 2006][ Jiang and Ishida, 2007]. However, such a situation is not truly representative of reality. In real society, there are so many collective intentions and practices [Balzer and Tuomela, 2003][Pacheco and Carmo, 2003], and the social strategies shared by many junior agents can also influence the superior agents. The following example demonstrates this:

You like smoking very much and you occupy the highest position in your company. However, if all other members dislike smoking, you will probably stop smoking, i.e. your social strategy has been trumped by that of the majority. Therefore, the social law of your office is now "no smoking".

[Scenario 2: diffusion by numbers]

The interplay between rank, strength of strategy support, and the numbers of supporters is extremely complex. The emergence of a social law may not prevent some agents from maintaining their original strategies or indeed adopting contra-strategies. For example:

None of the employees in an office like smoking; so the social law in the office is "no smoking in the office". The boss starts a long discussion with the employees. The boss has a habit: he likes to smoke while giving orders to the staff. Therefore, the boss will smoke even though the social law is "no smoking in the office". [Scenario 3: persistence of outliers]

In such a scenario, the outlier agent has a very high social position; so its corresponding social strategy may have high dominance though the number of overlaid agents is few (just one in this case).

All three scenarios are common in real world social strategy diffusion. We think that the dominance of a social strategy is determined by the numbers and ranking of its supporters relative to those of other strategies. A strategy becomes more dominant as the number of adopters increases and/or their ranking increases. The success of a social strategy supported by many junior agents over the social strategy of superior agents can be called collective insurgent diffusion; the reverse is called collective elite diffusion.

In this paper, we explore how a social strategy can diffuse among agents. Our model is explained using the example of crowd orientation.

2. An Example and Related Concepts

2.1 Social Strategy in Queue Orientation

To explain our model, we use the example of an agent system that reproduces a crowd of strangers standing on a soccer field. At the initial stage, the orientation of each agent (its strategy) is quite random. What we are looking for the emergence of a social law; most agents face the same direction.

Each of the n agents can stand with one of the 8 orientations, see Figure 1 (a). The social strategy of an agent is its orientation. Let n be the number of agents, we can use an array to denote the social strategies of agents. {1, , 8} ,1 i s i n , represents social strategy (i.e. the standing orientation) of agent i. The social strategies of the agents in (b) are shown as (c). Obviously, the standing orientations of the agents in Figure 1 (b) are disorderly.

Since our example consists of strangers, now we may replace explicit social rank with age. For example, if agent c looks older than e, then e may change its orientation to match that of c. If agents b and d share the same orientation, c may not be able to overcome their numerical advantage. At this time, c may change its orientation to match theirs. Let us examine the emergence of social laws. We consider five agents a, b, c, d and e, which have the same social rank. If a and b have the same social strategy, sab, but the social strategies of the other three agents are quite different, then the social law can be written as "all agents are under pressure to follow strategy sab". As time goes by, if c, d and e happen to establish the same social strategy, scde, the social law would change to "all agents are under pressure to follow strategy scde".

The situation becomes more complex if the agents do have explicit social rank. For this situation, we will need to balance the influence of rank against the weight of sheer numbers. Next we will give some related concepts to explain the collective diffusion.

2.2 Dominance of Social Strategy

If a social strategy is accepted by many agents, its dominance will be strong. However, different agents will contribute different amounts to the dominance of a social strategy. A superior agent strengthens a strategy's dominance far more than a junior agent. To allow for comparison, we equate the dominance of a social strategy to its rank. The concept of rank is used often in the web search field to denote the importance of web pages [Haveliwala, 2003]. Now we use it to represent the relative dominance of social strategies.

Definition 2.1 Social ranking of agent i can be a function: [0, ] i p , where is a natural number. i j p p i has superior rank to j. The set of the positions of all agents in the system can be denoted as: [ ], 1 i P p where i n , and n denotes the number of agents in the system.

In this paper, our basic idea is: if agent a has a social strategy s, a is implicitly conferring some importance to s. Then, how much importance does an agent a confer to its social strategy s? Let Na be the number of social strategies of a and pa represent the social rank of a, agent a confers pa / Na units of rank to s. As for our instance, the number of social strategies of an agent at one time is only one, therefore, agent a confers pa units of rank to s.

2.3 Overlay Group of A Social Strategy

The agents that share a social strategy are called the overlay group of th strategy. For example, in Figure 1 (b), agents b and d share social strategy 4 and so form one overlay group. Let G(s) represent the overlay group of social strategy s, we have:

(2.1) ( ) { | } s G s u agent u accepts the social strategy s Obviously, the rank of a social strategy is determined by its overlay group. Let G(s) be the overlay group of social strategy s, the rank of s can also be defined as:

As noted above, in our example agents can hold only one social strategy at any one time, and so can only contribute to the dominance of only one social strategy. The rank of social strategy s can be simplified to:

From Equations (2.2) (2.3), we can see that the rank of a social strategy is determined by the number and social ranks of the members of its overlay group.

The diffusion strength of social strategy s is the monotone increasing function of its rank, i.e. the higher Rank(s) is, the higher the diffusion strength is. Let the diffusion strength of social strategy s be represented as S(s), we have:

Where is a monotone increasing function.

To simplify the question, we can directly use the authority of a social strategy s to represent its diffusion strength. Moreover, we will use the concept of group rank to represent the social strategy rank, i.e.

2.4 Distance between Agent and Overlay Group

It is very simple to compute the distance between two agents, but not the one between an agent and a group. As stated above, each agent in the group strengthens the dominance of the strategy to a different extent. Therefore, we introduce the factor of social rank into the definition of the distance between an agent and a group as follows:

Definition 2.2 If d(a,u) denote the distance between agent a and agent u, |G| denote the number of agents in group G, pu denote the social rank of agent u, then the distance between agent a and group G can be defined as:

2.5 Difference of Two Social Strategies

In this paper, the angular difference of two agent orientations is used to represent the difference in their social strategies. Therefore, we have the following definition:

Definition 2.3 The difference of two social strategies i and j can be defined as the angular distance between their respective orientations:

For example, the difference between social strategy 1 and 7 is 2, and the difference between social strategy 3 and 4 is 1.

3. The Collective Diffusion Model

3.1 Diffusion Impact Force from Overlay Group to Agent

The impact force from an overlay group to an agent is determined both by their distance and the group's dominance (i.e. the dominance of the corresponding social strategy). Therefore, we define the impact force from overlay group G to agent a as:

Where f is a monotone increasing function, 1 and 2 are parameters to determine the relative importance of the two factors. From Equation (3.1), we can see that the nearer the agent is to the group and the higher the group's rank is, then the great the impact force of the group is on that agent.

3.2 Counteracting Force from Agent to Overlay Group

Based on real-world observations, if agent a is not a member of overlay group G, a will instinctively counter such influence. The counteracting force from agent a to overlay group G is determined by the following factors: 1) the social ranking of agent a, 2) the average social rank of overlay group G, 3) the distance of the social strategies (i.e. the standing orientations) between agent a and overlay group G. The higher the social rank of agent a is, the bigger the difference in social strategies is, the lower the average social rank of overlay group G is, then the more agent a resists adopting the social strategy of overlay group G. Therefore, if we let the social strategy of agent a be s1 and the social strategy of overlay group G is s2, we define the counteracting force from agent a to overlay group G as:

Where g is a monotone increasing function, 1 and 2 are two weighting parameters.

3.3 Collective Diffusion Criterion of Social Strategy

The collective diffusion criterion of agent social strategy needs to consider both G a IF and a G CF . The more G a IF is and the less a G CF is, then the more likely it is that agent a will adopt or move towards the social strategy of group G. Therefore, we use the ratio of G a IF to a G CF as the diffusion criterion. If the ratio exceeds a predefined value, then the social strategy of agent a will change by some amount.

We can predefine two parameters and according to the actual situation being simulated. If the value of / G a a G IF CF is more than , the social strategy of a will completely switch to that of G. If the value of / G a a G IF CF is less than but more than , then the social strategy of a will change to some extent but not equal that of G. While the value of / G a a G IF CF is less than , the social strategy of a remains unchanged.

Let the social strategies of G and a before diffusion are m and n respectively, 1 , 8 m n . Ifm n , the change of the standing orientation of a will be clock-wise; ifm n , the change of the standing orientation of a will be anticlock-wise. Therefore, the diffusion criterion, i.e. the change criterion of the social strategy of a can be defined as:

Where ' a s is the new social strategy of a after one step in the simulation.

3.4 Goal Function of Diffusion

Several social strategies may exist even after the diffusion process reaches equilibrium. Simulating actual situations will demand that we set different goals for the diffusion results.

For our example of crowd orientation, we may want to identify the conditions under which all agents finally adopt the same orientation. Moreover, the social laws are always established according to the more dominant social strategies. Obviously, the more agent numbers the dominant social strategies are accepted by, the more rational the established social laws are. Such assumption is also practical in realworld situations, e.g., the law should be established to satisfy the needs of most people in the society.

Therefore, we define the performance criterion of diffusion as a measure of the winnowing of social strategies.

Let NS be the number of social strategies in the system after diffusion, | ( ) | G s be the agent number in the overlay group of social strategy s, then the performance criterion of the diffusion can be defined as:

Higher values of PS indicate that fewer social strategies have survived and also show that better diffusion performance can be gotten.

3.5 Diffusion Progress

In the diffusion progress, the social strategy with the strongest dominance will firstly diffuse to other agents that belong to the other social strategies' overlay groups. After that, the social strategy with second strongest authority will diffuse to other agents that belong to the agents with more junior authority social strategy, …., until there are no diffusions take place.

Let A be the agent set of the system, sa be the social strategy of agent a, the diffusion progress can be shown as Algorithm 1.

Algorithm 1.

Input S; /*the initial set of social strategies of the system*/ SL={1, 2, …, 8}; Do { ' SL SL ; ' A A While ' SL is not empty {Select the social strategy with strongest dominance from SL ' : s ; Do {For ' ( ) a A G s If ( ) ( ) / G s a a G s IF CF { ( ) ( ) { } a a G s G s a ; ( ) ( ) a a a Rank s Rank s p If ( ) {} a G s then { } a SL SL s ; Compute ' a s according to Equation (3.3); ' ' ( ) ( ) { } a a G s G s a ; ' ' ( ) ( ) a a a Rank s Rank s p ;} } until the PS doesn't change any more; ' ' { } SL SL s ; ' ' ( ) A A G s ;}; } Until the PS doesn't change any more; Output S and PS.

4. Case Studies

We examined several cases to demonstrate and test our model. Figure 2 is one such case. From the ranks of social strategies, we can see that the social strategy 3 has the strongest dominance. So we compute the / G a a G IF CF between other agents and the overlay group of social strategy 3. The distribution of / G a a G IF CF is shown as Figure 3. As a trial, we set and to 10 and 4, respectively. This yields diffusion from G(3) to other agents according to Equation (3.3) and Algorithm 1, the progress of diffusion is shown in Figures 4-6. PS does not change from Figure 6, so diffusion process is finished. The total number of diffusion steps is 3.

From Figure 6, we can see that the standing orientations of all agents are identical after three diffusion steps, except for the agent in the bottom right corner.

Next, we change the values of and . At first we decrease them step by step for 4 cases, and then increase them step by step for another 4 cases. The diffusion results are given in Table 1. From Table 1, we can see that more steps are needed to reach diffusion termination when and increase. Therefore, we should set and to match the actual situation being simulated.

5. Discussion and Conclusion

A social strategy accepted by many agents will have high dominance and may diffuse to other agents. The dominance of a social strategy is determined by not only the number of adherents but also their social positions. That is, a superior agent strengthens the dominance of a social strategy drastically, while the addition of many junior agents can also strengthen the dominance of a social strategy.

This paper presents a collective strategy diffusion model in agent social law evolution. The model shows us that the social strategy of a superior agent may be changed by the social strategy shared by many agents, which is an example of collective insurgent diffusion. Section 4 showed that it was possible for one agent of quite high rank to retain its social strategy even after all other agents have adopted the same social strategy, i.e. the counteracting force of the lone agent overrides the collective diffusion force of all other agents. Moreover, if we increase the social rank of the lone agent significantly, it is possible that its social strategy will diffuse to all other agents, which is an example of collective elite diffusion.

We note that real world situations are often characterized by multiple strategies. For example, a commanding officer may walk among his troops in formation, and so has a completely different orientation to everyone else. The troops understand the situation and so unify their own orientation and do not blindly track the officer's orientation. In another simple example, the commander has an absolute power and can order all soldiers to follow his direction; the soldiers have to obey the order.

Though we explained our formal framework using the example of crowd orientation, it offers strong generality. The framework and algorithms described are quite general and can be applied in many other cases simply by making small adjustments.

Our agent social strategy diffusion model is based on the diffusion of strategy from collective agents to one agent step by step. This involves significant time costs when the number of agents is large. Such a diffusion model may be practical in some real-world situations, however, which are not fully representative of reality as a whole. In real-world situations, there are many concurrent diffusion movements between groups. Therefore, in our future works, we will explore the concurrent diffusion from collective agents to collective agents.

Acknowledgements

This work is supported by JSPS Research Grant No.1705282.