A context-based institutional normative environment

A Context-based Institutional Normative Environment Henrique Lopes Cardoso and Eug´enio Oliveira LIACC, DEI / Faculdade de Engenharia, Universidade do Porto R. Dr. Roberto Frias, 4200-465 Porto, Portugal {hlc,eco}@fe.up.pt Abstract. We explore the concept of an agent-based Electronic Institution including a normative environment that supports electronic contract formation by providing a contextual normative background. We formalize the normative state using first-order logic and define institutional rules and norms operating on that state. A suitable semantics regarding the use of norms within a hierarchical context structure is given, based on norm activation conflict and defeasibility. Norm activation relies on substitution as in first-order logic. Reasoning about the fulfillment and violation of deadline obligations is formalized using linear temporal logic; implementation with institutional rules is discussed. Examples exploiting the normative environment are given. Key words: Normative Environment, Context, Norm Activation, Defeasibility 1 Introduction Electronic Institutions [1][2][3] have been proposed and developed as frameworks embedding normative environments for open multi-agent systems, where heterogeneous and independently developed agents interact. Differences exist concerning the conceptual views of the “institutional environment”. In [1] a restrictive “rules of the game” approach is followed, where the institution fixes what agents are allowed to do; norms are in this case a set of interaction conventions that agents must conform to. In [2] the institution is seen as an external entity that ascribes institutional powers and normative positions, while admitting norm violations and prescribing appropriate sanctions. In our perspective [3], an Electronic Institution (EI) is a software framework embracing a set of services and a normative environment. Those services are meant to assist software agents in the process of creating organizational structures ruled by a set of mutual commitments, which in the end are translated into norms. Such norms are part of the normative environment that is maintained by the EI. In fact, one of the core services that we consider is the provision of a supportive normative framework in the institutional environment, which agents can exploit in order to establish their contracts in a more straightforward fashion. Contracts [4] can be underspecified, relying on a structured normative environment that fills in any omissions. The purpose of this paper is to formalize this normative environment. We define the notion of normative context, based on which a hierarchical structure provides a normative background for electronic contracts. Within that structure, we characterize the normative state of the system and define rules and norms operating on that state. We give a proper semantics for norms in our system by defining norm activation conflict and by providing an approach for conflict resolution based on defeasibility. We also detail the semantics of deontic statements (namely obligations with deadlines) using temporal logic, and discuss implementation issues. The paper is organized as follows. Section 2 presents our institutional normative environment, based on context structures, including the normative state, rules and norms. Section 3 describes the semantics associated with norms, including defeasibility; deadline obligation semantics is also explored and implemented with rules. In Section 4 we illustrate the exploitation of the normative environment. Section 5 concludes and discusses related work. 2 An Institutional Normative Environment We explore the concept of an agent-based EI including a normative environment as its core component. In the following definitions we try to provide a sound presentation of concepts in order to explain the use of norms within the normative environment. Definition 1. Normative Environment NE =hNS,IR,Ni The normative environment NE of an EI is composed of a normative state NS, a set IR of institutional rules that manipulate that normative state and a set Nof norms, which can be seen as a special kind of rules. While norms (see Def. 8) define the normative positions of each agent, the main purpose of institutional rules (see Def. 7) is to relate the normative state with the standing normative positions. A typical use of institutional rules is illustrated in subsection 3.2, where they are employed to implement the semantics of deadline obligations – rules monitor the normative state NS in order to detect the fulfillment or violation of deontic statements. On the other hand, norms “produce” those deontic statements upon certain normative state conditions. 2.1 Contexts Our model is based on a contextualization of both the normative state and norms. In this subsection we properly introduce the notion of context and context organization. Definition 2. Context C =hPC,CA,CI ,CN i A context Cis an organizational structure within which a set CA of agents commits to a joint activity partially regulated by a set CN ⊆N of appropriate norms. A context includes a set CI of contextual info that makes up a kind of background knowledge for that context (see Def. 4). PC is the parent context within which context Cis formed. Let PCA be the set of agents in context PC: we have that CA ⊆PCA. Contexts allow us to organize norms according to a hierarchical normative structure. Norm set Nis partitioned into the several contexts that may exist, that is, sets CN for each context are mutually disjoint. Typically, we will have CN ⊂N, in which case more than one context has a non-empty set CN ; only if all norms in Nare defined in the same context we may have CN =N. A norm inheritance mechanism, as explained later, justifies the fact that the locallydefined set CN of norms only partially regulates the activity of agents in set CA. We identify a top level context from which all other contexts are (directly or indirectly) formed; every agent is committed to the top context. We now introduce the notion of sub-context. Definition 3. Sub-context C0=hPC0,CA0,CI 0,CN 0i A context C0is a sub-context of a context C =hPC ,CA,CI ,CN i, denoted C0CC, if PC0=C or if PC0CC. When C0is either a subcontext of Cor Citself, we write C0EC. From Def. 2 we also have that CA0⊆CA. A sub-context defines a sub-activity committed to by a subset of the original context’s agents. Notice that the sub-context relationship is an explicit one. Every context is a sub-context of the top context. We now turn to the definition of background information that may be defined as a foundational element of a context. Definition 4. Contextual info InfoC Contextual info InfoCis a fully-grounded atomic formula in first-order logic, which comprises founding information regarding a context C=hPC,CA,CI ,CN i. InfoC∈CI . The CI component in a context definition is therefore composed of first-order logic formulae that provide background information for that context. A B2B analogy to this kind of context/sub-context relationship comes from the virtual organizations realm, wherein a group of enterprises seeks to build a mutually beneficial relationship regarding a specific business domain. They would form a contractual agreement within the top institutional context. Often, a contract is dependent on the existence of another business relation, which forms the business context for the new contract. Each contract must contain a set of definitions regarding the role of the participants, the values to be exchanged (products or services) and their provision. In our model, these comprise information that is intrinsic and foundational to the context associated with this contract – hence the term contextual info. In Section 4 a supply-agreement contract is described, in which a set of agents agrees to supply certain resources under certain conditions. In that context, contextual info is expressed as first-order formula relating each agent with a resource it supplies, together with an associated price: supply–infoC(Ag,Res,UPr). 2.2 Normative State The normative state is organized through contexts. The normative state concerns the description of what is taken for granted in a model of so-called institutional reality [5]. Therefore, we call every formula in NS an institutional reality element, or IRE. Each IRE refers to a specific context within which it is relevant. There can be more than one IRE pertaining to the same context. Definition 5. Contextual institutional reality element IREC A contextual institutional reality element IRECis an IRE regarding context C. We distinguish the following kinds of IRECwith the following meanings: ifactC(f,t)– institutional fact fhas occurred at time t timeC(t)– instant thas elapsed oblC(a,f,t)– agent ais obliged to bring about fact funtil deadline t fulf C(a,f,t)– agent ahas fulfilled at time this obligation to bring about f violC(a,f,t)– agent ahas violated at time this obligation to bring about f Note that the use of context Cas a superscript is only a syntactical convenience – both contextual info and institutional reality elements are first-order formulae (Ccould be used as the first argument of each of these formulae). While contextual info is confined to background information that is part of the context definition, contextual institutional reality elements represent occurrences taking place after the context’s creation, during its lifetime. We consider institutional facts as agent-originated, since they are obtained as a consequence of some agent action [4]. The remaining elements are environment events, asserted in the process of norm application and monitoring. Our model of institutional reality is based on a discrete model of time. The time elements are used to signal instants that are relevant to the context at hand. Obligations are deontic statements, and we admit both their fulfillment and violation. Definition 6. Normative State NS ={IREC1 1,IREC2 2, ..., IRECm n} The normative state NS is a set of fully-grounded atomic formulae IRECj i, 1≤i≤n, in first-order logic. The normative state will contain, at each moment, all elements that characterize the current state of affairs in every context. In that sense, NS could be seen as being partitioned among the several contexts, as is the case with norms; however, IRE’s are not part of a context’s definition, since they are obtained at a later stage, during the context’s operation. Some of the IRE’s are interrelated: for instance, a fulfillment connects an obligation to bring about a fact with its achievement as an institutional fact. These interrelations are captured with institutional rules. 2.3 Rules and Norms Given the “contextualization” of the normative state, we are now able to define rules and norms. Institutional rules allow us to maintain the normative state of the system. They are not contextualized, but yet they operate on contextual IRE’s. Definition 7. Institutional rule R ::= Antecedent →Consequent An institutional rule Rdefines, for a given set of conditions, what other elements should be added to the normative state. The rule’s Antecedent is a conjunction of patterns of IREC(see Def. 5), which may contain variables; restrictions may be imposed on such variables through relational conditions. We also allow the use of negation (as failure): Antecedent ::= IREC|Antecedent ∧Antecedent | ¬Antecedent | RelCondition The rule’s Consequent is a conjunction of IRECwhich are not deontic statements (IRE–C), and which are allowed to contain bounded variables: Consequent ::= IRE–C|Consequent ∧Consequent When the antecedent matches the normative state using a first-order logic substitution Θ, and if all the relational conditions over variables hold, the atomic formulae obtained by applying Θto the consequent of the rule are added to the normative state as fully-grounded elements. Besides institutional reality elements, the norms themselves are also contextual. Definition 8. Norm N C=Situation →Prescription A norm NCis a rule with a deontic consequent, defined in a specific context C. The norm is applicable to a context C0EC. The norm’s Situation is a conjunction of patterns of InfoC0and IRE–C0(no deontic statements). Both kinds of patterns are allowed to contain variables; restrictions may be imposed on such variables through relational conditions: Situation ::= InfoC0|IRE–C0|Situation ∧Situation |RelCondition The norm’s Prescription is a (possibly empty) conjunction of deontic statements (obligations) which are allowed to contain bounded variables and are affected to the same context C0: Prescription ::= |OblConj OblConj ::= oblC0(...)∧OblConj |oblC0(...) Conceptually, the norm’s Situation can be seen as being based on two sets of elements: background (Sb) and contingent (Sc). Background elements are those that exist at context creation (the founding contextual info), while contingent elements are those that are added to the normative state at a later stage. This distinction will be helpful when describing norm semantics. Observe the distinction between the context where the norm is defined, and the context to which the norm applies. While, in order to make the model as simple as we can, we define a norm as being applicable to a specific context, in Section 3.1 we relax this assumption, which will in part clarify the usefulness of the model. 3 Semantics After defining each component of our normative environment, we now proceed to defining the semantics of norms and deontic statements. 3.1 Norms and Contexts We now turn our attention to norm applicability according to the normative state. For that, we make use of the notion of substitution in first-order logic. We denote by f·Θthe result of applying substitution Θto atomic formula f. Definition 9. Norm activation A norm NC=S→P, applicable to a context C0=hPC 0,CA0,CI 0,CN 0i, is said to be activated if there is a substitution Θsuch that: –∀c∈Sc c·Θ∈NS, where Sc is the set of contingent conjuncts (IRE–C0 patterns) in S; and –∀b∈Sb b·Θ∈CI 0, where Sb is the set of background conjuncts (InfoC0 patterns) in S; and –all the relational conditions over variables hold. We are now able to define the notion of conflicting norm activations, as follows. Definition 10. Norm activation conflict Let Act1be the activation of norm NC1 1=S1→P1obtained with substitution Θ1and Act2the activation of norm NC2 2=S2→P2obtained with substitution Θ2. Let NS1={c·Θ1|c∈Sc1}, and NS2={c·Θ2|c∈Sc2}, where Sc1and Sc2are the sets of contingent conjuncts of S1and S2, respectively. Both NS1and NS2represent fractions of the whole normative state NS. Norm activations Act1and Act2are in conflict, written Act1NAct2, if NS1=NS2and either C1CC2or C2CC1. Succinctly, we say there is a norm activation conflict if we have two applicable norms activated with the same fraction of the normative state and defined in different contexts. Notice that the fact that both norms are activated with the same contextual IRE’s already dictates that the norm contexts, if different, have a sub-context relationship (there is no multiple inheritance mechanism in our normative structure). This becomes clearer when taking into account the sub-context (Def. 3) and norm (Def. 8) definitions: a context has a single parent context, and a norm NCapplies to a context C0EC. In principle, all norm activations are defeasible, according to the following definition. Definition 11. Norm activation defeasance A norm activation Act1for norm NC0 1defeats a norm activation Act2 for norm NC00 2if Act1NAct2and C0CC00. A defeated norm activation is discarded, that is, the defeated activation is not applied to the normative state fraction used for activating the norm. Only undefeated norm activations will be applied: the substitution that activated a norm is applied to its prescription part and the resulting fully-grounded deontic statements are added to the normative state (recall that there are no free variables in the prescription part of norms). Observe that we do not talk about norm defeasance, but rather norm activation defeasance. Thus, the defeasance relationship may only materialize on actual norm applicability. Norm Contextual Target. A question that may arise when going through the previous definitions can jeopardize the purpose of having defeasible norms as those in the model presented. Why should there be norms that, while being applicable to the same context, are defined in different contexts that have a subcontext relationship? Why not have all norms applicable to context Cdefined inside context C? The reason for our approach becomes apparent when considering the stated aim of a supportive normative environment: to have a normative background that can fill-in details of sub-contexts that are created later and that can benefit from this setup by being underspecified. This leads us to the subject of “default rules” in the law field [6]. Thus, part of the normative environment’s norms will typically be predefined, in the sense that they are pre-existent to the applicable contexts themselves. What we need is to typify contexts in order to be able to say that a norm applies to a certain type of contexts. This way, a norm might be defined at a super-context and applicable to a range of sub-contexts (of a certain type) to be subsequently created. We can do this adaptation by considering context identifier Cas a pair id:type, where id is a context identifier and type is a predefined context type. In a norm NC=S→P(see Def. 8), patterns of InfoC0and IREC0within Sand P will be rewritten to accommodate this kind of context reference, eventually using a variable in place of the context id. For instance, an IREId:xpattern, where Id is a variable, would match IRE’s of any sub-context of type x. When activating a norm with this kind of pattern, the substitution Θ(as used in Def. 9) would have to bind Id to a specific sub-context identifier; every further occurrence of Id is thus a bounded-variable. This approach allows us to maintain our definitions of norm activation conflict and defeasance, with minor syntactical changes. 3.2 Deadline Obligations Our definition of norm includes the set of conditions upon which one or more deontic statements come into place. As such, obligations being added to the normative state are no longer conditional: they are deadline obligations, in the sense discussed in [7]. In the following explanation we borrow some operators from linear temporal logic (LTL) [8]. In LTL time is assumed to be discrete, has an initial moment with no predecessors, and is infinite into the future. Let x= (s0, s1, s2, ...) be a timeline, defined as a sequence of states si. The syntax x|=preads that pis true in timeline x. We write xkto denote state skof x, and xk|=pto mean that pis true at state xk. The following operators shall be used: –until (U): x|= (p U q)iff ∃j(xj|=q and ∀k<j(xk|=p)) –before (B): x|= (p B q)iff ∀j(xj|=q implies ∃k<j(xk|=p)) –henceforth (G): x|=Gq iff ∀j(xj|=q) The fulf and viol terms in Def. 5 allow us to reason about the fulfillment and violation of obligations. Using these terms, a deadline obligation oblC(a,f,t) has the following semantics in LTL: (¬ifactC(f,t0)∧ ¬timeC(t)∧ ¬fulf C(a,f,t)∧ ¬violC(a,f,t)) U (ifactC(f,t0)∧ ¬timeC(t)∧Gfulf C(a,f,t)∧G¬violC(a,f,t))∨ (¬ifactC(f,t0)∧timeC(t)∧G¬fulf C(a,f,t)∧GviolC(a,f,t)) (1) This means that no violations can occur before the deadline, nor fulfillments before accomplishments; also, fulfillments and violations are mutually exclusive and persist over time. In order to make the above formalization more tractable, we relate a deadline obligation with conditions for its fulfillment and violation. In LTL we express these relationships with: oblC(a,f,t)∧(ifactC(f,t0)B timeC(t)) ⇒Gfulf C(a,f,t) (2) oblC(a,f,t)∧(timeC(t)B ifactC(f,t0)) ⇒GviolC(a,f,t) (3) Basically we are depending on which comes first: the deadline or the accomplishment of the fact. But in a model of discrete time, they can occur simultaneously (which is captured by operator @ defined below). In this case none of the above implications apply. So we add: oblC(a,f,t)∧(ifactC(f,t0) @ timeC(t)) ⇒Gfulf C(a,f,t) (4) where1(ρ@δ)≡(¬ρ U δ)∧(¬δ U ρ)≡ ¬(ρ B δ)∧ ¬(δ B ρ). We want obligations not to persist after the deadline. This allows us to model, within this framework, both cases of legal obligations, namely obligations that stand even when violated and those that do not. For instance [7], an obligation 1(ρ@δ) could also be defined as x|= (ρ@δ)iff ∃j(xj|= (ρ∧δ)and ∀k<j(xk|= (¬ρ∧ ¬δ))) to pay for a fine will persist if it is not fulfilled until the deadline, while an obligation to submit a conference paper will not persist after the submission deadline (because submitting makes no sense at that stage). For modeling a standing obligation, the obligation can be reinstated after a violation is detected. This property can be stated in a more general way: a fulfilled obligation cannot be violated anymore, and a violated obligation cannot be fulfilled anymore. oblC(a,f,t)∧fulf C(a,f,t)⇒G¬violC(a,f,t) (5) oblC(a,f,t)∧violC(a,f,t)⇒G¬fulf C(a,f,t) (6) These relationships weaken the obligation’s power after it has been fulfilled or violated. Implementation with Institutional Rules. As mentioned before, the normative environment (Def. 1) includes a set IR of institutional rules (Def. 7) that manipulate the normative state. Such rules allow us to implement the semantics of deontic statements, as defined above. The fulf and viol terms in Def. 5 are meant to allow us to reason about the fulfillment and violation of obligations as soon as they occur, by defining norms that take these elements into account in their antecedent. Institutional rules enable the specification of conditions for fulfillment and violation detection. According to the deadline obligation semantics described above, namely (2) and (3), we may have the following institutional rules: oblC(a,f,t)∧ifactC(f,t0)∧ ¬timeC(t)→fulf C(a,f,t) (7) oblC(a,f,t)∧timeC(t)∧ ¬ifactC(f,t0)→violC(a,f,t) (8) But what if both the fact and the deadline hold at some point? If (ifactC(f,t0)B timeC(t)), then rule (7) asserted a fulfillment; if (timeC(t)B ifactC(f,t0)), then rule (8) asserted a violation. But what if (ifactC(f,t0) @ timeC(t))? A rule like: oblC(a,f,t)∧ifactC(f,t0)∧timeC(t)→fulf C(a,f,t) (9) is not acceptable, as it would hold if (timeC(t)B ifactC(f,t0)). We need to keep the property that after being violated, the obligation cannot be fulfilled anymore (as in (6) above). We may say: oblC(a,f,t)∧ifactC(f,t0)∧ ¬violC(a,f,t)→fulf C(a,f,t) (10) It is tempting to also explicitly state that violations can only occur if no fulfillment was achieved before. Something like: oblC(a,f,t)∧timeC(t)∧ ¬fulf C(a,f,t)→violC(a,f,t) (11) However, when taken together with (10), this would imply that a simultaneous occurrence of ifactC(f,t0) and timeC(t) (that is, ifactC(f,t0) @ timeC(t)) could bring either a fulfillment or a violation! We therefore must join (8) with (10). (Notice that the pairing of (7) with (11) would bring a violation in the simultaneity case.)