Modeling the Emergence and Convergence of Norms

1 Introduction

Many aspects of daily life are governed not by laws or moral injunctions but rather by norms. Norms or conventions routinely guide the choice of behaviors in human societies and plays a pivotal role in determining social order [Hume, 1978]. Norms serve to simplify and regularize much of the complexity of the world around us [Lewis, 1969]. Norms typically become codified into law, but do not start out that way. An example of a norm might be deciding to always drive on either the left side or the right side of the road. The important characteristic of a norm is that it guides behavior where moral or rational reasoning does not provide clear guidance. Norms may also form in contexts where rational choices cannot be applied because of the myopic behaviors and the limited processing abilities of individuals. Consequently, such norms may prove to be suboptimal.

The systematic study and development of robust mechanisms that facilitate emergence of stable, efficient norms Sandip Sen Tulsa, Oklahoma, USA

University of Tulsa sandip@utulsa.edu

via learning in agent societies promises to be a productive research area that can improve coordination in agent societies. Correspondingly, there has been a number of recent, mostly empirical, investigations in the multiagent systems literature on norm evolution under different assumptions about agent interaction frameworks, societal topology, and observation capabilities [Delgado et al., 2003; Kittock, 1994; Sen and Airiau, 2007; Shoham and Tennenholtz, 1997], There is an associated need to develop analytical frameworks that can predict the trajectory and dynamics of emergence and convergence of society-wide behaviors [van Dyke Parunak, 2002].

Toward this end, we mathematically model the emergence of norms in societies of agents who adapt their likelihood of choosing one of a finite set of options based on their experience from repeated one-on-one interactions with other members in the society. The goal is to study both the process of emergence of norms as well as to predict the likely final convention that is going to emerge if agents had preconceived biases for certain options.

2 Related Research

Recent literature in multiagent systems show a significant increase in interest and research on normative systems. Norms or conventions can be substituted as external correlating signals to promote coordination. These aspects of norms or conventions have merited in-depth study of the evolution and economics of norms in social situations [Epstein, 2001; Posch, 1995; Young, 1996].

Norms can also be thought of as focal points evolved through learning [Young, 1996] that reduce disagreement and promote coherent behavior in societies with minimal oversight or centralized control [Coleman, 1987]. Norms can therefore have economic value to agents and help improve their efficiency.

While some research on norm emergence assumed uniform interaction probabilities between agents [Sen and Airiau, 2007; Shoham and Tennenholtz, 1997] others have studied the effect of topologies of agent relationships [Delgado et al., 2003; Kittock, 1994]. This body of research can be further divided into interaction-based learning [Sen and Airiau, 2007] versus observation-based adoption approaches to norm emergence [Delgado et al., 2003]. In the interaction-based learning mode, agents learn utility estimates of their behavior choices and over time converge on a particular behavior that becomes the norm in the society. In this mode, agents actually do not even need to observe others' behaviors, and agents over time adopt biased behaviors trial-based on their own experiences of what produces higher utility. In the observationbased learning mode, agents' behaviors must be fully observable and typically there is no direct consideration of utilities. The basic idea is to adopt behaviors of successful individuals.

3 Agent InteractionModel

We first characterize our model of agent interactions that drives the emergence of conventions in the society. Consider a population of n agents, each of which is capable of performing two distinct actions. Pairs of agents are randomly selected to interact. In each interaction, each agent selects one of its two available actions based on their current biases. The goal for the agents is to coordinate by selecting identical actions, but they cannot communicate or negotiate beforehand to coordinate their action choice. Based on the outcome of their interaction (coordination for identical actions or conflict otherwise), agents adjust their biases for their selected actions. For the purposes of our formal analysis, we can consider each bilateral agent interaction to consist of three phases: pairing of agents, action selection, and bias revision.

In our model, an agent i contains a single value, pi, representing the bias or probability of selecting action 1 (this model can be expanded to include a vector of size m- 1 for if agents could choose from m different actions). Agent i selects the other action with the complementary probability, (1-pi). At each time step, l agents are randomly selected to interact with each other; based on the outcome of the interaction, each agent i chosen to interact will change its p value by no more than some constant x using a predefined update rule.

Consider the scenario of a society of agents choosing over time to adopt a convention of driving on the right or left side of the road. Each agent can choose one of two actions: an action value of +1 indicates that the agent will choose to drive on the right side of the road, while a value of -1 corresponds to driving on the left side. Let pti represent the bias or likelihood that agent i will choose action +1 at time t. We assume that all agents have the same initial bias: (∀i)(p0i = ¯ p0). At each time step, two distinct agents are randomly selected with uniform probability from the population. Each agent selected calculates a random number ri from U[0, 1] and chooses an action value :

.

If both agents in the pair choose the same action, both will positively reinforce the action that they chose and play it with greater frequency in the future. If their actions did not coordinate, then each agent reduces the frequency with which it plays the action that it chose at that time step. Mathematically, this can be expressed by:

where acttj is the action taken by the other agent in the pair, and Δi(acti) is an update function. We have used the two following update fuctions.

• Constant update rule: Δi(actti ) = x · actti , where x ∈ (0, 1) is a constant. This rule assumes that each agent will update its preferences in constant increments.
• Proportional update rule:

where β ∈ (0, 1) is a constant. This rule assumes that the agents that are less biased towards either action will be less willing to make large changes in their biases.

To aid our analysis and provide better insight into the norm emergence process, we will make some simplifications to the model. If 1/x is an integer and an agent is initialized with a p value that is a multiple of x, then we find that that agent's p value will always remain a multiple of x. If all the n agents have bias values constrained this way, then the population average, ¯ p = 1n ∑ni=1 pi, can only assume values that are multiples of xn , or nx +1 distinct values.

We can then predict the average convergence time and the final convergence value for a given population bias, ¯ p. Let P (¯ p) represent the estimated average convergence value for any population with a current average bias of ¯ p, and T(¯ p) be the expected number of time steps before converging. We ignore the corrections for values that fall below 0 or above 1. Consequently, we can express the value of P (¯ p) as a weighted average of the P values for all distributions that could be reached at the next time step:

where F(i, j) is the expected probability that a population with mean bias i · x/n will change its mean to j · x/n due to a single interaction. For the constant update rule defined above, this is equivalent to

In this expression, (1 - ¯ p)2 is the probability that two randomly selected agents will both choose to drive on the left side of the road (actti = acttj = -1) , ¯ p -2 xn is the resulting ¯ p value at the next time step, and P ( ¯ p -2 xn ) is the average value to which ¯ p will converge in this case. The second term, 2(1 - ¯ p) ¯ pP ( ¯ p), deals with the case in which the two agents do not coordinate and ¯ p does not change, since the increase in the bias value of one agent is exactly offset by the decrease in the bias value of the other agent. The last term corresponds to when the two agents coordinate and increase their p values.

A similar expression can be used for T(¯ p), with an additional term of 1 to represent the current time step.

We need some values of P and T to solve the system. Since ¯ p values of 0 or 1 indicate that the population has converged, we have definite values of P and T at these points: P (0) = 0, P(1) = 1 (everyone chooses the same action hereafter), and T (0) = T (1) = 0 (population already converged). The above equations for P and T form nearly-diagonal linear systems of equations, which can be solved in O(n/x) time and space to give a close approximation of the average convergence time and values obtained in the simulations. For the proportional update rule given above, discretization of the distribution of individual agent p values poses a significantly more difficult problem. However, a fairly accurate model can be obtained by discretizing the possible ¯ p values into m·n/x+1 intervals, where m is some positive integer constant. The average value over all agents of Δi(actti ) when actti = +1 is given by:

Similarly, the average value of Δi(actti ) for actti = -1 is Δ= -x(β + (1 - β)(1 - ¯ p)). If we use this average value of Δi for all agents, then we can write a set of relationships similar to those for the constant update rule:

As with the previous expressions, P(0) = 0, P(1) = 1, T(0) = 0, and T(1) = 0. These relationships can also be transformed into nearly diagonal matrices and solved in O(m nx ) time and space.

The expressions that we have defined for P and T have neglected any clipping effects for p values outside the interval [0, 1]. While these expressions provide a good approximation when all agents begin with the same p value, they lose accuracy when the initial distribution is more spread out. In order to incorporate the clipping effect into the model, additional terms must be added to the expressions for P and T . The modified expression for T (¯ p) is as follows:

where Z¯ p represents the proportion of agents with p values of 0, O¯ p the proportion of agents with p values of 1, R¯ p =

¯ p - O¯ p the probability that an agent with a p value other than 0 or 1 will choose to drive on the right side of the road, and L¯ p = (1 - Z¯ p - ¯ p) the counterpart for the left side of the road; Z¯ p +O¯ p +R¯ p + L¯ p = 1.

We also modeled situations where the initial agent distribution is symmetrically distributed about ¯ p0, e.g., half of the population has initial bias of ¯ p0 +σ and the other half has the initial bias of ¯ p0 - σ. When a population is distributed symmetrically about its mean, we note that Z¯ p + O¯ p increases when |¯ p-0.5| is larger (given a constant σ). Additionally, Z1 = 0 and O0 = 0. Given these facts, we estimate Z¯ p and O¯ p using the cumulative distribution function Φ of the standard normal distribution:

The standard deviation of distributions with ¯ p values near zero and one is assumed to approach σ + 2 ( 13 - σ) |¯ p - 0.5| (where σ is the initial population standard deviation). This is a somewhat arbitrary choice from many viable candidates; almost any scaling factor that would yield Z1 ≈ 0 and O0 ≈ 0 would have been appropriate.

4 Empirical Validation of Model Predictions

A mathematical analysis provides conceptual value only when it accurately models the underlying process in question. We now examine how well our analysis of the two-agent interaction problem corresponds to simulated interactions of agents a simulated population.

Figure 1 presents a comparison of our analytical computations and empirical observations of the average value to which a population will converge as a function of the initial mean bias. In these simulations, all agents were initialized with bias values identical to the mean, and the constant update amount is x = 0.01. Each data point represents the average over 100, 000 simulations or a prediction from the model.

Note that the mean always converges to 0 or 1. Inspection of the graph suggests that populations tend to converge to 0 when they have an initial ¯ p value less than 0.5, and to 1 when their initial bias is greater than 0.5, regardless of the other characteristics of the initial distribution. It is heartening to note that the theoretical predictions from our model almost perfectly match the empirical observations.

Figure 2 displays the average number of time steps required for convergence by populations with the given initial bias. Both the simulations and the model indicate that populations with initial means near 0.5 take the longest to converge. The model predictions for convergence times, though not as accurate as those for convergence values, are still effective approximations of simulation results.

Figures 3 and 4 compare the results for the model and simulation for the proportional update rule . In these figures we have zoomed in on the interesting transition region of initial bias in the range [0.49, 0.51]. For populations with initial means below 0.49, the average convergence value is approximately 0, and the average convergence time increases linearly with the initial population mean. Symmetrical results hold for populations with initial mean biases above 0.51, with the population always converging to 1. Like the simulations and model using the constant update rule, the maximum average convergence time is observed when the initial mean bias is 0.5. It is interesting to note that the range of initial ¯ p values for which a population is observed to converge both to 0 and to 1 in at least about 1% of simulations is [0.4, 0.6] for the constant update rule, but only [0.49, 0.51] for the proportional update rule. The fact that the model has accurately predicted the decrease in size of this interval provides further validation of the model's fidelity.

Next, we present results where initial population biases are symmetrically distributed about the initial population mean. Increasing the standard deviation of the initial distribution of population p values does not significantly impact the average final convergence value. It can, however, result in large increases in average convergence time for both of the update rules discussed. Figure 5 shows the average convergence time for an initial population of n = 100 agents, 50 having a initial p values of 0.5-σ, and the other 50 starting with p = 0.5+σ when the proportional update rule is used.

4.1 Proof of Convergence

The models discussed above accurately predict the frequency with which the populations converge to 0 and 1, and the time that it takes to get there. However, we want to ensure that the model does not overlook any other possible convergence values. We now present a proof that the population bias always converges to 0 or 1, which means that the model does consider all possible cases.

A distribution D represents a set of bias values for all members of a population. We call a set of distributions, C ∈ P ([0, 1]n), a "convergence set" iff C ̸= ∅ and ∀D ∈ C, S(D) ⊆ C, where S(D) is the set of all distributions that can possibly be reached at time t + 1 if a distribution D was present at time t. C is a "minimal" convergence set iff ∀C ′ ⊂ C, C′ is not a convergence set. Let D0 be the distribution in which all agents have p values of 0, and D1 be the corresponding distribution for p values of 1. The goal is to prove that {D0} and {D1} are the only minimal convergence sets. During this discussion, a population of n agents will be represented by the multiset ⊎ni {pi}, where pi is the ith agent's bias value.

Proposition 1: {D0} and {D1} are minimal convergence sets. Proof: For distribution D0, every agent has a p value of 0; at each time step, both agents selected will always drive on the left side of the road and will always coordinate. Both agents will attempt to lower their p values, but since 0 is the lowest possible, the only configuration that can be reached is D0. Thus S(D0) = {D0} and {D0} is a convergence set. The only proper subset of {D0} is the empty set ∅, which, by definition, cannot be a convergence set. Hence, {D0} is a minimal convergence set. We can also show that {D1} is a minimal convergence using similar logic. No proper super set of {D0} or {D1} can also be a minimal convergence set, by definition. Thus, no minimal convergence sets contain D0 or D1 except {D0} and {D1}.

Proposition 2: There are no minimal convergence sets other than {D0} and {D1} .

Proof: Suppose C is a convergence set such that D0, D1 /∈ C. Since D0 is the only distribution in C that contains all zero elements, every distribution in C must contain at least one non-zero p value. Similarly, from the absence of D1 we can conclude that there is at least one non-one p value in each distribution.

Let Clow = {D ∈ C : (∀D′ ∈ C)(¯ pD ≤ ¯ pD′)}. If Clow contains a distribution D01, ¯ p composed of all zeroes and ones, it must contain at least one of each: D01, ¯ p = {0, 1}⊎D01,rest, where D01,rest ∈ {0, 1}n-2. Thus D01, ¯ p - {0, 1} + {βx, 1 - βx} is in S(D01, ¯ p), Clow, and the next category of distributions. If Clow contains a distribution D with a non-one p value and another non-one, non-zero value, then S(D) ∋ D¯ pxn , a distribution with a lower ¯ p value than D that could result when the agents from D with these two p values are selected to interact with each other. However, C does not have any distributions with a lower mean than those in Clow, which contradicts the initial assumption that C was a convergence set. Thus, there are no minimal convergence sets except {D0} and {D1}.

4.2 Further empirical results

The following trends were observed from simulation runs, but were not approximated by our model predictions.

Consider a population in which the majority of agents usually drive on the left side of the rode while a minority always drives on the right. This type of skewed distribution exhibits different behavior than other distributions with the same mean. When the initial population mean is not close to 0.5, the skewness of the distribution does not significantly impact convergence statistics. However, when the minority subgroup has a strong bias towards one action while the majority subgroup has a weaker bias towards the other action such that the mean of the entire population is near 0.5, the skewness produces significant effects on both the average convergence value and time. Increasing the standard deviation of the initial distribution will magnify these effects. Figures 6 and 7 show the convergence statistics for an initial population of 100 agents, m of them with initial p values of 0.5+0.5 100-m 100 , and the other 100-m starting at 0.5-0.5 m 100 . These results can be approximated by our model using P and T , but only if detailed information about the shape of the distribution at various times can be provided. For initially symmetric populations, we were able to approximate the distribution at any time with a normal distribution, and achieved good results. However, no such simple estimation can be made for skewed distributions.

When the constant update rule is used, ¯ p will generally follow an exponential relationship with time. However, when the population nears convergence, the rate of change of ¯ p decreases. This can be attributed to the increased frequency of events in which agents must adjust the changes in their p values so that they still lie in the interval [0, 1].

When the proportional update rule is used, the average p value is characterized by short intervals of rapid change alternating with long intervals with only minimal oscillations in ¯ p values. During these long intervals, when ¯ p is almost constant, the individual agent p values are polarized to either endpoint of their domain, [0, 1], and, like the average, only exhibit small oscillations. This phenomenon can be explained by the fact that, if an agent's p value is near 0, several increases in its p value can be offset by only a small number of decreases, due to the proportionate nature of Δi(acti). Figure 8 shows the average population bias over time for a typical simulation using the proportional update when all agents are initialized with biases of 0.5. Our model is unable to predict when these sharp drops in p values will occur.

5 Conclusions and Future Work

We developed a formal model to predict the convergent norms and the time taken for such norms to emerge in a population of agents adapting their biases for one of two choices based on success or failure of coordination in bilateral interactions. This analysis covered several variations of the initial state of the society and the bias update rule used by the agents. Our model predictions for both constant and proportional bias update schemes were validated by empirical results from a large number of simulations. In addition, we proved that a population using one of these two update rules will almost surely (that is, with 100% probability) converge on one of a small set of norms.

The analysis presented in this paper establishes a broad foundation for several types of subsequent work. While the matrices used to predict convergence statistics were nearly diagonal and thus could be scaled to model much larger populations, it would be ideal if closed-form expressions could be produced to express convergence statistics in terms of initial population characteristics.

We would also like to develop a better understanding of how increasing diversity in the population impacts convergence time. In a similar vein, skewness in the population could have unanticipated effects on convergence and we would prefer to gain insights into those effects through a more expansive analysis. We would also like to extend our analyses to other norm-emergence scenarios. Apart from different interaction schemes, we would also explore larger action sets, more complicated l-way interactions, and different network topologies.