Normative Multiagent Systems: The Dynamic Generalization

1 Introduction

Multiagent systems have been used to model and analyse distributed and heterogeneous systems, with agents being suitable for modelling software processes and physical resources. Roughly speaking, autonomy means that the system by itself, or the agents in the system, can decide for themselves what to do and when to do it [Fisher et al., 2013]. To facilitate autonomous behaviours, agents are provided with capabilities, e.g., to gather information by making observations (via e.g., sensors) and communicating with each other (via e.g., wireless network), to a↵ect the environment and other agents by taking actions, etc. Moreover, systems and agents may have specific objectives to pursue. In this paper, we study autonomy issues related to social norms [Shoham and Tennenholtz, 1992], which are powerful formalism for the coordination of agents, by restricting their behaviour to prevent destructive interactions from taking place, or to facilitate positive interactions [van der Hoek et al., 2007; Ågotnes and Wooldridge, 2010].

Existing normative systems [Wooldridge and van der Hoek, 2005; Ågotnes et al., 2007; Christelis and Rovatsos, 2009; Ågotnes and Wooldridge, 2010; Morales et al., 2013] impose restriction rules on the multiagent systems to disallow agents' actions based on the evaluation of current system state. An implicit assumption behind this setting is that the normative systems do not have (normative) states to describe di↵erent social norms under di↵erent circumstances. That is, they are static normative systems. Specifically, if an action is disallowed on some system state then it will remain disallowed when the same system state occurs again. However, more realistically, social norms may be subject to changes. For example, a human society has di↵erent social norms in peacetime and wartime, and an autonomous multiagent system may have di↵erent social norms when exposed to di↵erent levels of cyber-attacks. This motivates us to propose a new definition of normative systems (in Section 3), to enable the representation of norms under multiple states (hence, dynamic normative systems). With a running example, we show that a dynamic normative system can be a necessity if a multiagent systemwants to implement certain objectives.

We focus on two related autonomy issues 1 . The first is norm synthesis, which is to determine the existence of a normative system for the achievement of objectives. The success of this problem suggests the autonomy of the multiagent system with respect to the objectives, i.e., if all agents in the system choose to conform to the normative system 2 , the objectives can be achieved. For static normative systems, norm synthesis problem is shown to be NP-complete [Shoham and Tennenholtz, 1995]. For our new, and more general, definition of normative systems, we show that it is EXPTIMEcomplete. This encouraging decidable result shows that the maximum number of normative states can be bounded.

The second is norm recognition, which can be seen as a successive step after deploying an autonomous multiagent systems (e.g., by norm synthesis). For deployed systems such as [Chalupsky et al., 2001], it can be essential to allow new agents to join anytime. If so, it is generally expected that the new agent is able to recognise the current social norms after playing in the system for a while. Under this general description, we consider two subproblems related to the autonomy of the system and the new agent, respectively. The first one, whose complexity is in PTIME, tests whether the system, under the normative system, can be autonomous in ensuring that the new agent can eventually recognise the norms, no matter how it plays. If such a level of autonomy is unachievable, we may consider the second subproblem, whose success suggests that if the new agent is autonomous (in moving in a smart way) then it can eventually recognise the norms. We show that the second subproblem is PSPACE-complete.

1 In this paper, we consider decision problems of these autonomy issues. The algorithms for the upper bounds in Theorem 1, 2, and 3 can be adapted to implement their related autonomy.

2 The synthesised normative system is a common knowledge [Fagin et al., 1995] to the agents.

2 Partial ObservationMultiagent Systems

A multiagent system consists of a set of agents running in an environment [Fagin et al., 1995]. At each time, every agent takes a local action independently, and the environment updates its state according to agents' joint action. We assume that agents have only partial observations over the system states, because in most real-world systems, agents either do not have the capability of observing all the information (e.g., an autonomous car on the road can only observe those cars in the surrounding area by its sensors or cameras, etc) or are not supposed to observe private information of other agents (e.g., a car cannot observe the destinations of other cars, etc).

Let Agt be a finite set of agents and Prop be a finite set of atomic propositions. A finite multiagent system is a tuple M = (S, {Acti}i2Agt, {Li}i2Agt, {Oi}i2Agt, I, T, ⇡), where S is a finite set of environment states, Acti is a finite set of local actions of agent i 2 Agt such that Act = Act1⇥...⇥Actn is a set of joint actions, Li : S !P(Acti)\{;} provides on every state a nonempty set of local actions that are available to agent i, I ✓ S is a nonempty set of initial states, T ✓ S ⇥ Act ⇥ S is a transition relation such that for all s 2 S and a 2 Act there exists a state s 0 such that (s, a, s 0 ) 2 T, Oi : S ! O is an observation function for each agent i 2 Agt such that O is a set of possible observations, and ⇡ : S ! P(Prop) is an interpretation of the atomic propositions Prop at the states. We require that for all states s1, s2 2 S and i 2 Agt, Oi(s1) = Oi(s2) implies Li(s1) = Li(s2), i.e., an agent can distinguish two states with di↵erent sets of next available actions.

Example 1 We consider a business system with two sets of autonomous agents: the producer agents P = {p1, ..., pn}, and consumer agents C = {c1, ..., cm}. Let Agt = P[C. Each producer agent p j 2 P produces a specific kind of goods with limited quantity each time. There can be more than one agents producing the same goods. We use gj 2 G to denote the kind of goods that are produced by agent pj, and bj 2 N to denote the number of goods that can be produced at a time. Every consumer agent ci 2 C has a designated job which needs a set of goods to complete. It is possible that more than one goods of a kind are needed. We use ri to denote the multiset of goods that are required by agent ci.

We use rri ✓ ri to denote the multiset of remaining goods to be collected for ci, di 2 G 0 = G[ {?} to represent ci's current demand, and ti 2 P 0 = P[{?} to represent the producer agent fromwhom ci is currently requesting goods. Every interaction of agents occurs in two consecutive rounds, and we use k 2 {1, 2} to denote the current round number.

Because gj, bj, ri do not change their values in a system execution, we assume that they are fixed inputs of the system. The multiagent system M has the state space as

where the first component {1, 2} is for the round number. The initial states are I = {1} ⇥ ⇧i2{1,...,m}{(;, ?, ?)}.

The consumer agent ci has a set of actions Actci = {a?} [ {apj | pj 2 P}. Intuitively, a? means that an agent does nothing, and the action apj means that agent ci sends a request to producer pj for its goods. The producer agent pj has a set of actions Actpj = {a?} [ {aB | B ✓ C, |B|  bj}. Intuitively, the action aB for B a subset of agents represents that agent p j satisfies the requests from agents in B.

We use pseudocode to describe the transition relation. In the first round, i.e., k = 1, it can be described as follows.

R1a. all consumer agents ci do the following sequential steps:

• (a) if rri = ; then we let rri = ri. Intuitively, this represents that agent ci's job is repeated.
• (b) if di = ? then do the following: let di 2 rri, choose an agent pj such that di = gj, and let ti = pj. Intuitively, if there is no current demand, then a new demand di 2 rri is generated, and ci sends a request to a producer agent pj who is producing goods di.

R1b. all producer agents pj execute action a?, and let k = 2.

In the second round, i.e., k = 2, it can be described as follows.

R2a. all producer agents pj do the following sequential steps:

• (a) select a maximal subset B of agents such that B ✓ {ci | ti = pj} and |B|  bj. Intuitively, from the existing requests, the producer agent pj selects a set of them according to its production capability.
• (b) for all agents ci in B, let rri = rri \ {gj} and di = ti = ?. Intuitively, if a demand di is satisfied, then it is removed from rri and we let di = ti = ?.

R2b. all consumer agents execute action a?, and let k = 1.

We use "var = val", for var a variable and val one of its values, to denote an atomic proposition. Then the labelling function ⇡ can be defined naturally over the states. The observation Oi will be discussed in Section 6.

We provide a simple instantiation of the system 3 . Let n = 2, G = {g1, g2}, b1 = b2 = 1 (two agents produce goods one at each time), m = 3, r1 = {g1}, r2 = {g2} and r3 = {g1, g2} (three consumers with the required goods). From the initial state s0 = (1, (;,?,?), (;,?,?), (;,?,?)), we may have the following two states such that (s0, (a?, a?, ap1 , ap2 , ap1 ), s 0 2 ) 2 T and (s 0 2 , (a{c1}, a{c2}, a?, a?, a?), s 0 1 ) 2 T:

s 0 1 = (1, ({}, ?, ?), ({}, ?, ?), ({g1, g2}, g1, p1))

( s 0 2 = (2, ({g1}, g1, p1), ({g2}, g2, p2), ({g1, g2}, g1, p1)), and

3 Dynamic Normative Systems

The following is our new definition of normative systems.

Definition 1 A dynamic normative system of a multiagent system M = (S, {Acti}i2Agt, {Li}i2Agt, {Oi}i2Agt, I, T, ⇡) is a tuple NM = (Q, δn, δu, q0) such that Q is a set of normative states, δn : S ⇥ Q ! P(Act) is a function specifying, for each environment state and each normative state, a set of joint actions that are disallowed, δu : Q ⇥ S ! Q is a function specifying the update of normative states according to the changes of environment states, and q0 is the initial normative state.

A (static) normative system in the literature can be seen as a special case of our definition where the only normative state is q0. In such case, we have Q = {q0}, δu(q0, s) = q0 for all s 2 S , and can therefore write the function δn as function

3 The instantiation is simply to ease the understanding of the definitions in Example 1 and 2. The conclusions for the example system (i.e., Proposition 1, 2, 3, 4, 5) are based on the general definition.

δ : S ! P(Act). It is required that the function δn (and thus δ) does not completely eliminate agents' joint actions, i.e., δn(s, q) ⇢ ⇧i2AgtLi(s) for all s 2 S and q 2 Q.

We give two dynamic normative systems.

Example 2 Let M be the multiagent system given in Example 1. Let s1 and s2 range over those environmental states such that k = 1 and k = 2, respectively.

The normative system N 1 M = (Q 1 , δ 1 n , δ 1 u , q 1 0 ) is such that:

• Q 1 = ⇧pj2P{1, ...,m}, where each producer maintains a number indicating the consumer whose requirement must be satisfied in this normative state,
• δ 1 n (s1, q) = ;, i.e., no joint actions are disallowed on s1, and (aB1 , ..., aBn , a?, ..., a?) 2 δ 1 n (s2, (y1, ..., yn)) if there exists j 2 {1, ..., n} such that Bj ✓ C and cyj < Bj. Intuitively, for producer agent pj, an action aBj is disallowed on the second round if Bj does not contain the consumer cy j who is needed to be satisfied in this round.
• δ 1 u (q, s2) = q and δ 1 u ((y1, ..., yn), s1) = (y 0 1 , ..., y 0 n ) such that y 0 j = (yj mod m) + 1 for j 2 {1, ..., n}; intuitively, the normative state increments by 1 and loops forever.
• q 1 0 = (1, ..., n), i.e., producer agents pj start from cj.

For the instantiation in Example 1, we have that

• Q 1 = {1, 2, 3} ⇥ {1, 2, 3}, q 1 0 = (1, 2),
• δ 1 u ((1, 2), s1) = (2, 3), δ 1 u ((2, 3), s1) = (3, 1).
• (aB1 , aB2 , a?, a?, a?) 2 δ 1 n (s 0 2 , (1, 2)) if either B1 2 {;, {c2}, {c3}, {c2, c3}} or B2 2 {;, {c1}, {c3}, {c1, c3}},

We define another normative system N 2 M = (Q 2 , δ 2 n , δ 2 u , q 2 0 ) by extending the number maintained by each producer into a first-in-first-out queue so that the ordering between consumers who have sent the requests matters. That is, we have Q 2 = ⇧pj2P({✏} [ {i1...ik | k 2 {1, ...,m}, ix 2 C for 1  x  k}) where the symbol ✏ denotes an empty queue, and q 2 0 = ⇧pj2P{✏} which means that producers start from empty queues. The functions δ 2 n and δ 2 u can be adapted from N 1 M , and details are omitted here due to space limit.

The following captures the result of applying a normative system on a multiagent system, which is essentially a product of these two systems.

Definition 2 Let M be a multiagent system and NM a normative system on M, the result of applying NM on M is a Kripke structure K(NM) = (S † , I † , T † , ⇡ † ) such that

• S † = S ⇥ Q is a set of states,
• T † ✓ S † ⇥S † is such that, for any two states (s1, q1) and (s2, q2), we have ((s1, q1), (s2, q2)) 2 T † if and only if, (1) there exists an action a 2 Act such that (s1, a, s2) 2 T and a < δn(s1, q1), and (2) q2 = δu(q1, s2). Intuitively, the first condition specifies the enabling condition to transit from state s1 to state s2 by taking a joint action a which is allowed in the normative state q1. The second condition specifies that the transition relation needs to be consistent with the changes of normative states.
• I † = I ⇥ {q0} is a set of initial states,
• ⇡ † : S † !P(Prop) is such that ⇡ † ((s, q)) = ⇡(s).

Example 3 For the instantiation, in the structure K(N 1 M ), we have ((s0, (1, 2)), (s 0 2 , (1, 2))), ((s 0 2 , (1, 2)), (s 0 1 , (2, 3))) 2 T † . The latter is because (s 0 2 , (a{c1}, a{c2}, a?, a?, a?), s 0 1 ) 2 T, {c1} < {;, {c2}, {c3}, {c2, c3}}, and {c2} < {;, {c1}, {c3}, {c1, c3}}.

On the other hand, for a = (a{c1}, a{c3}, a?, a?, a?) and s 00 1 = (1, ({}, ?, ?), ({g2}, g2, p2), ({g1}, ?, ?)), we have (s 0 2 , a, s 00 1 ) 2 T but ((s 0 2 , (1, 2)), (s 00 1 , (2, 3))) < T † . This is because, for p2, it is required to make c2 as its current priority according to the normative state, and cannot choose to satisfy c3 instead.

We remark that, the normative system, as many current formalisms, imposes hard constraints on the agents' behaviour. As stated in e.g., [Boella et al., 2006], social norms may be soft constraints that agents can choose to comply with or not. To accommodate soft social norms, we can redefine the function δn as δn : S ⇥ Q ⇥ Act ! U to assign each joint action a cost utility for every agent, on each environment state and normative state. With this definition, norms become soft constraints: agents can choose to take destructive actions, but are encouraged to avoid them due to their high costs. The objective language to be introduced in the next section also needs to be upgraded accordingly to express properties related to the utilities. We leave such an extension as a future work.

4 Objective Language

To specify agents' and the system's objectives, we use temporal logic CTL [Clarke et al., 1999] whose syntax is as follows.

A path in a Kripke structure K(NM) is a sequence s0s1... of states such that (si, si+1) 2 T † for all i ≥ 0. The semantics of the language is given by a relation K(NM), s |= φ for s 2 S † , which is defined inductively as follows [Clarke et al., 1999]:

where p 2 Prop. Intuitively, formula EXφ expresses that φ holds at some next state, E(φ1 U φ2) expresses that on some path from current state, φ1 holds until φ2 becomes true, and EGφ expresses that on some path from current state, φ always holds. Other operators can be obtained as usual, e.g., EFφ ⌘ E(T rue U φ), AGφ ⌘ ¬E(T rue U ¬φ), AFφ = ¬EG¬φ etc.

1. K(NM), s |= p if p 2 ⇡ † (s),
2. K(NM), s |= φ1 _ φ2 if K(NM), s |= φ1 or K(NM), s |= φ2,
3. K(NM), s |= ¬φ if not K(NM), s |= φ,
4. K(NM), s |= EXφ if there exists a state s 0 2 S † such that (s, s 0 ) 2 T † and K(NM), s 0 |= φ,
5. K(NM), s |= EGφ if there exists a path s0s1 . . . such that s0 = s and K(NM), sk |= φ for all k ≥ 0.
6. K(NM), s |= E(φ1 U φ2) if there exists a path s0s1 . . . and a number n ≥ 0 such that s0 = s, K(NM), sk |= φ1 for 0  k  n - 1 and K(NM), sn |= φ2,

The verification problem, denoted as K(NM) |= φ, is, given a multiagent system M, its associated normative system NM, and an objective formula φ, to decide whether K(NM), s |= φ for all s 2 I † . The norm synthesis problem is, given a system M and an objective formula φ, to decide the existence of a normative system NM such that K(NM) |= φ. The norm recognition problem will be defined in Section 6. For the measurement of the complexity, we take the standard assumption that the sizes of the multiagent system and the normative system are measured with the number of states, and the size of the objective formula is measured with the number of operators.

Example 4 For the system in Example 1, interesting objectives expressed in CTL may include

which says that it is always the case that if there is a request from a consumer ci to a producer pj (i.e., ti = pj), then the request is possible to be satisfied eventually (i.e., di = ?), and

which says that it is always the case that if there is a request from a consumer ci to a producer pj, then on all the paths the request will eventually be satisfied. Both φ1 and φ2 are liveness objectives that are important for an ecosystem to guarantee that no agent can be starving forever. The objective φ2 is stronger than φ1, and their usefulness is applicationdependent. The following proposition shows that static normative systems are insufficient to guarantee the satisfiability of the objectives in this ecosystem.

Proposition 1 There exists an instance of a multiagent system M such that, for all static normative systems NM, we have that K(NM) 6 |= φ1 ^ φ2.

The proof idea is based on the following simple case. Assume that there are one producer p1, such that b1 = 1, and two consumers c1 and c2, such that r1 = r2 = {g1}. There only exist the following three static normative systems which have di↵erent restrictions on an environment state s2 = (2, ({g1}, g1, p1), ({g1}, g1, p1)): (Recall that q0 is the only normative state in static normative systems.)

• N 3 M is such that δ 3 n (s2, q0) = {a{c1}}, i.e., c1 is not satisfied.
• N 5 M is such that δ 5 n (s2, q0) = ;, i.e., no restriction.
• N 4 M is such that δ 4 n (s2, q0) = {a{c2}}, i.e., c2 is not satisfied.

We can see that K(N h M ) 6 |= φ1 for h 2 {3, 4} and K(N 5 M ) 6 |= φ2. The former is because one of the agents is constantly excluded from being satisfied. For the latter, there exists an infinite path s0(s2s1) 1 such that s0 = (1, (;,?,?), (;,?,?)) is an initial state, s2 is given as above, and s1 = (1, (;, ?, ?), ({g1}, g1, p1)) is the state on which consumer c 1 i 's requirement is satisfied. On this path, the requirement from c 2 i is never satisfied. On the other hand, for the dynamic normative systems in Example 2, all the consumers' requests can be satisfied, so we have the following conclusion.

Proposition 2 Given a systemM and a normative systemN 1 M or N 2 M , we have that K(N h M ) |= φ1 ^ φ2 for h 2 {1, 2}.

The above example suggests that, to achieve some objectives, we need dynamic normative systems to represent the changes of social norms under di↵erent circumstances. Then, another question may follow about the maximum number of normative states. The dynamic system could be uninteresting if the number of states can be infinite. Fortunately, in the next section, we show with the complexity result that, for objectives expressed with CTL formulas, in the worst case, an exponential number of normative states are needed.

5 The Complexity of Norm Synthesis

We have the following result for norm synthesis.

Theorem 1 The norm synthesis problem is EXPTIMEcomplete, with respect to the sizes of the system and the objective formula. 4

Proof idea for the upper bound: EXPTIMEMembership

We use an automata-theoretic approach. Given a system M, we construct a B¨uchi tree automaton AM = (⌃, D, Q, δ, q0, Q), by a variant of the approach in [Kupferman and Vardi, 1996], such that Q = S ⇥ {>, `, ?} and δ : Q ⇥ ⌃ ⇥ D ! 2 Q ⇤ a transition function. Given a CTL formula φ and a set D ⇢ N with a maximal element k, there exists a B¨uchi tree automaton AD,¬φ that accepts exactly all the tree models of ¬φ with branching degrees in D. By [Vardi and Wolper, 1986], the size of AD,¬φ is O(2 k·|φ| ). Then we show that the norm synthesis problem is equivalent to an unsuccessful result from checking the emptiness of the product automaton AM ⇥ AD,¬φ. The checking of emptiness of B¨uchi tree automaton can be done in quadratic time, so the norm synthesis can be done in exponential time.

Proof idea for the lower bound: EXPTIME Hardness

We reduce from the problem of a linearly bounded alternating Turing machine (LBATM) accepting an empty input tape, which is known to be EXPTIME-complete [Chandra et al., 1980]. An alternating Turing machine AT is a tuple (Q, Γ, ⌧, q0, g) where Q is a finite set of states, Γ is a finite set of tape symbols including a blank symbol ?, ⌧ : Q ⇥ Γ ! P(Q ⇥ Γ ⇥ {-1, +1}) is a transition function, q0 2 Q is an initial state, g : Q ! {8, 9, accept, re ject} specifies the type of each state. An LBATM is an ATM which uses m tape cells for a Turing machine description of size m.

We construct a multiagent system M(AT) of a single agent 9, such that the state space S consists of three sets (Q ⇥ L), (Q ⇥ L ⇥ Γ), and (Q ⇥ L ⇥ L ⇥ Γ). Each transition (r, c, d) 2 ⌧(q, b) of AT is simulated by three consecutive transitions in M(AT), moving from states in one set to states in the next set. The basic idea of the transition relation T is to use agent 9 to move on 9 states and treat movements on 8 states as nondeterminism. Then the function δn of normative systems can be imposed to restrict the behaviour of the agent 9.

For the objectives, we use formula φ ^ AFacc, where φ is a CTL formula expressing the correct behaviour of the transition relation T with respect to ⌧, and AFacc expresses that all paths are accepting. Then the norm synthesis problem on M(AT) can be shown to be equivalent to the acceptance of the automata AT. Therefore, it is EXPTIME hard.

6 Agent Recognition of Social Norms

For a multiagent system to be autonomous without human intervention, it is important that it can maintain its functionality when new agents join or old agents leave. For a new agent to join and function well, it is essential that it is capable of recognising the social norms that are currently active. As stated in the previous sections, the agent has only partial observation over the system state, and is not supposed to observe the social norms. On the other hand, it is also unrealistic to assume that the agent does not know anything about the social norms of the system it is about to join. Agent is designed to have a set of prescribed capabilities and is usually supposed to work within some specific scenarios. Therefore, the actual situation can be that, the agent knows in prior that there are a set of possible normative systems, one of which is currently applied on the multiagent system. We remark that, assuming a set of normative systems does not weaken the generality of the setting, because Theorem 1 implies that there are a finite number of possible normative systems (subject to a bisimulation relation between Kripke structures). This situation naturally leads to the following two new problems:

4 Refer to http://arxiv.org/abs/1604.05086 for full proofs.

• (NC1) to determine whether the agent can always recognise which normative system is currently applied; and
• (NC2) to determine whether the agent can find a way to recognise which normative system is currently applied.

The successful answer to the problem NC1 implies the successful answer to the problem NC2, but not vice versa. Intuitively, the successful answer of NC1 implies a high-level autonomy of the system that the new agent can be eventually incorporated into the system no matter how it behaves. We assume that once learned the social norms the new agent will behave accordingly. If such an autonomy of the system cannot be achieved, the successful answer of NC2 implies a high-level autonomy of the agent that, by moving in a smart way, it can eventually recognise the social norms.

We formalise the problems first. Let be a set of possible normative systems defined on a multiagent system, Path(K(N)) be the set of possible paths of the Kripke structure K(N) for N 2 . We assign every normative system in a distinct index, denoted as ind(N). This index is attached to every path ⇢ 2 Path(K(N)), and let ind(⇢) = ind(N).

Let the new agent be x such that x < Agt and its observation function be Ox. For any state (s, q) 2 S † , we define a projection function[ (s, q) = s. So b⇢ is the projection of a path ⇢ of a Kripke structure to the associated multiagent system. We extend Ox to the paths of Kripke structure K(N) as follows: Ox(⇢s † ) = Ox(⇢) ·Ox(b s † ) for ⇢ 2 Path(K(N)) and s † 2 S † . We have Ox(✏) = ✏, which means when a path is empty, the observation is also empty. We also define its inverse O -1 x which gives a sequence o of observations, returns a set of possible paths ⇢ on which agent x's observations are o, i.e.,

W.l.o.g., we assume that N0 2 is the active normative system. Let N be the set of natural numbers, we have

Definition 3 NC1 problem is the existence of a number k 2 N such that for all paths ⇢ 2 Path(K(N0)) such that |⇢| ≥ k, we have that ⇢ 0 2 O -1 x (Ox(⇢)) implies that ind(⇢ 0 ) = ind(⇢).

Intuitively, NC1 states that as long as the path is long enough, the new agent can eventually know that the active normative system is N0. That is, no matter how the new agent behaves, it can eventually recognise the current normative system. On the other hand, NC2 states that such a path exists (but not necessarily for all paths). That is, to recognise the normative system, the new agent needs to move smartly.

NC2 problem is the existence of a path ⇢ 2 Path(K(N0)) such that for all ⇢ 0 2 O -1 x (Ox(⇢)) we have ind(⇢ 0 ) = ind(⇢).

Example 5 For the system in Example 1, we assume a new consumer agent cv such that v = m + 1. Also, we define Ocv (s) = {ci | ci 2 C, ti(s) = tv(s) , ?} for all s 2 S . Intuitively, the agent cv keeps track of the set of agents that are currently having the same request. Unfortunately, we have

Proposition 3 There exists an instance of system M such that under the set = {N 1 M , N 2 M } of normative systems, both NC1 and NC2 are unsuccessful.

This can be seen from a simple case where there are a single producer p1 with b1 = 1 and a set of consumers C such that ri = {g1} for all ci 2 C. For the initial state, every consumer sends its request to p1, so {ci | ti = p1} = C. For any path ⇢1 of K(N 1 M ) and ⇢2 of K(N 2 M ), we have b ⇢1 = b ⇢2 = s0 s2 s 1 1 s2...s m 1 s2s v 1 s2 s 1 1 ... where s0 = (1, (;, ?, ?), ..., (;, ?, ?)), s2 = (2, ({g1}, g1, p1), ..., ({g1}, g1, p1)), and s i 1 is di↵erent with s2 in ci's local state, e.g., s 1 1 = (1, ({}, ?, ?), ..., ({g1}, g1, p1)). And therefore Ocv (⇢1) = Ocv (⇢2) = ;C(C \ {c1})C(C \ {c2})..., i.e., the agent cv's observations are always the same 5 . That is, the new agent cv finds that for ⇢1, the single path on K(N 1 M ), there are ⇢2 2 O -1 cv (Ocv (⇢1)) and ind(⇢1) , ind(⇢2). Therefore, neither NC1 nor NC2 can be successful in such a case.

The reasons for the above result may come from either the insufficient capabilities of the agent or the designing of normative systems. We explain this in the following example.

Example 6 First, consider that we increase the capabilities of the new agent by updating the rule R2b in Section 2.

R2b'. the newagent cv may cancel its current request by letting dv = tv = ?; all other consumer agents execute action a?; and let k = 1.

With this upgraded capabilities of the new agent, the NC2 can be successful. The intuition is that, by canceling and rerequesting for at least twice, the ordering of consumer agents whose requests are satisfied can be di↵erent in two normative systems: with N 2 M , there are other agents ci between cm and cv, but with N 1 M , their requests are always satisfied consecutively. Note that, by its new capabilities, cv can always choose a producer agent which have more than 2 existing and future requests (Assuming that n ⌧ m, which is usual for a business ecosystem).

Proposition 4 With the new rule R2b', the NC2 problem is successful on system M and the set = {N 1 M , N 2 M }.

However, the NC1 problem is still unsuccessful, because the agent cv may not move in such a smart way. For this, we replace N 1 M with N 6 M = (Q 1 , δ 1 n , δ 6 u , q 1 0 ) such that

• δ 6 u (q, s2) = q and δ 6 u ((y1, ..., yn), s1) = (y 0 1 , ..., y 0 n ), s.t. y 0 j = ((yj + 1) mod m) + 1 for j 2 {1, ..., n}. Intuitively, the normative state increments by 2 (modulo m).

Proposition 5 Both NC1 and NC2 problems are successful on system M and the set = {N 2 M , N 6 M }.

5 We reasonably assume that, for N 1 M , when a producer sees cv, it will adjust its range in normative states from {1, ..., m} to {1, ..., m, v}.

7 The Complexity of NormRecognition

The discussion in the last section clearly shows that, the two norm recognition problems are non-trivial. It is therefore useful to study if there exist efficient algorithms that can decide them automatically. In this section, we show a somewhat surprising result that the determination of NC1 problem can be done in PTIME, while it is PSPACE-complete for NC2 problem. Assume that the size of the set is measured over both the number of normative systems and the number of normative states. We have the following conclusions.

Theorem 2 The NC1 problem can be decided in PTIME, with respect to the sizes of the system and the set .

The proof idea is as follows. The unsuccessful answer to the NC1 problem can be obtained by the existence of two infinite paths ⇢ 2 Path(K(N0)) and ⇢ 0 2 O -1 x (Ox(⇢)) such that ind(⇢ 0 ) , ind(⇢). To check this, we construct a product system K(N0) ⇥ K(N1) for N1 2 \ {N0}. The product system synchronises the behaviour of the two Kripke structures K(N0) and K(N1) such that the observations are always the same. Then the existence of an infinite path in the product system is equivalent to the existence of ⇢ and ⇢ 0 . Further, the existence of an infinite path is equivalent to the existence of reachable strongly connected components. The latter can be decided in PTIME by the Tarjan's algorithm [Tarjan, 1972].

Theorem 3 The NC2 problem is PSPACE-complete, with respect to the sizes of the system and the set .

Proof idea for the upper bound: PSPACEMembership

The upper bound is obtained by having a nondeterministic algorithm which takes a polynomial size of space, i.e., it is in NPSPACE=PSPACE. The algorithm starts by guessing a set of initial states of the structures {K(N) | N 2 } on which agent x has the same observation. It then continuously guesses the next set of states such that they are reachable in one step from some state in the current set and on which agent x has the same observation. If this guess can be done infinitely then the NC2 problem is successful. This infinite number of guesses can be achieved with a finite number of guesses, by adapting the approach of LTL model checking.

Proof idea for the lower bound: PSPACE Hardness

It is obtained by a reduction from the problem of deciding if, for a given nondeterministic finite state automaton A over an alphabet ⌃, the language L(A) is equivalent to the universal language ⌃ ⇤ . Let A = (Q, q0, δ, F) be an NFA such that Q is a set of states, q0 2 Q is an initial state, δ : Q ⇥ ⌃ ! P(Q) is a transition function, and F ✓ Q is a set of final states. We construct a system M(A) which consists of two subsystems, one of them simulates the behaviour of A and the other simulates the behaviour of the language ⌃ ⇤ . The subsystems are reachable from an initial state s0 by two actions a1 and a2 respectively. On the system M(A), we have two normative systems whose only di↵erence is on the state s0: N0 disallows action a1 and N1 disallows action a2. Therefore, the universality of the NFA A is equivalent to the unsuccessful answer to the NC2 problem on M(A) and = {N0, N1}.

8 RelatedWork

Normative multiagent systems have attracted many research interests in recent years, see e.g., [Boella et al., 2006; Criado et al., 2011] for comprehensive reviews of the area. Here we can only review some closely related work.

Norm synthesis for static normative systems. As stated, most current formalisms of normative systems are static. [Shoham and Tennenholtz, 1995] shows that this norm synthesis problem is NP-complete. [Christelis and Rovatsos, 2009] proposes a norm synthesis algorithm in declarative planning domains for reachability objectives, and [Morales et al., 2013] considers the on-line synthesis of norms. [Bulling and Dastani, 2011] considers the norm synthesis problem by conditioning over agents' preferences, expresses as pairs of LTL formula and utility, and a normative behaviour function. Changes of normative system. [Knobbout et al., 2014] represents the norms as a set of atomic propositions and then employs a language to specify the update of norms. Although the updates are parameterised over actions, no considerations are taken to investigate, by either verification or norm synthesis, whether the normative system can be imposed to coordinate agents' behaviour to secure the objectives of the system.

Norm recognition. Norm recognition can be related to the norm learning problem, which employs various approaches, such as data mining [Savarimuthu et al., 2013] and sampling and parsing [Oren and Meneguzzi, 2013; Cranefield et al., 2015], for the agent to learn social norms by observing other agents' behaviour. On the other hand, our norm recognition problems are based on formal verification, aiming to decide whether the agents are designed well so that they can recognise the current normative system from a set of possible ones. We also study the complexity of them.

Application of social norms Social norms are to regulate the behaviour of the stakeholders in a system, including sociotechnical system [Chopra and Singh, 2016] which has both humans and computers. They are used to represent the commitments (by e.g., business contracts, etc) between humans and organisations. The dynamic norms of this paper can be useful to model more realistic scenarios in which commitments may be changed with the environmental changes.

9 Conclusions

In the paper, we first present a novel definition of normative systems, by arguing with an example that it can be a necessity to have multiple normative states. We study the complexity of two autonomy issues related to normative systems. The decidability (precisely, EXPTIME-complete) of norm synthesis is an encouraging result, suggesting that the maximum number of normative states is bounded for CTL objectives. For the two norm recognition subproblems, one of them is, surprisingly, in PTIME and the other is PSPACE-complete. Because the first one suggests a better level of autonomy, to see if an agent can recognise the social norms, we can deploy a PTIME algorithm first. If it fails, we may apply a PSPACE algorithm to check the weaker autonomy.

Acknowledgement The authors would like to thank the reviewers for their constructive comments which are helpful in improving the paper. The authors are supported by ERC Advanced Grant VERIWARE, EPSRC Mobile Autonomy Programme Grant EP/M019918/1, National Natural Science Foundation of China Grant 61572234 and 61472369, Fundamental Research Funds for the Central Universities of China Grant 21615441, and ARC Grant DP150101618.