Socially Intelligent Genetic Agents for the Emergence of Explicit Norms

1 Introduction

Norms encourage coordination and prosocial interactions in a society [Morris-Martin et al., 2019]. For example, ignoring a phone call in a meeting is a social norm that helps avoid disruption. Importantly, norms may conflict with one another [Kollingbaum et al., 2007; Santos et al., 2017]: an agent must decide which norms to follow and which to violate. For example, picking up an urgent call and ignoring a call during a meeting

during a meeting, one or the other norm must be violated.

Norms can be implicit (encoded in common behaviors [Morris-Martin et al., 2019]) or explicit (explicitly maintained and reasoned about like laws [Von Wright, 1963] and regulations [Jones and Sergot, 1993; Kafalı et al., 2020]). Where do norms come from? Prior work considers (decentralized) emergence for implicit norms and (central) synthesis for explicit ones [Morales et al., 2014; Morales et al., 2018].

Norm emergence is the decentralized evolution of norms [Morris-Martin et al., 2019], driven by signaling between agents. A norm violation may result in a negative sanction [Nardin et al., 2016], i.e., a scowl on the face of a meeting attendee. If the scowl is outweighed by the benefits of picking up an urgent call, the norm ignore a call during a meeting, unless it is an urgent call may emerge. Alternatively, if the sanction is severe, the norm pick up an urgent call, unless you are in a meeting may emerge. For us, a norm violation is not necessarily considered a negative act, but rather a decision by an autonomous agent to choose between norms. Thus, norm violations drive norm change [Castelfranchi, 2016].

We focus on the emergence of explicit norms. Ajmeri et al. [2018] show that sharing contextual information in case of norm violations facilitates norm emergence for implicit norms and results in increased goal satisfaction and cohesion (i.e., perception of norm compliance) by helping agents understand the context (i.e., attributes that define the circumstances) in which the norm was violated and thus learn contextual boundaries. By sharing explanations in cases of norm violations, agents can continually refine existing norms. Examples include photo sharing [Mosca and Such, 2021] and user acceptance in general [Ye and Johnson, 1995]. Explanations underlie accountability, and refining norms yields innovation in a sociotechnical system [Chopra and Singh, 2016].

Our research objective is to understand how creating and sharing explanations for norm violations facilitates the emergence of norms. We develop agents who produce and reason with explanations. Explicit norms are conducive to explanations of when they are satisfied or violated. We propose a method for the emergence of explicit norms by developing genetic agents that use rule learning [Liu et al., 2016]. Based on the foregoing, we identify these research questions:

RQG (Goal) Do societies of agents who provide and evaluate explanations for norm violations achieve higher goal satisfaction for their members than other societies?

RQC (Cohesion) Does providing and evaluating explanations lead to norms that improve social cohesion?

We make these contributions. First, we develop a socially intelligent genetic agent (SIGA) in two variants: A plain SIGA (or NSIGA) represents norms explicitly; an XSIGA in addition explains its actions and incorporates others' explanations. Second, using SIGAs, we answer both RQs positively: (1) Sharing explanations to explain actions lead to improved goal satisfaction; and (2) sharing explanations to explain actions lead to emergence of norms with increased cohesion.

2 Running Example and Solution Idea

In our model, each agent has one primary stakeholder, whom the agent represents, and potentially many other stakeholders who are affected by the agent's actions [Ajmeri et al., 2020].

We adopt a phone ringer application to explain our method. An agent is responsible for ringing the phone of its primary stakeholder (the callee) when a call is received or to keep it silent. The other stakeholders are the caller and the people in the vicinity of the callee who may be disturbed by the ringing phone. Actions available to the agent are ring or ignore. The agent decides to ring the phone or keep it silent based on the norms it follows. Agents of other stakeholders may sanction the agent if they don't agree with its action.

Suppose Alice's agent follows three norms: always ring an urgent call, always ring a call from a family member, and ignore calls during a meeting. Suppose Bob's agent follows the norms: always ring an urgent call and ignore calls during a meeting. Suppose Alice gets an urgent call from a family member during a meeting. Her agent assigns a value (expected reward) to each action in terms of the norms that support it. If the combined value of always ring an urgent call and always ring a call from a family member is more than the norm ignore calls during a meeting, it rings the phone.

If Alice's agent does not explain its action, Bob's agent would assume that the only applicable norm, ignore calls during a meeting, was violated, and sanction Alice. If Alice presents the supporting norms, always ring an urgent call and always ring a call from a family member, they are evaluated by Bob's agent. Suppose Charlie's agent does not follow always ring a call from a family member but follows always ring an urgent call. If Charlie's agent assigns a higher value to always ring an urgent call over ignore calls during a meeting, it would not issue a sanction. Else, it would reject the explanation and sanction Alice, leading her agent to adjust its values of the three norms.

3 Method: Realizing a SIGA

A SIGA's actions are governed by explicit norms. Norms in our conception are commitments [Singh, 2013]. A commitment is written Commitment(subject, object, antecedent, consequent). The antecedent determines when it goes in force; the consequent determines when it completes (is satisfied or violated); the subject is the agent who commits, and the object is the agent to whom it is committed. We can express (Callee) commits to always ringing a call from a family member (Caller) as: Commitment(Callee, Caller, callerRel = family, action=ring). Commitments are well suited for rule-based learning as rules can suggest actions that can map to a commitment's consequent.

3.1 NormLearning and Discovery

A rule-based approach to implementing norms supports flexibility and ease of implementation. Each agent stores norms as rules that it learns, evaluates, and evolves. (Below, we write ⊤ for true and ⊥ for false.) Here, the antecedents are conjunctions of key-value pairs, e.g., callerRel = family, urgent = ⊤. The consequents are actions to be taken to satisfy the norm. Thus, a norm maps to a rule of the form: IF antecedent THEN consequent.

We adapt eXtended Learning Classifiers (XCS), a rule learning algorithm based on reinforcement learning [Butz and Wilson, 2000; Urbanowicz and Browne, 2017], which evolves rules by learning from rewards obtained from the environment in response to actions. This algorithm enables agents to discover norms and learn their values. Specifically, we (1) aggregate the sanctions and payoffs received by an agent into rewards; (2) map norms to IF-THEN rules to be manipulated by XCS; and (3) define crossover and mutation operations for norms to enable norm discovery.

XCS operates in two modes, exploration (take random actions to find new norms) and exploitation (apply learned rules and their weights to choose an action). We adopt the ϵ-greedy technique, choosing exploration with probability ϵ.

Each rule has associated parameters of fitness (worth of the rule in making accurate predictions), reward prediction, prediction error (of the reward), and numerosity (how many "copies" of the rule exist, indicating robustness against accidental deletion [Urbanowicz and Browne, 2017]).

Create Match Set

The match set is the set of rules that are activated in a given context. This means that the antecedents of the corresponding norms are true in the given context.

Cover Context

Covering ensures that rules with sufficiently many actions are available for a given context. Covering maintains diversity by adding new rules to the agent's ruleset, to avoid overfitting to the initial conditions. The new rules are generated by randomly selecting some subset of the context to be the antecedent of the rule. This ensures that the antecedent would be true in the given context. The consequent is randomly selected from available actions. Covering is essential at the beginning since each agent has an empty ruleset, meaning its match set is empty.

Select Action

The expected value of each action aggregates the fitnessweighted reward predictions of rules supporting that actionto predict the expected reward of following each norm. Pick the available action with the highest expected value.

Create Action Set

Matching rules that support a chosen action form the action set. We create this set by identifying which rules had suggested the selected action.

Update Rule Parameters

These updates follow Urbanowicz and Browne [2017]. Upon receiving a reward, the agent revises its value estimation of the rules by updating its rule parameters. Only rules in the action set are updated because we don't know the influence of selecting any other action. Equation 1 updates the predicted reward. Here, p is the reward prediction, r is the reward received, and β is the rate of learning hyperparameter.

Equation 2 updates the prediction error, ε. Equation 3 estimates accuracy κ where ε0 is the error threshold below which we assume a rule to be accurate. Here, v controls the relationship between error and accuracy to increase the difference in fitness levels between two rules that are close in prediction error-to prefer a less error-prone rule during discovery. And, α is the scaling factor used to raise the least error-prone non-accurate classifier to be close to an accurate classifier.

We normalize accuracy to κ′ using Equation 4, and update fitness F using the Widrow and Hoff [1960] update:

Subsume Action Set Rules

Subsumption means replacing a rule with a more general rule that yields a smaller prediction error-as defined in Section 3.1, the error in the reward predicted to be received when following the rule. This process provides generalization pressure to the algorithm. If the first rule below (R1) is more error-prone than the second (R2), it may be replaced by the second, thus increasing R2's numerosity (see Section 3.1).

Discover Rules

We apply a genetic algorithm (GA) to generate new rules from current rules of high fitness. GA selects parents using tournament selection [Urbanowicz and Browne, 2017]. We randomly select 30% of the rules (with replacement, so they can be the same rule) in the action set to compete. The fittest two among them become parents. We generate two children using crossover and mutation operations, which we define for norms. The children are added to the population of rules maintained by the agent. To allow the rules to stabilize, we breed them only when the average experience (number of times a rule has been selected) of the rules in the action set is above a threshold. We use single-point crossover, in which the values are randomly swapped for each contextual property present in either parent's antecedent.

In XCS, mutation is used to create a more general or more specific rule by randomly flipping bits in the parent encoding. For norms, we randomly add (using ∧) or remove key-value pairs in the antecedent of the norm being mutated. For example, if the antecedent of a norm is {callerRel = friend ∧ urgent = ⊤}, we may mutate it to {urgent = ⊤} by removing a pair or to {callerRel = friend ∧ urgent = ⊤ ∧ calleeLoc = home}, if the location in the current context is home.

Subsume Child Rules

Upon creation, a child rule is subsumed into its parent if the parent is more general and its error is less than a threshold.

Delete Rules

A hyperparameter defines the maximum number of rules a SIGA can keep. We apply Kovacs's [1999] deletion Scheme 3, which prefers to delete unfit rules.

3.2 Norms as Explanations

An explanation is comprised of norms that support the action taken, i.e., the action set identified above. An agent evaluating the explanation identifies norms it follows in the explanation plus the norms that have been violated. It adds the associated rules to the match set and then follows the same procedure as action selection by performing fitness-weighted aggregation of reward prediction. If the resulting action matches the observed action, it applies no sanctions.

4 Simulation Scenario: RINGER

This scenario is based on our running example and is implemented using MASON [Luke et al., 2005]. Our simulation consists of a population of agents. There are five shared locations where agents can interact: homes (H), parties (P), meetings (M), a library (L), and an emergency room (ER). Some of these locations (H, P, and M) have an associated relationship circle. Each home has a family circle, each party has a friend circle, and each meeting has a colleague circle. People of the same circle share that relationship. An agent stays at one location for a random number of steps chosen from a Gaussian distribution with a mean of 60 steps and a standard deviation of 30, with the number of steps restricted to the range [30, 90]. Then it moves to another location. An agent is more likely to enter a location that is associated with its own circles (75% probability) than a location with which it has no association (25% probability). For example, an agent is more likely to enter its own home than a stranger's home.

At each timestep, an agent calls another agent with a probability chosen from a Gaussian distribution with a mean of 5% and a standard deviation of 1%. There is a 25% probability each of calling a family member, a colleague, a friend, or a stranger.

Each agents has goals based on its role (Table 1). The degree to which an agent is affected by the promotion or demotion of these goals determines the payoff that it receives. The payoff may differ based on location and relationship.

Tables 2, 3, and 4 present the callee, caller, and neighbor payoffs, respectively. Neighbor payoffs and sanctions may be affected by the explanation provided, depending on whether the explanation was accepted or not. Table 5 summarizes the expected payoff of each situation in this case.

4.1 Contextual Properties

The relevant context includes callee's location (home, party, meeting, library, and ER), relationship with caller (family, friend, colleague, stranger), and call urgency.

4.2 Types of Societies

Agents optimize their norms based on a weighted sum of payoffs received by each stakeholder. We define types of societies based on the generosity of their members in terms of the weight they place on the welfare (payoff) of their peers.

Selfish Members give weight only to their own payoff.

Pragmatic Members give equal weight to everyone's payoff.

Considerate Members give weight only to others' payoffs.

Mixed 25% selfish, 25% considerate, 50% pragmatic.

5 Experiments and Results

To address our research questions, we run simulations of pragmatic, selfish, considerate, and mixed agent societies using three kinds of agents:

Fixed agents follow a fixed set of norms (Table 6). When norms conflict, they choose a random action.

NSIGAs evolve a set of explicit norms following our mechanism. When they violate a norm, they accept the sanction and use that feedback to guide learning.

XSIGAs go beyond NSIGAs by explaining their actions and issuing sanctions based on explanations received.

5.1 EvaluationMetrics and Hypotheses

We compute Social Experience, Cohesion, and Adoption.

Social Experience measures the degree of goal satisfaction delivered by an agent [Ajmeri et al., 2018]. We compute it as the weighted aggregate of payoffs received by all of an agent's stakeholders as the result of its actions [Ajmeri et al., 2018]. The weights depend on the nature of the agent (selfish, considerate, or pragmatic), as defined in Section 4.2.

Cohesion measures the perception of norm compliance [Ajmeri et al., 2018], and is the number of an agent's actions perceived as norm compliant by agents who are affected by them divided by the total number of interactions.

Adoption measures the percentage of agents in a society who comply with a particular norm. A norm is said to have emerged when adoption of the norm exceeds a threshold [Haynes et al., 2017]. As in the literature, we consider 90% adoption as the threshold [Delgado, 2002].

We evaluate the following hypotheses: H1 and H2 relate to RQG; H3 and H4 relate to RQC; and H5 relates to our overall research objective of studying the influence of explanations on norm emergence. Each hypothesis compares the XSIGA approach with the other approaches. We omit the corresponding null hypotheses for brevity.

H1 XSIGAs give higher social experience than Fixed agents.

H2 XSIGAs give higher social experience than NSIGAs.

H3 XSIGAs give higher cohesion than Fixed agents.

• H4 XSIGAs give higher cohesion than NSIGAs.

H5 XSIGAs give higher adoption of norms than NSIGAs.

We report results for each simulation run eight times for 10,000 timesteps. To evaluate these hypotheses, we conduct a paired t-test and measure the effect size as Cohen's d.

5.2 Experiment: Pragmatic Agent Society

Table 7 summarizes the social experience, cohesion, and adoption for the three agent types in a pragmatic society. Figure 1a compares the social experience for Fixed, NSIGAs, and XSIGAs agents. We find the social experience, cohesion, and adoption yielded by XSIGAs to be better (p < 0.01; d > 0.8, indicating a large effect) than the two baselines.

Figure 2a shows the adoption of norms for NSIGAs and XSIGAs (Fixed doesn't yield new norms). Each dot is a norm. Explanations help in identifying and promoting useful norms while discouraging the adoption of useless norms. As a result, XSIGAs produce a more extreme distribution.

Table 8 shows the norms that emerge using SIGAs. The sole norm emerged with XSIGAs, always ring, improves the payoffs overall. This norm provides a better experience to the caller. The neighbor's experience depends on the acceptance or rejection of the explanation. The callee's experience can be negative, as for a casual call by a stranger. NSIGAs get harsher penalties from neighbors for violating norms as they do not provide explanations. As a result, the emerged norms are more cautious: ring an urgent call, ring a call by a known person, and ring a call in an ER because these provide sufficient positive payoffs to overcome possible negative neighbor reactions. Whereas Figure 2a shows several norms with adoption above 90%, Table 8 lists only one emerged norm for XSIGAs, ring all calls, because this norm is more general than the other emerged norms, such as ring urgent calls.

• (a) Adoption of norms: Pragmatic society.
• (b) Adoption of norms: Selfish society.
• (c) Adoption of norms: Considerate society.

Table 7: Social experience and cohesion in a pragmatic society.

5.3 Experiment: Selfish Agent Society

Table 9 summarizes the social experience, cohesion, and adoption yielded by the three agent types in a selfish society. As Figure 1b shows, we find the social experience and cohesion for XSIGAs to be better (p < 0.01; d > 0.8, indicating a large effect) than the baselines, and reject the null hypotheses corresponding to H1-H4. For adoption, however, the difference in mean values is not statistically significant and we fail to reject the null hypothesis corresponding to H5.

Figure 2b shows the norm adoption for the SIGA approaches. Providing explanations has a lower effect on emergence in a selfish society than pragmatic or considerate societies. Mean adoption among emerged norms is similar for XSIGAs and NSIGAs because selfish agents don't give weight to anyone's payoff other than their own and do not give value to responses from other agents. Hence, selfish XSIGAs learn norms without regard to how others evaluate their explanations though, as XIGAs, they provide and evaluate explanations. Providing an explanation is better in terms of social experience and cohesion because the neighbors are also selfish, and would accept an explanation when they would have done the same thing as the callee in the same context, even if it is a selfish action. This acceptance of explanations leads to better social experience and cohesion, even if it doesn't affect the exact norms that emerge.

Table 10 shows the norms that have emerged. The norms emerged for XSIGAs and NSIGAs are similar to each other, in line with our expectation that norms emerging in a selfish society won't be affected by providing explanations. The emerged norms are: pick up an urgent call and always ignore a casual call from a stranger. This is because a selfish agent does not value the payoff of neighbors or callers. It ignores a casual call from a stranger even in a nonrestrictive location like ER where the neighbors expect it to ring a call.

5.4 Experiment: Considerate Agent Society

Table 11 summarizes the social experience, cohesion, and adoption for the three agent types in a considerate society.

Figure 1c compares the social experience plots for Fixed, NSIGAs, and XSIGAs agents in a considerate society. We find the social experience, cohesion, and adoption yielded by XSIGAs to be better (p < 0.01; d > 0.8, indicating a large effect) than the two baselines, and thus reject the null hypotheses corresponding to H1-H5. Figure 2c shows the adoption of norms for different approaches in a considerate society. As in a pragmatic society, providing explanations had a polarizing influence on adoption. This helps in the emergence of norms by increasing the adoption of the emerged norms.

Table 12 shows explicit norms that emerge using SIGAs. For XSIGAs, the effective norm is to ring in all cases for similar reasons as for pragmatic agents. We observe that even within the norm, a more specialized version like ring an urgent call has higher adoption than ring a casual call. For NSIGAs, the agent needs to be more careful with the neighbors' payoffs, as for pragmatic agents. As a result, the most adopted norms are based on location and urgency.

6 Discussion

We find that societies composed of XSIGAs have better social experience and cohesion than the baselines and that providing and evaluating explanations leads to better adoption of emerged norms, except for a selfish society.

Mosca and Such [2021] generate explanations in multiuser privacy scenarios for evaluation by a human. In contrast, our explanations are communicated between agents for norm emergence. Hind et al. [2019] apply machine learning to jointly predict actions and explanations. In contrast, our explanations are formed of the norms that explain an action.

Morales et al. [2014] study centralized norm emergence where conflict scenarios are recognized and norms adapted to handle the conflicts. But, here, agents themselves create the norms. Morales et al. [2018] synthesize norms using an offline, centralized mechanism to evolve norms aligned with goals, whereas here norms evolve in an online, decentralized manner based on sanctions. Mashayekhi et al.'s [2022] decentralized norm emergence framework is driven by conflict detection with norms created to avoid conflicts. But, here, SIGAs are driven by sanctions and sharing explanations.

Dell'Anna et al. [2020] use Bayesian Networks to revise sanctions associated with enforced norms. In contrast, we revise the norms themselves while the sanctions stay the same. Hao et al. [2018] propose heuristic collective learning frameworks to learn norms as best responses to all states, whereas we apply genetic exploration to evolve the antecedents used in the norms instead of learning for all states.

Ajmeri et al. [2018] provide an implicit norm system that learns actions to be taken in different contexts, whereas our work is an explicit norm system that explicitly learns and reasons about norms. They share not explanations but the entire context in which the decision was made to violate the norm. This context is evaluated by other agents to decide if they would have done the same action as a basis for sanctioning. In contrast, we share explicit norms that influence a decision.

This work suggests important and interesting extensions. One, to generate explanations that trade off privacy and specificity-revealing more information may yield clarity at the loss of privacy. Two, to apply a domain ontology to learn norms with complex boundaries reflecting the subtleties of real-life norms. Three, to enhance SIGAs to incorporate values and value preferences, ethics, and fairness to guide explicit norm emergence [Ajmeri et al., 2020; Murukannaiah et al., 2020; Santos et al., 2019; Serramia et al., 2018; Woodgate and Ajmeri, 2022].

Acknowledgments

RA is now with Google. NA thanks the University of Bristol for support. MPS thanks the US National Science Foundation (grant IIS-2116751) for support.