Identifying prohibition norms in agent societies

In normative multi-agent systems, the question of “how an agent identifies norms in an open agent society” has not received much attention. This paper aims at addressing this question. To this end, this paper proposes an architecture for norm identification for an agent. The architecture is based on observation of interactions between agents. This architecture enables an autonomous agent to identify prohibition norms in a society using the prohibition norm identification (PNI) algorithm. The PNI algorithm uses association rule mining, a data mining approach to identify sequences of events as candidate norms. When a norm changes, an agent using our architecture will be able to modify the norm and also remove a norm if it does not hold in the society. Using simulations of a park scenario we demonstrate how an agent makes use of the norm identification framework to identify prohibition norms.     

Norm-based agency for designing collaborative information systems

Abstract. Information systems are organizations in which signs are created, processed and consumed. In order to fulfil the organizational goals and objectives, its members must understand their responsibilities and authorities, and must act co-operatively. The key to this organization and co-ordination lies in norms, which define responsibilities and authorities for each human agent, and establish regularities of behaviour. In the context of co-operative work, where 'intelligent' software agents are involved, to understand the norms of behaviour of various human agents becomes critical. Software agents can perform some tasks autonomously on the user's behalf. Such delegation involves a set of complicated philosophical and legal issues. After discussion on delineation of various boundaries of responsibility and authorities, this paper addresses norms and normative behaviour of human agents within an organization. It discusses the taxonomies of norms and a method of norm specification, with examples. Finally it presents an approach of norm-based agency for designing collaborative information systems and a case study of an insurance claim for illustration.     

Norms in artificial decision making

A method for forcing norms onto individual agents in a multi-agent system is presented. The agents under study are supersoft agents: autonomous artificial agents programmed to represent and evaluate vague and imprecise information. Agents are further assumed to act in accordance with advice obtained from a normative decision module, with which they can communicate. Norms act as global constraints on the evaluations performed in the decision module and hence no action that violates a norm will be suggested to any agent. Further constraints on action may then be added locally. The method strives to characterise real-time decision making in agents, in the presence of risk and uncertainty.     

Norm reasoning services

Norms are used in open Multi-Agent Systems as a formal specification of deontic statements aimed at regulating the actions of agents and the interactions among them. In this paper, we propose a set of services facilitating the development of both non-normative and normative agents for norm-governed MAS. Specifically, we propose to provide agents with norm reasoning services. These services will help agent designers/developers to programme agents that consider norm reasoning without having to implement the needed mechanisms to reason about norms by themselves. This article shows how these services perform as well as the results of the experiments that we conducted to evaluate their performance.     

From the specification to the implementation of norms: an automatic approach to generate rules from norms to govern the behavior of agents

Open multi-agent systems composed of heterogeneous, autonomous and independently designed agents are usually governed by a set of norms. The established norms regulate the behavior of the agents by pointing out their permissions, prohibitions and obligations. This paper presents a normative language to specify norms and proposes the implementation of such norms by using a rule-based system. The implementation is achieved by automatically transforming the specification of each norm of the system into a set of rules used to govern the behavior of the agents according to the norm. The governance system is able to activate and deactivate norms, to point out the norms violations and fulfillments and to inform about punishments and rewards.     

Conflict Detection among Multiple Norms in Multi-Agent Systems

In open multi-agent systems (MAS), norms are being used to regulate the behavior of the autonomous, heterogeneous and independently designed agents. One of the main challenges on developing normative systems is that norms may be in conflict with each other. Norms are in conflict when the fulfillment of one norm violates the other and vice-versa. In previous works, the conflict checkers consider that conflicts can be detected by simply analyzing pairs of norms. However, there may be conflicts that can only be detected when we analyze several norms together. This work presents a conflict checker capable to detect conflicts between two or more norms at the same time. A new, more expressive normative language, represented by a BNF grammar, was developed to define norms and Conflict Checker was implemented in tool format. Two validation principles were applied: software testing and formal verification. The strategy thus developed emerges as a new syntax for definition and verification of conflicts in MAS.     

The cognitive legacy of norm simulation

The comprehension of norms in complex social systems is one of the most active fields of research in agent-based modelling. This is faced with the challenge to comprehend the recursive interaction between inter- and intra-agent processes. In this article, a comparative analysis of selected cases of normative agent architectures will be given based on a review of theories of norms in the social sciences. This allows to identify the prerequisites for a representation of the cognitive processes of norm recognition. As yet, there is no unequivocal concept for the design of normative agents. Different approaches are compared along the line of different theoretical accounts.     

A multiagent network for peer norm enforcement

In a multiagent system where norms are used to regulate the actions agents ought to execute, some agents may decide not to abide by the norms if this can benefit them. Norm enforcement mechanisms are designed to counteract these benefits and thus the motives for not abiding by the norms. In this work we propose a distributed mechanism through which agents in the multiagent system that do not abide by the norms can be ostracised by their peers. An ostracised agent cannot interact anymore and looses all benefits from future interactions. We describe a model for multiagent systems structured as networks of agents, and a behavioural model for the agents in such systems. Furthermore, we provide analytical results which show that there exists an upper bound to the number of potential norm violations when all the agents exhibit certain behaviours. We also provide experimental results showing that both stricter enforcement behaviours and larger percentage of agents exhibiting these behaviours reduce the number of norm violations, and that the network topology influences the number of norm violations. These experiments have been executed under varying scenarios with different values for the number of agents, percentage of enforcers, percentage of violators, network topology, and agent behaviours. Finally, we give examples of applications where the enforcement techniques we provide could be used.     

Artificial institutions: a model of institutional reality for open multiagent systems

Software agents’ ability to interact within different open systems, designed by different groups, presupposes an agreement on an unambiguous definition of a set of concepts, used to describe the context of the interaction and the communication language the agents can use. Agents’ interactions ought to allow for reliable expectations on the possible evolution of the system; however, in open systems interacting agents may not conform to predefined specifications. A possible solution is to define interaction environments including a normative component, with suitable rules to regulate the behaviour of agents. To tackle this problem we propose an application-independent metamodel of artificial institutions that can be used to define open multiagent systems. In our view an artificial institution is made up by an ontology that models the social context of the interaction, a set of authorizations to act on the institutional context, a set of linguistic conventions for the performance of institutional actions and a system of norms that are necessary to constrain the agents’ actions.     

MaNEA: A distributed architecture for enforcing norms in open MAS

Norms have been promoted as a coordination mechanism for controlling agent behaviours in open MAS. Thus, agent platforms must provide normative support, allowing both norm-aware and non-norm-aware agents to take part in MAS that are controlled by norms. In this paper, the most relevant proposals on the definition of norm enforcement mechanisms are analyzed. These proposals present several drawbacks that make them unsuitable for open MAS. In response to these problems, this paper describes a new Norm-Enforcing Architecture aimed at controlling norms in open MAS. Specifically, this architecture supports the creation and deletion of norms on-line as well as the dynamic activation and expiration of instances. Finally, it can dynamically adapt to different scale MAS. The efficiency of this architecture has been experimentally evaluated and the results are shown in this paper.     

Normative conflict resolution in multi-agent systems

Norms (permissions, obligations and prohibitions) offer a useful and powerful abstraction with which to capture social constraints in multi-agent systems. Norms should exclude disruptive or antisocial behaviour without prescribing the design of individual agents or restricting their autonomy. An important challenge, however, in the design and management of systems governed by norms is that norms may, at times, conflict with one another; e.g, an action may be simultaneously prohibited and obliged for a particular agent. In such circumstances, agents no longer have the option of complying with these norms; whatever they do or refrain from doing will lead to a social constraint being broken. In this paper, we present mechanisms for the detection and resolution of normative conflicts. These mechanisms, based on first-order unification and constraint solving techniques, are the building blocks of more sophisticated algorithms we present for the management of normative positions, that is, the adoption and removal of permissions, obligations and prohibitions in societies of agents. We capture both direct and indirect conflicts between norms, formalise a practical concept of authority, and model conflicts that may arise as a result of delegation. We are able to formally define classic ways for resolving conflicts such as lex superior and lex posterior.     

Detection and resolution of normative conflicts in multi-agent systems: a literature survey

Multi-agents systems are composed of autonomous and possibly heterogeneous software agents that act according to their own interests. Some coordination mechanism must be adopted to ensure a proper functioning of the whole system. Norms can be viewed as a powerful means to regulate and influence the behaviour of the agents by specifying, for instance, obligations, permissions, or prohibitions in a given context. A critical issue that must be considered in a system governed by multiple norms is the possible existence of normative conflicts. A conflict between norms is a situation in which the fulfilment of a norm causes a violation of another one. In this paper, we present several techniques that have been proposed to detect and resolve normative conflicts in multi-agent systems. Our aim is to organize the literature, present a classification of the techniques found, and provide a means to compare alternative approaches dealing with normative conflicts.     

A Role Based Model for the Normative Specification of Organized Collective Agency and Agents Interaction

In this article we propose a role based model for the specification of organized collective agency, based on the legal concept of artificial person and on the normative perspective of organizational systems. We focus on the analysis of groups of agents (humans or not) that want to act collectively in a (more or less) permanent basis, and in a stable and organized way, as it is the typical case of organizations. We argue that in those cases such groups of agents should give rise to a new agent, that we call of institutionalized agent, with its own identity, whose structure is essentially defined through the characterization of a set of roles and whose behavior is determined by the acts of the agents that play such roles. We also present a deontic and action modal logic that captures the concept of acting in a role and relates it with the deontic notions of obligation, permission and prohibition. This logic is used in the formal specification of institutionalized agents and of societies of agents and in the rigorous analysis of them. We pay particular attention to the interaction between agents through contracts or other normative relations. A high level specification language is also suggested.     

Modelling social norms in multiagent systems

Social norms are cultural phenomena that naturally emerge in human societies and help to prescribe and proscribe normative patterns of behaviour. In recent times, the discipline of multi-agent systems has been used to model social norms in an artificial society of agents. In this paper we review norms in multi-agent systems and then explore a series of norms in a simulated urban traffic setting. Using game-theoretic concepts we define and offer an account of norm stability. Particularly in small groups, a relatively small number of individuals with cooperative attitude are needed for the norm of cooperation to evolve and be stable. In contrast, in larger populations, a larger proportion of cooperating individuals are required to achieve stability.     

NO Revision and NO Contraction

One goal of normative multi-agent system theory is to formulate principles for normative system change that maintain the rule-like structure of norms and preserve links between norms and individual agent obligations. A central question raised by this problem is whether there is a framework for norm change that is at once specific enough to capture this rule-like behavior of norms, yet general enough to support a full battery of norm and obligation change operators. In this paper we propose an answer to this question by developing a bimodal logic for norms and obligations called NO. A key to our approach is that norms are treated as propositional formulas, and we provide some independent reasons for adopting this stance. Then we define norm change operations for a wide class of modal systems, including the class of NO systems, by constructing a class of modal revision operators that satisfy all the AGM postulates for revision, and constructing a class of modal contraction operators that satisfy all the AGM postulates for contraction. More generally, our approach yields an easily extendable framework within which to work out principles for a theory of normative system change.     

Severity-sensitive norm-governed multi-agent planning

In making practical decisions, agents are expected to comply with ideals of behaviour, or norms. In reality, it may not be possible for an individual, or a team of agents, to be fully compliant—actual behaviour often differs from the ideal. The question we address in this paper is how we can design agents that act in such a way that they select collective strategies to avoid more critical failures (norm violations), and mitigate the effects of violations that do occur. We model the normative requirements of a system through contrary-to-duty obligations and violation severity levels, and propose a novel multi-agent planning mechanism based on Decentralised POMDPs that uses a qualitative reward function to capture levels of compliance: N-Dec-POMDPs. We develop mechanisms for solving this type of multi-agent planning problem and show, through empirical analysis, that joint policies generated are equally as good as those produced through existing methods but with significant reductions in execution time.     

Participant Selection for Short-term Collaboration in Open Multi-agent systems

In multi-agent systems, agents coordinate their behaviour and work together to achieve a shared goal through collaboration. However, in open multi-agent systems, selecting qualified participants to form effective collaboration communities is challenging. In such systems, agents do not have access to complete domain knowledge, they leave and join the systems unpredictably. More importantly, agents are mostly self-interested and have multiple goals and policies that may be even conflicting with others, which makes the participant selection even more challenging.Many of the current approaches are not applicable in constantly evolving open systems, where their performance will be affected by any unpredictable behaviour, agents’ lack of complete domain knowledge and the impossibility of having a central coordinator agent. In open systems, agents require a mechanism that enables them to dynamically change their perception of the environment and observe their neighbouring agents, so that they can identify qualified collaboration participants that have no conflicting goals and to balance their level of cooperation and self-interest.In this paper, we propose OPSCO, as a solution for On-demand Participant Selection for Short-term Collaboration in Open multi-agent systems. Unlike the existing research, we do not assume any predefined setting for agents’ structure in the system and do not have access to complete domain knowledge and allow each agent to build a dynamic dependency model and maintain when there is a change in the system. The model captures the agent’s most recent dependency structure of goals and policies with its neighbouring agents. It enables them to identify and select a qualified non-conflicting set of participants.OPSCO is evaluated in a real world open system smart grid and constrained resource sharing case studies. OPSCO outperforms other methods by selecting a qualified non-conflicting set of agents to collaborate. OPSCO balances the self-interest and level of cooperation and decreases failure in the overall agents’ goals (individual/shared).     

State space measures of robustness of pole locations for structured and unstructured perturbations

Measures of pole location robustness for linear feedback systems are derived from a state space model of the system. The robustness tests ensure that the eigenvalues of the perturbed systems matrix A + E remain in a desired region D of the complex plane containing the eigenvalues of the nominal system matrix A. The region D may be any open set of the complex plane whatsoever. The results are expressed in terms of induced matrix norms and apply to structured perturbations of the form E = BΔC, where B and C define the structure of E, and may be nonsquare matrices. Rank one perturbations E of minimal norm and with the given structure that will cause A + E to have an eigenvalue outside of D are constructed for the cases when the matrix norm is induced by the vector 1-norm or the vector ∞-norm. The advantages of having robustness measures for several matrix norms that can be computed are illustrated with a simple example that demonstrates how the conservatism of single tests can be reduced using several tests (i.e. several matrix norms). A method for computing numerically the robustness measures for particular norms is presented. It can be used to compute, with a guaranteed degree of accuracy, the maximum of the norm of the frequency response of a system.     

Off-line synthesis of evolutionarily stable normative systems

Within the area of multi-agent systems, normative systems are a widely used framework for the coordination of interdependent activities. A crucial problem associated with normative systems is that of synthesising norms that will effectively accomplish a coordination task and that the agents will comply with. Many works in the literature focus on the on-line synthesis of a single, evolutionarily stable norm (convention) whose compliance forms a rational choice for the agents and that effectively coordinates them in one particular coordination situation that needs to be identified and modelled as a game in advance. In this work, we introduce a framework for the automatic off-line synthesis of evolutionarily stable normative systems that coordinate the agents in multiple interdependent coordination situations that cannot be easily identified in advance nor resolved separately. Our framework roots in evolutionary game theory. It considers multi-agent systems in which the potential conflict situations can be automatically enumerated by employing MAS simulations along with basic domain information. Our framework simulates an evolutionary process whereby successful norms prosper and spread within the agent population, while unsuccessful norms are discarded. The outputs of such a natural selection process are sets of codependent norms that, together, effectively coordinate the agents in multiple interdependent situations and are evolutionarily stable. We empirically show the effectiveness of our approach through empirical evaluation in a simulated traffic domain.     

Using Gower Plots and Decision Balls to rank alternatives involving inconsistent preferences

Ranking alternatives involving inconsistent preferences is one of the most important topics in decision-making. Determining how to assist decision makers in understanding the decision context and adjusting inconsistencies in judgment are two important issues in ranking alternatives. This study proposes a visualization approach which will assist decision makers in ranking alternatives involving inconsistent preferences. Gower Plots are adopted to detect alternatives involving inconsistencies. An adjusting model is developed to provide suggestions for simultaneously improving ordinal and cardinal inconsistencies. A Decision Ball model is applied to visualize the decision context. By a graphical and interactive interface, decision makers can iteratively detect inconsistencies, choose the preferred way to adjust inconsistencies, observe relationships among alternatives, and then rank alternatives.