6.1 Agent level identification

The approaches in this section are all based upon individual agents reasoning about the existence of norms. Although they may observe other agents and communicate with them, the actual inference is performed by a single agent. Existing research in norm identificationFootnote ⁷ mostly concentrates on newcomer agents ignorant of the norms within a society learning those norms. These are, of course, not new norms emerging in the system. However, we suggest that these approaches should also be able to detect newly emerging norms before they are fully established since the case where an agent is trying to infer an existing norm (that it is unaware of is) is similar to the case where it is trying to infer an emerging norm. Therefore, it is those approaches that we focus on in this section.

Savarimuthu and Cranefield (Reference Savarimuthu and Cranefield2011) identify three ways that an agent can identify norms. First, experiential methods, where the agent performs behaviour and is punished if it violates a norm; second, communication methods, where the agent is explicitly informed of a norm by other agents, or system artefact (such as a list of rules); and third, where it infers the existence of a norm by observing other agents either violating a norm and being punished, or consistently avoiding some possible behaviour.

For example, consider a norm against walking on the grass in a park. If an agent unfamiliar with the norm enters the park, it may learn of the norm in the following ways. If it steps on the grass and is punished, then it has learned experientially. If it reads a sign saying, ‘Do not walk on the grass’, it has learned via communication. If it sees another agent being punished after walking on the grass, it has learned by observation. Finally, if it notices that no other agent walks on the grass then it may infer that it is prohibited by a norm, also by observation.

Andrighetto et al. (Reference Andrighetto, Campenni, Cecconi and Conte2010a) simulate a norm recognition mechanism based on a cognitive approach. Agents receive information about possible norms in the form of either messages from other agents or by observing their actions. These messages and observations are analyzed for either deontic (‘You must do X’) or normative value components (‘Not doing X is bad’): if these are present then the agent stores the behaviour as a possible norm. As more such observations are recorded, the salience of the possible norm is increased—that is, it is deemed more likely to be an important norm. If multiple conflicting norms apply to a situation then the most salient is complied with. If agents have personal goals and desires, these can also be weighed against the salience of the norms. While they evaluate their approach via agent-based simulation they do not propose an actual mechanism for analyzing the messages and observation for deontic or normative value content. Instead, they assume that the agent is able to perform this analysis using some undefined method.

One observational approach is to detect the use of signalling behaviour, where some agent takes an action to show a norm has been violated (e.g. punishing another agent), to allow the inference of the existence of a norm. Savarimuthu et al. (Reference Savarimuthu, Cranefield, Purvis and Purvis2010, Reference Savarimuthu and Dam2013a) propose norm identification mechanisms for identifying obligation and prohibition norms in agent societies. When an agent perceives a signalling event it invokes a norm inference component to determine whether the event may have occurred as a result of the violation of an unknown norm. The inference itself is a three step process: first, the agent records sequences of events that it observes; second, when the agent perceives a signalling event it extracts the sequence of events related to the sanctioned agent that preceded the signal; finally, the agent generates a set of candidate norms using a rule-mining algorithm. These candidate norms are then verified by communicating with other agents (who are presumed to know the norms of the society).

There are three obstacles to using violation signals to infer norms: first, norm violations may be rare, second, the signals may occur sometime after the violation, and finally, a newcomer may not recognize the signalling behaviour at all. For example, in a law-abiding society where only a very few agents violate the norms, newcomers may rarely witness violation signals.

Instead of inferring norms from the observation of violations, an agent could learn by observing compliant behaviour and comparing that with possible ways of reaching the same goals. By detecting actions not taken towards goals, it may be possible to infer prohibitions or obligations. For example, if there are five possible roads by which an agent could travel from point A to point B, and one road is consistently avoided, then there may be a norm prohibiting that road. Oren and Meneguzzi (Reference Oren and Meneguzzi2013) propose such a method using two components: a plan recognizer and a planner. The agent first observes the behaviour of an agent in the society and uses the plan recognizer to infer the overarching goal of that agent. Once the goal has been identified, it uses the planner to generate a set of possible plans by which that goal can be achieved. Sets of all possible obligated and prohibited states are generated and over a series of observations states are removed from each set, and states are added to a set of potential prohibited states. States that are entered by agents are deemed to be not prohibited and removed from the potential prohibited set; states that are not entered are removed from the set of potential obligations.

While their initial approach assumes that all agents comply with the norms, Oren and Meneguzzi extend it to allow the possibility of violation. Instead of monotonically removing states from the potential obligation and prohibition sets they allow for a certain ratio of violation to compliance. In simple terms, they keep a count of possible obligations and prohibitions and also a count of violations of those possible norms. If the ratio of compliance to violation is above a specified threshold then the norm is inferred.

Cranefield et al. (Reference Cranefield, Savarimuthu, Meneguzzi and Oren2015) combine both the observation of signalling behaviour and plan recognition in order to infer norms. They use Bayesian reasoning to generate a list of norms ordered by likelihood. Another combination approach is proposed by Mahmoud et al. (Reference Mahmoud, Ahmad, Ahmad, Yusoff and Mustapha2012a) who present a norm detection framework that uses data mining techniques on three sources of data: system logs of agent activity, communication with local agents, and observations of agent activity. The security policies of the system determine which of the three sources an agent can actually use.

6.2 System level identification

Existing work on the detection of emergent properties in complex systems is not specifically focussed on norms, but in so far as social norms are derived from emergent patterns of behaviour, the techniques are appropriate. Emergent behaviour in complex software systems, such as computer networks, or load-balancer applications, is a practical problem that has been investigated. Mogul (Reference Mogul2006) categorizes the most likely behaviour and causes in such systems. In such systems, the presence of emergent behaviour is detected largely by examining the difference between the actual and expected behaviour. Parunak and VanderBok (Reference Parunak and VanderBok1997) discuss techniques to detect possible emergent behaviour in distributed control systems, including Fourier analysis to distinguish periodic events from random noise. They propose using agent-based simulation to examine possible causes of emergent behaviour within a system.

Moving into more general detection of emergent behaviour, we examine three different strands of research: variable-based detection, event-based detection and data mining. Variable-based detection relies on macro-level variables representing system properties. Changes in these macro-level variables may constitute emergent behaviour. For example, the GDP of a nation is a macro-level variable. GDP depends upon the behaviour of micro-level components of the nation (humans), and changes to the GDP are not directly calculable from the interaction of those components. Seth (Reference Seth2008) proposes a statistical approach to measure the degree of emergence of a macro-level variable in relation to a set of micro-level variables. He calculates the degree of emergence based upon the extent to which the macro-level behaviour is both caused by and autonomous from the micro-level behaviour. Kubík (Reference Kubík2003) presents a grammar-based approach where macro-level and micro-level properties are expressed as two different grammars. Emergent behaviour is defined as those macro-level properties that cannot be derived from summation of the micro-level properties. There are two problems with variable-based detection: it relies on the aggregated behaviour of the individual micro-level components (albeit in an unpredictable way), and there is a need to specify the macro-level variables of interest and to choose which of them to monitor, which often requires expert domain knowledge. The aggregation means that if emergent properties are detected, it can be impossible to work out which micro-level actions or interactions caused them. Norms are an intrinsically micro-level phenomenon, although their effects may not be, so this represents a fundamental problem with this approach.

Event-based detection solves this problem by allowing macro-level behaviour to be defined in terms of simple micro-level events. Chen et al. (Reference Chen, Nagl and Clack2009, Reference Chen, Nagl and Clack2007) propose an event-based formalism of emergent behaviour for specifying and detecting such behaviour in an agent-based system. They define a complex event as a set of temporally, or spatially, related simple events, where a simple event is a state change in the system (typically caused by an agent performing an action). A complex event can also be made up of related complex events. Temporal relationships specify when one event occurs in relation to another and may include simultaneity, at some time before, at some time after, and immediately after; spatial relationships specify where one event occurs in relation to another. This formalism also allows variables to be specified as part of a relation. Sets of complex events are specified to represent different types of possible emergent behaviour. These can then be watched for and detected as the agents perform actions that change the system state. As complex events are ultimately defined in terms of simple events, the cause of the emergent behaviour can be determined (unlike with variable-based detection in which behaviour is aggregated).

Figure 2 shows two norms expressed as complex events: a British greeting (handshake) and a Japanese greeting (a mutual bow). A British greeting is defined as one agent extending a hand, a second agent gripping it, and a mutual handshake. A Japanese greeting is defined as two agents simultaneously bowing to each other. In this way, the two greeting norms can be specified and observers can look for instances of either phenomena.

Figure 2

Two example norms represented as complex events (after Chen et al., Reference Chen, Nagl and Clack2009)

One disadvantage of this approach is that possible emergent behaviour must be specified in order to monitor the system for the behaviour. Therefore, some entity must derive a set of such behaviours a priori. One possibility is to specify high-level behaviour that, if identified, can be used as a starting point for more detailed investigations.

Data mining can be used to identify patterns within large quantities of data. Of particular relevance to detecting emergent behaviour of agents is association rule-mining (Kotsiantis & Kanellopoulos, Reference Kotsiantis and Kanellopoulos2006) which extracts correlations, patterns and associations between items of data (such as logs of agent actions). This form of data mining has been used to formalize business processes and workflows (Van der Aalst et al., Reference Van der Aalst, van Dongen, Herbst, Maruster, Schimm and Weijters2003) and so to extract structure from data. These processes represent the actions of entities within the business (e.g. human workers acting in response to customer requirements), and so it seems likely that these techniques could be used to detect emergent patterns of behaviour in multiagent systems.

6.3 Analysis

Table 2 summarizes the examined approaches and their requirements. The important system property with respect to emergent norm identification is, of course, observability, since one must be able to observe a behaviour in order to determine whether it constitutes an emergent norm. However, it would be possible for the agent level approaches to be implemented as part of a mechanism where the system uses specific monitor agents empowered to observe the other agents in order to identify emergent behaviour. Likewise, individual agents could make use of the event-based detection mechanisms proposed by Chen et al. (Reference Chen, Nagl and Clack2009), even if system-wide observability was not possible.

Table 2

Summary of norm identification approaches

7.1 Individual evaluation

Norm evaluations made from an agent perspective are typically for two reasons: compliance and adoption. If a norm exists in a society then an agent must determine whether it will comply with that norm in the situations when it is applicable. This is one type of norm evaluation, as the agent must decide whether compliance will bring it more value than violation. However, such an evaluation must take into account the enforcement of the norm—specifically, the probability of being punished and the extent of the likely punishment. A purely utilitarian approach would weigh up the expected net benefit from following the norm against the expected net benefit of violating it (including both the direct costs of possible punishment and the indirect costs of possible miscoordination with other agents complying with the norm). Rewards could include the benefits of improved coordination (if complying) or gaining an advantage over other agents (if violating). This utilitarian approach may be of limited use when evaluating a newly emergent norm that has no associated punishments (although things change if other agents have begun to punish violators, or reward compliance). Therefore, agents may use metrics other than pure utility. They may consider whether the new norm is coherent and consistent with their other norms, beliefs and goals. Agents may also consider the effect of compliance or non-compliance on their reputation amongst their peers and the trust that others have in them.

Agents evaluating strategies without regard to punishments are common in the literature as part of models investigating the spreading of norms. This can range from simple imitation of a single successful neighbour to an assessment of the local agent strategies. We examine a selection of these approaches in Section 8.3 where we discuss the role of influencer agents in norm spreading. These evaluations are purely concerned with the utility to a single agent; although they may result in a convergence to a common norm that benefits society, this is usually accidental.

Moving away from the purely utilitarian approach, Joseph et al. (Reference Joseph, Sierra and Schorlemmer2008) use the notion of coherence to evaluate a new norm for the purposes of deciding whether an agent should adopt a norm. In their approach, norms that are more coherent with existing norms and beliefs are evaluated more highly. Thagard’s theory of coherence is used to measure coherence in terms of constraint satisfaction: associations between beliefs are seen as imposing either positive constraints, which reinforce those beliefs, or negative constraints, which weaken them. A coherent set of beliefs has few (or no) negative constraints between the beliefs, whereas an incoherent set of beliefs may have many negative constraints. Joseph et al. formalize this theory, and represent belief and norm sets as coherence graphs: nodes representing beliefs and weighted edges representing associations. When a new norm is proposed it is added to the graph, and the coherence of the combined graph can be assessed. Criado et al. (Reference Criado, Argente and Botti2010) present a norm compliance mechanism that also uses theories of coherence and consistency. In their approach, an agent evaluates a proposed norm with respect to its existing norms. If adding a new norm will make their norm set, or overall beliefs, incoherent or inconsistent then it is not accepted. Both of these approaches (Joseph et al., Reference Joseph, Sierra and Schorlemmer2008; Criado et al., Reference Criado, Argente and Botti2010) are notable for being purely individual strategies for evaluating a norm, in which an agent considers only the norm with respect to its existing set of norms. They require no assessment of whether the agent’s peers consider the norm to be valuable. In contrast, Itaiwi et al. (Reference Itaiwi, Ahmad, Tang and Mahmoud2014) propose an agent level norm evaluation framework that combines utility, the degree of adoption of the norm by one’s peers, and the consistency of the norm with respect to existing norms. They do not specify a mechanism to evaluate the utility or consistency (which they term the norm’s morality), and calculating the degree of adoption requires a global perspective (although it would be possible to modify their approach to only consider the observable neighbourhood).

Andrighetto et al. (Reference Andrighetto, Villatoro and Conte2010b) provide a model of norm internalization where an agent decides adopts the normative goals as their own and self-enforces the compliance with the norm. This process requires that an agent evaluates the norm in order to decide whether or not to internalize it. They implemented an internalization module in their EMIL framework that determines when to internalize a norm based upon two factors: norm salience and the cost of deliberating whether to comply with the norm. Salience is calculated from interactions with their neighbours, punishments observed and received, and from educative messages received from other agents regarding the norm. The cost of deliberation is a cumulative measurement of how long the agent has spent performing cost-benefit calculations concerning complying with the norm. If both salience and the cost of deliberation exceed a threshold then the norm is internalized.

Evaluating the norm in terms of personal utility or coherence and consistency with its existing beliefs can be valuable for an individual agent, but it does not necessarily shed light upon the value of the norm to society at large. An agent may hold selfish beliefs, or beliefs not shared by the majority of the society, and in any case, simply because a norm is coherent and consistent with existing norms does not make it intrinsically of value.

The approaches in this section are useful for an agent seeking to determine whether or not a norm is beneficial to itself. However, norms are usually considered in a social context, in so far as they are shared rules, so it makes sense to consider their value in terms of groups of agents, rather than individuals. In the next section, we consider approaches that evaluate norms within a wider context—that of a society or computational system.

7.2 System evaluation

In this section, we review approaches to evaluate a norm from a system or societal perspective. For any such evaluation, it is necessary that the system or society have some set of goals that it wishes to achieve, so that the norm can be evaluated with respect to that set. However, there is no need for this set of goals to be imposed by a central authority, since the goals could be an aggregate of the individual user goals, or the valuation could be based upon a utilitarian ideal of the greatest happiness for the greatest number of individuals (Mill, Reference Mill1863).

At the most basic level, evaluation can determine whether or not a norm will allow the system to fulfil its goals at all. Shoham and Tennenholtz (Reference Shoham and Tennenholtz1995) take this approach in their study of the offline design of social laws, when they define a useful law as one that allows agents to perform their required tasks (represented as changing the environment from one state to another) without other agents interfering no matter what actions they perform, so long as all agents comply with the laws. For complex systems and social norms, this conception of usefulness is perhaps both too strong and too weak. It may be too strong, since a norm may help an agent reach its goals most of the time without absolutely ensuring that it will not occasionally fail due to interference from other agents (especially where agents may have conflicting goals); and it may be too weak because it allows no gradation of usefulness, and no notion of the fact that some norms may be more effective than others.

Morales et al. (Reference Morales, Lopez-Sanchez, Rodriguez-Aguilar, Vasconcelos and Wooldridge2015) include a norm evaluation calculation in their norm synthesis mechanism (IRON). They evaluate a norm using two metrics: effectiveness and necessity. Effectiveness is a weighted measure of the ratio of successful norm fulfilments (instances where complying with the norm led to a desired state of affairs) to total fulfilments (including instances where complying led to an undesired state). So, for example, if a norm is complied with 10 times and leads to the desired state eight times, then the effectiveness is 0.8. Necessity is a weighted measure of the ratio of harmful violations (instances where violating the norm led to an undesired state of affairs) to total infringements (including instances where violating the norm had no ill effects). So, if a norm is violated 10 times and only two violations lead to a undesired state, then the norm has a necessity of 0.2. These measures are calculated over time using a reinforcement learning approach. This evaluation approach assumes that the results of all agent actions are observable and that compliance or violation of the norm can be explicitly connected to a desirable or undesirable state. In simple systems, this may be true, but in more complex ones complying with, or violating, a norm may have a more nuanced effect since norms may have indirect effects on agent behaviour beyond the success or failure of the interaction directly governed by the norm.

The notion of gradations of usefulness, or fitness, is key to evolutionary algorithmic approaches of norm design. In such approaches, a population of candidate norms is created and evaluated on a simulated system. The best performing candidates are reproduced, using evolutionary algorithm techniques, into the next generation and re-evaluated. This process continues until an adequately effective norm is found. For example, Bou et al. (Reference Bou, López-Sánchez and Rodrguez-Aguilar2007) model a traffic scenario with norms controlling how vehicles should behave at road junctions (i.e. whether to give way to traffic coming from the right). The fitness was calculated based upon the number of factors, including the frequency of collisions and the speed of traffic flow. Genetic algorithms are used to increase the fitness of the norms in an iterative evolutionary process.

Simulation techniques have also been proposed to evaluate public policy in a variety of domains, including agriculture (Berger et al., Reference Berger, Schreinemachers and Woelcke2006) and public utilities (Bunn & Oliveira, Reference Bunn and Oliveira2001). Dignum et al. (Reference Dignum, Dignum and Jonker2009) examine the use of agent-based simulation to evaluate public policy in human societies and propose a simulation framework that encompasses three levels: first, individual agent personality and cognitive traits; second, cultural aspects, such as existing social norms; and third, the macro-level effects upon society. Haynes et al. (Reference Haynes, Miles and Luck2014) explicitly use a notion of the fitness for purpose of a norm in their work on estimating norm impact. Norm impact is defined as the difference caused by the existence of a norm upon the performance of an organization, with this performance being based upon the achievement of organizational goals. The organization is simulated both with and without the norm of interest in order to estimate the impact. The efficacy of such simulation techniques depends upon the accuracy of the model with respect to reality, or at least the parts of reality that relate to both the norm and the organizational, or societal, goals. Creating accurate simulations may be very hard, even with help from domain experts.

7.3 Analysis

The choice of norm evaluation approaches depend upon normative autonomy and observability. Table 3 summarizes the requirements of the norm evaluation approaches. The system evaluation approaches require that some entity in the system be able to observe the effects of the emergent norm across the entire system, so that this can be used to assess its value. The individual evaluation approaches (Joseph et al., Reference Joseph, Sierra and Schorlemmer2008; Criado et al., Reference Criado, Argente and Botti2010; Itaiwi et al., Reference Itaiwi, Ahmad, Tang and Mahmoud2014) assume that the agents choose their own norms, and thus have norm adoption autonomy, whereas the other approaches make no such assumption. In fact, with the system evaluation approaches as presented, it would make little sense for an agent to choose their own norms, since they do not have the overall view of the system that is necessary for them to assess the value of a proposed norm. However, one could envisage a modified system approach where individual agents are presented with information about a norm’s value (assessed at a system level), and are then given the choice whether or not to adopt it. We are not aware of any existing research that examines this possibility.

Table 3

Summary of norm evaluation approaches

8.1 Metanorms

Metanorms are norms about norms, or in other words, rules that concern the usage of norms in a society. With regards to norm emergence, research on metanorms has concentrated on a rule that obliges agents to punish norm violators. Since delivering punishment usually has a cost, agents may prefer not to punish norm violations that they observe. The effect of the metanorm is to encourage agents to punish violators, since not punishing them may itself bring about punishment. Axelrod (Reference Axelrod1986) makes use of metanorms in his norms game in order to bring about norm emergence. In his norms game, each agent chooses to either cooperate (comply with a norm), or defect (violate it). Defectors may be observed by other agents with a known probability, who then have the chance to punish the defection. Each agent has two properties: vengefulness and boldness. If an agent’s boldness is greater than the probability of being observed it defects and receives a temptation payoff and the other agents suffer a loss. If another agent observes the defection it chooses to punish with a probability of its vengefulness property. A punished agent receives a large negative payoff, but the punishing agent also suffers a loss to reflect the cost of enforcement. Axelrod’s norms game uses an evolutionary approach: agents with a high utility score at the end of each round are reproduced twice into the next generation to play the next round of the game, and there is a small chance of a random mutation changing the agent properties.

Norm establishment is represented by a population with high levels of vengefulness and low levels of boldness since this reflects a society that punishes defectors while mostly complying with the norm. Axelrod shows that the basic norms game rarely results in the establishment of a norm, due to the cost of enforcement effectively punishing those with high levels of vengefulness. He therefore proposes the use of a metanorm, whereby agents are themselves liable to be punished if they are observed allowing violations to go unpunished. His experiments using the metanorm result in the establishment of the norm in most cases.

Subsequent investigation into Axelrod’s norms game (Galán & Izquierdo, Reference Galán and Izquierdo2005; Mahmoud et al., Reference Mahmoud, Barakat, Miles, Taweel, Delaney and Luck2010) has found that extending the number of generations lead to the eventual collapse of the norm, due to the chance of a sequence of unfavourable mutations taking advantage of the evolutionary nature of the agent reproduction. However, this weakness in Axelrod’s original game does not invalidate the use of metanorms to aid norm emergence. Mahmoud et al. (Reference Mahmoud, Griffiths, Keppens, Taweel, Bench-Capon and Luck2015a) show that metanorms can be used in a more realistic context to promote the emergence of norms. Specifically, they investigate a model that uses learning, rather than evolution, to change the agent properties, and where agents only punish according to the defections that they observe, in contrast to Axelrod’s game where agents punish non-punishers even if the initial violation is not observed.

8.2 Controlling norm introduction and change

As well as metanorms concerned with the usage of norms, multiagent systems may also have rules and mechanisms for changing and introducing norms. These are analogous to Hart’s (Reference Hart2012) rules of recognition and change for laws in human societies (see Section 3). The nature of these rules, if they exist, determines how a norm emerges and becomes established in an agent society. Therefore, in this section we consider different approaches that have been proposed to control how norms may be introduced and changed in multiagent systems.

Artikis (Reference Artikis2012) presents an infrastructure to allow the runtime modification of system norms by agents within the system. The infrastructure uses meta-protocols that specify how and when norms may be changed (e.g. which agents may propose new norms), and also higher levels of meta-meta-protocols that determine how those meta-protocols may themselves be changed.

In order to evaluate proposed norm modification, Artikis suggests two factors: the similarity of the modified norm to the original norm, and its expected utility (which is domain specific). To derive the similarity, they model the norm specification as a metric space (Bryant, Reference Bryant1985) whereby the ‘distance’ between the existing norm and the proposed modified norm can be calculated using some function. In this way, the system designer can constrain norm changes so that only gradual, incremental changes (represented by a small distance) can be made. As an alternative, in previous work, Artikis (Reference Artikis2009) proposed limiting the maximum distance of new norms from some ‘desired’ norm specification in order to allow the system designer more control.

Another agent-based norm modification approach is proposed by Riveret et al. (Reference Riveret, Artikis, Busquets and Pitt2014). In their approach, agents generate possible norms by considering their own experiences: for example, by learning what behaviour gives the greatest reward in a certain situation. They then each propose a possible norm for consideration by the other agents in the system. The most common proposal is voted on by all agents and, if a majority support it, it becomes a new system norm.

Tinnemeier et al. (Reference Tinnemeier, Dastani and Meyer2010) present a rule-based set of programming constructs to facilitate the operationalization of norm introduction and change during runtime. Their approach uses the concepts of norm schemes and norm instances. Norm schemes are the underlying rules of conduct for the system designed to further the design goals of the systems, and norm instances are the obligations and prohibitions concerning specific system states. Separate change rules may be specified for schemes and instances to allow fine-grain control: for example, agents may be able to change norm instances to reflect their localized knowledge, but not change the norm schemes which may require a more global perspective. While they do not specifically address emergent norms, their approach could be used to implement other techniques for engineering emergent norms.

8.3 Influencers

The metanorm approaches assume that peers enforce norms, and that no agents are privileged over another. However, it may be natural and desirable that some agents either have more power to enforce norms than others (because they are empowered to do so by the system), or that some agents are willing to expend more effort persuading others to follow norms. These agents are known as influencers, and the use to aid the spreading or emergence of a desired norm has been the subject of research. Such agents try to influence the behaviour of other agents by complying with the norm and by punishing violators or rewarding compliers, and are themselves invariant in their adoption of the norms—that is, an influencer will not cease to punish or reward. An example in human societies are police officers: they (should) punish law-breakers consistently. Norm entrepreneurs (or norm innovators) are agents who devise a new norm and try to convince others to follow the norm, either by persuasion or by example (Finnemore & Sikkink, Reference Finnemore and Sikkink1998). Human history shows many examples of individual or small groups of norm entrepreneurs, that successfully effected changes to the prevailing norms of the time. For example, the abolitionists who led to the end of the slave trade, and the suffragettes who helped to bring about women’s suffrage, were norm entrepreneurs.

Sen and Airiau (Reference Sen and Airiau2007) investigate the spread of norms via social learning where each agent learns behaviour from interacting with other agents. As part of their investigation they examined the effect of fixed agents, who do not learn, but always stay with the same strategy. In a simple coordination game where agents have a binary choice of behaviour they find that using as few as four fixed agents within a population of 3000 almost always leads to a convergence with the fixed strategy. These fixed agents can be seen as limited influencers, in so far as they persuade only by their actions and the other agents converge in order to accommodate these immovable objects in their society. However, the model is very simple, with only two choices of strategy and no notion of punishments (beyond the cost of using a defecting strategy). Hoffmann (Reference Hoffmann2005) explores the effect of norm entrepreneurs on norm emergence in agent-based simulations. In this model, agents have three candidate norms (out of a possible seven) at any one time and attempt to converge to a common group norm. The norms are scored according to how close they are to the group norm. The norm entrepreneurs suggest norms to the other agents, who use the suggestion to replace their lowest scored norm. It was found that entrepreneurs aided the establishment of a common norm.

Franks et al. (Reference Franks, Griffiths and Jhumka2013) examine the use of influencer agents to affect the convergence of a convention in a more sophisticated model. They use a linguistic domain where agents build up lexicons that map words to concepts. Agents start with randomized lexicons and over a series of rounds, they try to communicate with each other. This communication is naturally more successful if agents have more similar lexicons. The quality of this communication is measured and each round they share their lexicons (or parts of them) with other agents, and update their own lexicons based upon this level of quality (so high-quality lexicons are propagated). Over time, the agents may converge on a common lexicon, which results in more successful communication for the whole society. This domain provides many possible strategies to converge upon. Influencer agents are represented by agents with the same fixed high-quality lexicons. It is found that a relatively small number of influencers can aid the convergence of a convention. Network topology affects the results: when the influencer agents are well-connected in a communication network fewer of them are needed. As well as fixed strategy agents, Franks et al. examine the effect of non-fixed agents starting with complete, high-quality lexicons. These non-fixed agents could alter their strategies. They were also found to improve convergence, though not to the extent of the fixed strategy agents. This is perhaps analogous to highly skilled agents prepared to teach by example, but not as single-minded as norm entrepreneurs. Finally, flawed influencer agents were investigated: fixed strategy agents with poor-quality lexicons. These flawed influencers were found to have a detrimental effect on convergence, with few such agents required to prevent a useful lexicon arising in the society.

Savarimuthu et al. (Reference Savarimuthu, Cranefield, Purvis and Purvis2008) propose a mechanism to spread norms through a society of agents by the means of role model agents. Agents choose the most successful agents in their neighbourhood as role models, and these role models pass advice (in the form of a norm) to their followers. The follower agents then modify their norm based upon their role model’s advice. This is similar to learning by observation and imitation of successful agents, but because the communication is explicit the observer need not infer the successful strategy. However, it does open up the risk of malicious role models exploiting their followers for personal gain.

As well as individual agents, or a class of agents, influencing their peers, it is possible to have an approach where there is a system-wide mechanism for recommending norms to agents. Savarimuthu et al. (Reference Savarimuthu, Padget and Purvis2013b) present an architecture for such a norm recommendation service that has four distinct phases: identification, classification by salience, classification by stage in the norm life-cycle, and the recommendation itself. The identification is performed using the detection of sanctioning behaviour (as in Savarimuthu et al. (Reference Savarimuthu and Dam2013a) described in Section 6). Salience is a measure of how important the norm is to the system and is determined by the frequency of the action targeted by the norm and the probability of a norm violation being sanctioned. For example, high frequency actions that are frequently punished are deemed to be very highly salient. The life-cycle is determined by the change of salience over time: for example, newly detected norms are deemed to be emergent, norms that have risen above a specified salience threshold are deemed to be mature. The determination whether to recommend a norm is based on system-specific heuristics using the salience and life-cycle. While Savarimuthu et al. suggest that the recommendation architecture could be used by individual agents, its reliance upon observations perhaps makes it more suitable as a system-wide service able to observe globally (or at least more widely than a single agent). It could clearly be used in concert with system-controlled influencer agents such as those detailed earlier in this section.

8.4 Incentivization

In this section, we examine the use of extrinsic incentives to encourage agents to comply with norms. Incentives can include rewarding desirable behaviour, punishing undesirable behaviour or both. Complying with a norm may bring about intrinsic benefits to an agent due to improved coordination or cooperation with neighbours, and violating a norm may likewise cause intrinsic loss of utility. For example, if an agent chooses to drive on the wrong side of the road it will certainly suffer delays and probably collisions. On the other hand, if it complies with the driving lane norm, it reaps the benefit of improved coordination and can travel smoothly with the rest of the traffic. While these intrinsic incentives may be enough to encourage desired behaviour, this is not always the case. The undesired behaviour may be individually rewarding for an agent, while bad for the society as a whole (e.g. in a tragedy of the commons situation), or an agent may be unable to calculate the intrinsic benefits for itself.

Therefore, on top of these intrinsic incentives, societies may need to impose extrinsic incentives to encourage (or discourage) norm formation and adoption. In the driving example, being caught violating the driving lane norm will result in legal penalties imposed by society. The driving laws, and their enforcement, both increase the potential cost of behaving badly, and make explicit that cost, as opposed to the uncertain cost of delays and collision.

The nature of the incentive must depend upon both the deliverer and the target of the incentive. With purely peer-based incentivization where agents have no direct power over each other, incentives are limited to the offering of rewards for good behaviour, or punishment via the withdrawal of services or cooperation. For example, agents could shun norm violators and refuse to deal with them. The use of trust and reputation systems can facilitate peer-based incentivization, since they allow a long-term view of the trustworthiness of agents and, with respect to reputation, allow agents to share their opinion of other agents (Castelfranchi & Falcone, Reference Castelfranchi, Conte and Paolucci1998; Castelfranchi et al., Reference Castelfranchi and Falcone1998). Where the incentivization is delivered by the system itself, there are other options—violators could be barred from services, or even ejected from the system.

With respect to humans, there is some evidence that the use of extrinsic rewards can reduce the intrinsic motivation to perform desirable behaviour (Gneezy et al., Reference Gneezy, Meier and Rey-Biel2011), especially if the rewards are later removed. If behaviour comes to be performed purely to gain reward (or avoid punishment) then the salience of intrinsic rewards may be reduced. For example, children encouraged to read by monetary rewards may come to see reading as a chore (albeit a profitable one), and may not read unless they are offered a reward.

With computational agents, rather than humans, the effect of incentivization is simpler and more easily studied. However, when dealing with autonomous agents with uncertain motivations, whose internal reasoning is opaque, it can still be challenging to design an appropriate incentivization systems. In general, there are two questions that must be answered to determine whether an incentive system is appropriate: is the correct behaviour rewarded (or punished), and is the degree of reward (or punishment) sufficient to modify the behaviour?

Extrinsic incentives may be delivered by peers, where any agent has the ability to punish or reward behaviour, or by specific agents empowered by the system to administer punishment or deliver rewards. In this section we are concerned with incentivization administered by the society or system, either indirectly, through mechanisms which control how peers may punish or reward others, or directly, via centralized mechanisms or specified agents. Peer incentivization has been studied in relation to metanorms (described in Section 8.1) for the purpose of encouraging agents to punish norm violators, however, it may also be useful to restrict peer punishment.

While punishment has a cost which agents may be unwilling to pay (leading to under-punishment), agents may also over-punish: either to harm rivals, or to impose their view of the severity of a norm violation upon society regardless of the opinions of other agents. Over-punishment can be wasteful of resources (if the cost of a punishment is proportional to its severity), or can be harmful in other ways. For example, in an open system such as a market place, where accidental norm violation is possible, a fear of over-punishment can deter agents from joining the market and so reduce the potential customers. For these reasons, the administering of punishments can itself be a source of asocial behaviour. One mechanism to prevent over-punishment is a consensual institution of peer punishment (Casari & Luini, Reference Casari and Luini2009), where violations are only punished when more than one agent agrees with the punishment. This prevents single agents from punishing others for purely individual reasons. An alternative approach is proposed by Faillo et al. (Reference Faillo, Grieco and Zarri2013), in the context of punishing free-riders in a cooperative scenario. In their approach, agents can only punish those agents who contribute less than they themselves contribute. This prevents antisocial behaviour where low contributors punish high contributors, either as retribution for previous sanctions, or simply out of spite. Both these approaches seek to ensure that a punishment is applied in appropriate situations, rather than in an arbitrary fashion. The other factor to consider is whether the degree of incentivization is appropriate, or, in other words, is there enough of an incentive to ensure that behaviour is modified while also ensuring that not too many resources are expended?

A static punishment system, where each violator receives the same sanction for each violation has the advantage of simplicity, but it suffers from the problem that agents may react differently to the same degree of punishment. It also punishes first-time offenders the same as perpetual recidivists. Human legal systems often vary the punishment for crimes based upon the past criminal history of the offenders, with repeated law breaking being dealt with far more harshly than a first-time offence, or monetary fines scaled to match the wealth of the offender. In the context of multiagent systems, the notion of dynamic punishment, where the punishment for norm violation changes in response to agent reaction to that punishment, has been studied both with a simple escalating model (Miceli & Bucci, Reference Miceli and Bucci2005; Emons, Reference Emons2007) where repeated violations incur a greater punishment, and using machine learning techniques to refine incentives depending upon the reaction of agents (Villatoro et al., Reference Villatoro, Sabater-Mir and Sen2011a; Mahmoud et al., Reference Mahmoud, Griffiths, Keppens and Luck2012b, Reference Mahmoud, Miles, Taweel, Delaney and Luck2015b).

Increasing the punishment for an agent which violates a norm repeatedly, is analogous to the custom in some human legal systems for increasing sanctions for recidivists. The concept is based upon the assumption that the initial sanction did not make the violation costly enough to the agent (i.e. they still gained enough benefit from the violation to make it worth their while to repeat the violation), or that the first violation may have been a mistake (in which case a relatively small sanction may be enough to ensure that they take more care in the future). Emons (Reference Emons2007) examines the effect of varying sanctions on agents. In his scenario, agents can violate norms by accident or purposefully twice in order to gain utility from the violation; the scenario was intended to represent a commitment to criminal behaviour rather than a one-off intentional violation. If detected, violation was punished by fines that reduced the agents’ utility; two strategies were investigated: a small fine for an initial offence, followed by a larger fine for a second offence, or vice versa. It was found that if violation gave a large benefit, then a large fine for the second offence was optimal, since it made honesty more attractive. Bearing in mind that accidental violation was possible, a large fine for a first offence serves to make honesty less attractive, since the punishment for a second offence would be lower and agents who accidentally violate a norm have little to lose from violating it again. On the other hand, if the benefit of violation is low then a large fine for a first offence is optimal since it makes criminality less attractive—since detection is not automatic, a persistent violator is more likely to be detected only once than twice. As mentioned above, in this scenario a deliberate intention to violate a norm requires the agent to violate it twice to represent a commitment to a life of crime.

Norm violators may suffer incidental costs as well as direct sanctions. In particular, they may have reduced prospects of legitimate income in the future. For example, humans convicted of criminal behaviour may find it harder to find legal employment, and computational agents working within systems with trust and reputation mechanisms may find that past norm violations restrict their options. This reduction in future income serves as a deterrent to first-time violators but can reduce deterrence in repeat offenders, since compliance brings about lower rewards. Miceli and Bucci (Reference Miceli and Bucci2005) show that, in such a situation, an escalating punishment mechanism is optimal, since it makes continual violation less and less beneficial to the agent.

While increasing or decreasing punishments based upon repeated violations can be effective, dynamic punishment has been proposed as a way of altering the degree of punishment in response to circumstances in a more flexible way. With dynamic punishments, the degree can either go up or down as required, so that agents are neither over nor under punished.

Villatoro et al. (Reference Villatoro, Sabater-Mir and Sen2011a) propose a dynamic adaptation heuristic that varies punishment based on the number of defectors (agents violating the norm) in the society. If the number of defectors is increasing and above a set tolerance threshold, then the punishment is increased by a small amount. If the number is decreasing or below the tolerance threshold, then the punishment is decreased by a small amount. Using the dynamic punishment reduced the amount of punishment that was required to establish a norm in their model (a variation of the Prisoner’s Dilemma game). Varying punishment based on the number of defectors has two restrictions: first, the entity performing the punishment must either know the number of defectors, or be regularly informed of the correct amount of punishment to inflict, and; second, the punishment amount is determined based on the behaviour of the entire population and not the individual behaviour of the agents. If the total number of defectors is low, then a consistent defector will always receive a low degree of punishment. An alternative approach is to vary punishment dynamically based on the individual behaviour of agents. Mahmoud et al. (Reference Mahmoud, Griffiths, Keppens and Luck2012b) propose such a punishment mechanism in order to bring about norm establishment in the context of Axelrod’s (Reference Axelrod1986) norms game (described in Section 8.1). In their mechanism, each agent keeps track of past interactions and modifies how they punish violators based upon the number of previous violations. Only a specified number of the most recent interactions are considered; older violations are considered forgiven. This approach was found to bring about norm establishment with less punishment than a static punishment approach.

Mahmoud et al. (Reference Mahmoud, Griffiths, Keppens and Luck2014) propose an information-based incentivization framework, capable of supporting monetary rewards with any number of other relevant incentivization mechanisms, offered to an entity in the form of informational incentives. This framework allows learning and reasoning about the effect of various incentives on an entity’s behaviour (which is not known in advance and may change over time), and reflecting such reasoning on the design of more effective (personalized) future incentives for the entity.

8.5 Rewiring networks

Norms can spread between agents as they interact and change their behaviour to accommodate the behaviour of others, or learn successful strategies from their neighbours (e.g. via influencers as described in Section 8.3). The agents and the connections between them can be represented as a network or graph, with the agents being nodes of the graph and the interaction links being the edges. The topology of the connections can affect how norms spread through an agent population (Villatoro et al., Reference Villatoro, Andrighetto, Sabater-Mir and Conte2009; Sen and Sen, Reference Sen and Sen2010). In particular, norms have been found to spread more quickly in networks where agents interact with many neighbours, as opposed to networks where agents have fewer neighbours. Some work has examined the impact of different topologies on norm establishment. For example, Savarimuthu et al. (Reference Savarimuthu, Cranefield, Purvis and Purvis2007) consider the ultimatum game in the context of a role model that provides advice on whether to change norms in order to enhance performance, and provide experimental results for random and scale-free networks. Delgado et al. (Reference De Pelsmacker and Janssens2003) study norm emergence in coordination games in scale-free networks, and Sen and Sen (Reference Sen and Sen2010) similarly examine rings and scale-free networks in a related context. Additionally, Villatoro et al. (Reference Villatoro, Andrighetto, Sabater-Mir and Conte2009) explore norm emergence within lattices and scale-free networks. Mahmoud et al. (Reference Mahmoud, Griffiths, Keppens and Luck2013) propose dynamic policy adaptation to aid the establishment of norms using metanorms in scale-free networks. While these efforts provide valuable and useful results, the context of application has tended to be limited, with only two agents involved in a single interaction, rather than a larger population. This simplifies the problem compared to those in which multiple agents involved in a single interaction can impact on norm establishment. For example, norms may emerge in group situations such as within newly created human teams solving a group task (Bettenhausen & Murnighan, Reference Bettenhausen and Murnighan1985) or in collaborative enterprises such as open source software projects (Savarimuthu & Dam, Reference Savarimuthu, Cranefield, Purvis and Purvis2013) where developers work on the same task over a period of time, but do not necessarily interact directly.

Since the topology of the agent network connections influences the spread of norms, rewiring those connections has been proposed as a method of encouraging norm emergence. This rewiring can be purely ad hoc as individual agents choose which of their neighbours to interact with based upon their behaviour(Zimmermann & Eguíluz, Reference Zimmermann and Eguluz2005; Zhang & Leezer, Reference Zhang and Leezer2009; Griffiths & Luck, Reference Griffiths and Luck2010), or it can be performed with the specific aim of encouraging or discouraging norm establishment (Garlick & Chli, Reference Garlick and Chli2009; Villatoro et al., Reference Villatoro, Sen and Sabater-Mir2011b).

Zhang and Leezer (Reference Zhang and Leezer2009) examine the effect of selfish ad hoc rewiring upon the emergence and spread of norms. In their approach, each agent seeks to maximize its utility without concern for others and rewires its own connections in order to do so. Unrewarding connections are broken and rewarding ones maintained. They evaluate their approach with agents playing three games (Prisoners Dilemma, Stag Hunt and Pure Coordination) and found that this selfish rewiring led to a faster convergence of behaviour, and so establishment of a social norm, than simply learning from interactions in a static network. Their agents do not consider the experiences of other agents, nor do they observe the behaviour of others, so it is a purely individual approach that does not rely on trust in other agents.

If agents can observe the interactions of their neighbours, this information can be used to supplement their own experiences. Zimmermann and Eguíluz (Reference Zimmermann and Eguluz2005) use this approach to examine the effect of allowing agents to remove connections with neighbours within an iterated Prisoner’s Dilemma game. Removed neighbours are replaced with a random agent, so agents have no control over their new neighbours. Agents modify their strategy based upon the most successful of their neighbours, and these successful agents do not change their neighbours. The agents typically converge into either fully defective or fully cooperative societies, with the cooperative societies dependent upon successful cooperative ‘leader’ agents arising with stable local networks (or chains) of cooperative followers.

As well as observing the interactions of neighbours, agents may also be able to modify who they interact with based upon the reported experiences of those neighbours. This is, in effect, a reputation system where norm violators gain a bad reputation which leads to other agents shunning them. Griffiths and Luck (Reference Griffiths and Luck2010) propose such a rewiring mechanism. They focus upon agents using rewiring in order to punish defectors: essentially removing norm violators from their local neighbourhood networks. Agents do not use only their own experiences, but also those of their neighbours. Although they do not explicitly address emerging norms, this punitive rewiring could be used to reinforce norms that are not fully established and so hasten convergence, and the use of information from neighbours allows a social consensus to emerge about what constitutes defection from a norm.

The above mechanisms facilitate convergence towards a norm indirectly—agents copying successful behaviour or shunning defectors are seeking to maximize their own rewards, rather than explicitly trying to bring about the establishment of a norm. However, it is also possible to use rewiring in a more conscious attempt to influence the spread of a norm. The use of restricting communication links to discourage unwanted behaviour is examined by Garlick and Chli (Reference Garlick and Chli2009). They use an agent-based model of social unrest, where agents’ behaviour is influenced by those they interact with, and investigate the effect of implementing curfews whereby agents are prevented from interacting with their neighbours (unless they take a risk of arrest by breaking the curfew). Unsurprisingly, the results show that such curfews inhibit the spread of unrest.

A more sophisticated approach is proposed by Villatoro et al. (Reference Villatoro, Sen and Sabater-Mir2011b). Their method focusses on removing metastable subconventions that otherwise prevent the widespread establishment of a norm. Subconventions are regional norms adopted by subsets of agents within the society, perhaps due to local network topology or local agent preference. For example, if a subset of agents are relatively isolated from the main society then a subconvention could be locally reinforced and not allow another (potentially more useful) norm to spread. They propose the use of observation and rewiring (which they collectively term social instruments) to facilitate norm convergence in an agent society. In their approach, agents observe interactions outside of their immediate neighbourhood and learn from those interactions. By observing widely, agents can modify their behaviour based upon global, rather than purely local, norms and so subconventions can be dissolved. Their second social instrument is rewiring, where agents change their links to other agents to overcome topological bottlenecks that are restricting the spread of norms. Agents identify frontier regions, where two conflicting norms meet, and further determine if a self-reinforcing structure (SRS) is present (where the topology maintains a local metastable subconvention). Figure 3 shows examples of the two types of SRS that their approach looks for—the caterpillar, and the claw. They are typified by the presence of ‘hangers’ that only connect to the SRS (or other SRSs), and not the wider world. For example, in the claw structure (Figure 3(b)) nodes C, D, G and H are hangers, and the structure consisting of B, E and F is another claw. If such a structure is found, the agents rewire their local network connections in order to remove the SRS and facilitate the dissolution of the subconvention.

Figure 3

Self-reinforcing structures (after Villatoro et al., Reference Villatoro, Sen and Sabater-Mir2011b); (a) caterpillar; (b) claw

Mungovan et al. (Reference Mungovan, Howley and Duggan2011) also propose a method to remove local self-reinforcement of conventions. They introduced the idea of weighted random interaction by which agents are able to interact with random members of the population based on the distance, so the closer an agent is to another, the more likely there will be an interaction between these two agents. Their results suggest that dynamic interaction helps in easing emergence especially in breaking local biases that are normally hard to break.

The research on rewiring agent connections shows that it can be an effective way of encouraging the establishment of a norm and removing conflicting local norms sustained by topological reinforcement. It can also be used as a sanctioning and enforcement mechanism once a norm is established.

8.6 Normative conflict detection and resolution

In the previous section, we describe methods to remove local subconventions by means of rewiring networks. This is an example of resolving conflicts between norms so that one can become fully established across the society. A normative conflict occurs when one norm obliges behaviour that is prohibited by another norm, or when two norms oblige actions that cannot both be performed: for example, obligations to attend two social events at the same time (Elhag et al., Reference Elhag, Breuker and Brouwer2000). Such conflicts may prevent norms emerging in a society because agents cannot comply without violating other norms. For this reason, detecting and resolving such conflicts can aid the emergence of norms. Additionally, the resolution technique can be tailored to favour the norms preferred by the system designers. The research on normative conflict detection and resolution is extensive, so we do not attempt to fully survey the field. Much of the research focusses on individual agent assessment of the value of the norm in an attempt to choose the best one. For example, Criado et al. (Reference Criado, Argente and Botti2010) (see Section 7) that examines whether a new norm is consistent with an agent’s existing norms, or dos Santos Neto et al. (Reference dos Santos Neto, da Silva and de Lucena2012) in which an agent weighs up the benefits and costs of complying with each possible norm and chooses the most individually beneficial norm). We focus on system-based approaches, since if each agent resolves normative conflict in its own way they may disagree over which norm to favour and this will not aid in the encouragement or discouragement of an emerging norm.

Vasconcelos et al. (Reference Vasconcelos, Kollingbaum and Norman2009) detail an approach to detect and resolve conflicts between norms that regulate agent actions. They represent norms as constraints over variables and conflict occurs when the constraint variables of a prohibition overlap with those of an obligation or permission. This is detected, during runtime, using first-order unification. If a conflict is detected, it is resolved by curtailing one of the norms so that its scope is reduced—that is, it no longer overlaps with the other norm. Which norm to curtail is determined by system policies. The work suggests two policies, based on the legal principles of lex posterior (where the older norm is curtailed) and lex superior (where the norm proposed by the weaker authority is curtailed). A similar approach of unification and curtailment is taken by Vasconcelos et al. (Reference Vasconcelos, Kollingbaum and Norman2007).

Sensoy et al. (Reference Sensoy, Norman, Vasconcelos and Sycara2012) propose a language for representing norms, OWL-POLAR, based upon the Web ontology language OWL-DL. They provide an algorithm that detects possible conflicts by creating canonical states of the world where each norm is complied with and using an ontology consistency checker (such as Pellet (Sirin et al., Reference Sirin, Parsia, Grau, Kalyanpur and Katz2007)) to see if such compliance is possible for all norms. Resolution is performed by one norm overriding another, either by lex posterior or lex superior (as in Vasconcelos et al., Reference Vasconcelos, Kollingbaum and Norman2009), or lex specialis, where a more specialized norm overrides a more general formFootnote ⁸ . This latter is possible due to an algorithm they detail that determines whether one norm can be subsumed by another.

Constraint satisfaction techniques can be used to detect conflicts between norms. Günay and Yolum (Reference Günay and Yolum2013) treat obligations as constraints on agent behaviour and represent a set of obligations as a constraint satisfaction problem. Such a problem can be run through a problem solver to see if all the constraints can be satisfied. If not, then there is a conflict that must be resolved.

8.7 Analysis

Table 4 summarizes the approaches used to encourage or discourage norm establishment. The enforcement method and observability requirements are most important, since many of the approaches rely on peer pressure to spread or discourage norms: either direct sanctions (such as with the metanorm approaches) or via indirect measures (such as rewiring to exclude norm violators). The assumption of norm adoption autonomy is irrelevant to most of the approaches, since they do not specify where the norms come from, but some of the system level approaches do assume that a norm has been mandated by a controlling authority, or mandate how and when agents must punish violators.

Table 4

Summary of approaches encouraging or discouraging norm establishment

Most of the research effort on norm establishment has been focussed on peer-based systems, presumably since more centralized controlled systems can often establish a norm by fiat. However, this means there is a gap with respect to systems that seek to exert some degree of control over its norms, while being unable to impose those norms directly: for example, systems that are open to autonomous, heterogeneous agents that wish to maintain specific community standards.