Keywords

1 Introduction

The focus of this paper is on the task coordination (TC) problem in Multiagent Systems (MAS). Given a state of affairs (exogenously imposed to, and to be fulfilled by, a MAS) it is crucial to have a systematic method for allocating tasks to involved agents (prospectively) and ascribing responsibilities to agents based on what they were tasked to do and what they actually did (in retrospection). This way, TC consists of two stages: Task Allocation (TA) and Task Responsibility (TR) [36]. Given a collective state of affairs (to be fulfilled by the MAS) TA is concerned with how the state of affairs should be distributed among agent groups in terms of tasks. Then TR is about evaluating the behavior of the MAS in fulfilling the tasks and ascribing (a degree of) responsibility to agents for dismissing/fulfilling tasks. In other words, following the allocation of a task to an agent or agent group, we see the group as being responsible for fulfilling the allocated task. In a MAS, there might be tasks for which no single agent has the required capabilities. Our work allows such tasks to be allocated to capable agent groups (instead of dismissing the task).

We believe that ascribing responsibility to agents is justified only if the task allocation process takes into account the strategic abilities of the agents and their epistemic limitations. In brief, strategic abilities of agents or agent groups determine what they can do in the MAS (e.g., in terms of properties that they can ensure or preclude), while epistemic limitations are about their potential (lack of) knowledge about the MAS. Capturing these two aspects for allocating tasks and ascribing responsibilities in MAS are focal points of this work.

In general, the TC problem relates to studies on Multiagent Organizational (MAO) frameworks, task allocation methods in MAS, and responsibility reasoning concepts in multiagent settings. Reviewing MAO frameworks in [13, 21, 24, 32], their focus is on how the MAO is organized in terms of its organizational structure and high level constructs to enable role/task allocation. They abstract from the exact procedure of task allocation and in some cases assume the availability of agents that are capable of fulfilling any assigned task. In MAO—as a whole or within any of its organizational units—task allocation techniques are often employed as a module to determine who should do what task(s) to ensure the organizational goals (as a collectively defined state of affairs). For instance, given the goal to have a picnic in the countryside for a two-member organization, one agent can be responsible for driving while the other one is responsible for food (i.e., allocating the task to drive to one agent and to prepare the food to the other one). Then some relevant questions are: “which one is able to drive (strategic ability)?”; “who knows about potential food allergies (epistemic limitations in imperfect information settingsFootnote 1)?”; “who is able to cook/drive at what time, as the journey/picnic evolves (temporal dynamics)?”. In most real-world environments, the task allocation procedure should capture all three aspects, i.e., addressing strategic, epistemic, and temporal aspects. However, no such method currently exists [3, 9, 11, 16, 26, 29]. In [16], authors capture strategic abilities but under a perfect information assumption. The presented approach in [29] relaxes this assumption for team formation—as a related problem to TC—but has less temporal expressivity than [16].

Recall that in the picnic example, we said that an agent is responsible for food or for driving. That is, when we arrive at the picnic spot with no food, we can justifiably see the agent (to whom we allocated the task of providing food) as being responsible for the (undesirable) outcome. We argue that dealing with autonomous agents, allocating tasks (prospectively) needs to be complemented by a (retrospective) phase of responsibility allocation. In , the TR component answers this question by ascribing a degree of responsibility to each agent, for an outcome \(\varphi \). This means seeing an agent as being responsible (for \(\varphi \)) to a degree proportional to its contribution to the occurrence of \(\varphi \). To model task responsibility, we apply multiagent responsibility reasoning methods [2, 35], in particular the notion of strategic responsibility [37], for ascription of responsibility in such imperfect information settings.

To overcome these shortcomings, we develop : a dynamic task coordination method based on formal methods for multiagent strategic reasoning. is a two-part method: its prospective part is focused on task allocation, while the retrospective part is focused on task responsibility. For task allocation, we allocate a task to an agent or agent group that is capable of handling it. One aspect that we see as being crucial to capture is the fact that the agents’ ability is limited to their knowledge about the environment. It is therefore necessary to capture strategic abilities in imperfect information settings and to avoid assuming perfect information for all agents. In imperfect information settings, agent A may be able to guarantee the fulfillment of a task \(\tau \) today, but not necessarily tomorrow—due to the information and strategies that it possesses today and may miss tomorrowFootnote 2. This is a missing aspect in most task allocation methods for MAS. It also motivates our approach to use the semantic machinery of multiagent logics that are expressive for modeling temporal and strategic properties in imperfect information settings. The retrospective part of is focused on the history and is about ascribing responsibility to agents—considering what they did and what they had to do. As we allocate tasks by taking into account agents’ abilities, the fulfillment of an allocated task is a justified expectation, hence agents that violate this expectation are justifiably responsible for it. Against this background, for the first time, this paper captures strategic abilities under imperfect information for task allocation in multiagent settings and applies responsibility reasoning for task coordination in organizational settings.

We present a conceptual analysis on the TC problem and recall formal preliminaries in Sect. 2. Then, in Sect. 3, we specify and its components. In Sects. 4 and 5, we focus on the allocation of tasks and ascription of responsibilities, respectively. We formally verify properties of : on validity as well as stability of task allocations and fairness as well as non-monotonicity of task responsibilities. Finally, Sect. 6 discusses the relevance and implementability of and presents the concluding remarks.

2 Conceptual Analysis and Formal Preliminaries

In this section, we present the intuition behind our work, analyze conceptual aspects of TC, and recall key formal notions that form the basis of the framework.

2.1 Conceptual Analysis

Imagine a family picnic scenario in which parents allocate different picnic-related tasks to their children Alex, Bob, Cathy, and see them responsible for organizing a picnic that satisfies some expectations. They expect the picnic to be organized in a clean picnic spot in the country side and to have home-made food for the day. In this case, having a desirable picnic is a collective state of affairs. Then the first bit of the task coordination problem is to see “who is able to do what” in a temporal, strategic, and imperfect information setting. The second bit is about “seeing who did what” and ascribing responsibility to agents for the outcome. We deem that the second phase (task responsibility) is justified only if in the first phase (task allocation), the strategic, temporal, and epistemic aspects of the setting are captured. For instance, if we give the task of driving to the spot to Cathy while she has no driving licence, it is not reasonable to blame her for dismissing the allocated task. The analogous case is valid for giving the task of cleaning to Bob, if he cannot distinguish clean from unclean (e.g., due to a visual impairment). We later show how these aspects can be modeled and verified using the semantic machinery of logics for multiagent strategic reasoning. In addition to these aspects, there are a number of high-level principles that are essential to effective task coordination:

Suitability of the collective state of affairs: given the set of agents and their available actions, fulfilling some states of affairs are impossible in principle, regardless of how we allocate tasks among the agents. For instance, in our picnic scenario, a modest picnic is reasonable to expect but seeing the small group organize a festival might not be a suitable (collective) state of affairs.

Validity of task allocation: given a suitable state of affairs, the process of task allocation ought to be such that all that should be done is allocated, neither more nor less (i.e., if all agents fulfill their tasks, the collective state of affairs will be fulfilled). For instance, if we tell Alex to take care of driving and give the task of cleaning the place to Bob and Cathy, the allocation is not valid as preparing food is dismissed. Basically, we see an allocation of tasks as valid if by assuming that all agents fulfill their allocated task, we can see the collective state of affairs will ensure.

Justifiability of task responsibility: task responsibility should be consistent with task allocation. In other words, seeing a group as being responsible is not independent of what tasks they were given in an earlier stage. For instance, if we give the task of preparing food to Alex, then it is not justifiable to see Bob responsible for the food quality even if he is able to cook. This shows that verifying task responsibility is not merely based on agents’ ability but builds upon the implemented task allocation and the history of realized actions (i.e., the evolution of the multiagent system).

In subsequent sections, we provide a formal account of these principles and then fulfill them using . To specify the multiagent setting, we use Concurrent Epistemic Game Structures (CEGS) [1] as it allows: modeling the behavior of a MAS, specifying strategic abilities of agents, and representing agents’ knowledge. Then we focus on task and responsibility allocation in .

2.2 Concurrent Epistemic Game Structures

To model multiagent systems and analyze their strategic behavior under imperfect information, we use Concurrent Epistemic Game Structures (CEGS) [1] as an epistemic extension of Concurrent Game Structures [4]. In addition to being expressive for specifying temporal, strategic, and epistemic aspects of MAS, models that use CEGS can benefit from standard model checking platforms (e.g., ATL-based model-checking tools in [23, 25]) to verify properties of the modeled MAS.

Concurrent Epistemic Game Structures: Formally, a concurrent epistemic game structure is a tuple \(\mathcal {M}=\langle \varSigma ,Q,Act,\varPi ,\pi ,\sim _1,\dots ,\sim _n,d,o \rangle \) where: \(\varSigma =\{a_1,\dots ,a_n\}\) is a finite non-empty set of agents; Q is a finite non-empty set of states; Act is a finite set of atomic actions; \(\varPi \) a set of atomic propositions; \(\pi : \varPi \mapsto 2^Q\) is a propositional evaluation function; \(\sim _a \subseteq Q \times Q\) is an epistemic indistinguishability relation for each agent \(a \in \varSigma \) (we assume that \(\sim _a\) is an equivalence relation, where \(q\sim _a q'\) indicates that states q and \(q'\) are indistinguishable to a); function \(d: \varSigma \times Q \mapsto \mathcal {P}(Act)\) specifies the sets of actions available to agents at each state (we require that the same actions be available to an agent in indistinguishable states, i.e., \(d(a,q)=d(a,q')\) whenever \(q \sim _a q'\)); and o is a deterministic transition function that assigns the outcome state \(q'=o(q,\alpha _1,\dots , \alpha _n)\) to state q and a tuple of actions \(\alpha _i \in d(i,q)\) that can be executed by \(\varSigma \) in q.

To enable the specification of a collective state of affairs, we adopt the standard language of LTL (Linear Temporal Logic [30]). Formulas of the language \(\mathcal {L}_{LTL}\) are defined by the following syntax, where \(p \in \varPi \) is a proposition, \(\lnot \) and \(\wedge \) are standard logical operators, means that \(\varphi \) is true in the next state of \(\mathcal {M}\), \(\psi \mathcal {U} \varphi \) means that \(\psi \) has to hold at least until \(\varphi \) becomes true; and \(\square \varphi \) means that \(\varphi \) is always true. For convenience, \(\diamond \varphi \) is defined as an equivalent to \(\lnot \square \,\lnot \,\varphi \) meaning that \(\varphi \) is eventually true. To represent and reason about strategies and outcomes in agent systems with imperfect information, we make use of the following auxiliary notions. (References to elements of \(\mathcal {M}\) are to elements of a CEGS \(\mathcal {M}\) modeling a given multiagent system, e.g., we write Q instead of Q in \(\mathcal {M}\).)

Successors and Computations: For two states q and \(q'\), we say \(q'\) is a successor of q if there exist actions \(\alpha _i\in d(i,q)\) for \(i \in \{1,\ldots ,n\}\) in q such that \(q'=o(q,\alpha _1,\dots , \alpha _n)\), i.e., agents in \(\varSigma \) can collectively guarantee in q that \(q'\) will be the next system state. A computation of a CEGS \(\mathcal {M}\) is an infinite sequence of states \(\lambda =q_0,q_1,\dots \) such that, for all \(k > 0\), we have that \(q_k\) is a successor of \(q_{k-1}\). We refer to a computation that starts in q as a q-computation. For \(k \in \{0,1,\dots \}\), we denote the k’th state in \(\lambda \) by \(\lambda [k]\), and \(\lambda [0,k]\) and \(\lambda [k,\infty ]\) respectively denote the finite prefix \(q_0,\dots ,q_k\) and infinite suffix \(q_k,q_{k+1},\dots \) of \(\lambda \). We refer to any two arbitrary states \(q_k\) and \(q_{k+1}\) as two consecutive states in \(\lambda [k,\infty ]\). Finally, we say a finite sequence of states \(q_0,\dots ,q_n\) is a q-history if \(q_n=q\), \(n \ge 1\), and for all \(0 \le k <n\) we have that \(q_{k+1}\) is a successor of \(q_k\). We denote a q-history that starts in \(q_k\) and has n steps with \(\lambda [q_k,n]\). The set of q-histories for all \(q \in Q\) is denoted by \(\mathcal {H}\).

Strategies and Outcomes: A memoryless imperfect information strategyFootnote 3 for an agent \(a \in \varSigma \) is a function \(\zeta _a: Q \mapsto Act\) such that, for all \(q \in Q\): (1) \(\zeta _a(q) \in d(q,a)\), and (2) \(q \sim _a q'\) implies \(\zeta _a(q)=\zeta _a(q')\). For a group of agents \(\varGamma \subseteq \varSigma \), a collective strategy \(Z_\varGamma =\{\zeta _a \mid a \in \varGamma \}\) is an indexed set of strategies, one for every \(a \in \varGamma \). Then, \(out(q,Z_\varGamma )\) is defined as the set of potential q-computations that agents in \(\varGamma \) can enforce by following their corresponding strategies in \(Z_\varGamma \). We extend the notion to sets of states \(\chi \subseteq Q\) in the straightforward way: \(out(\chi ,Z_\varGamma ) = \bigcup _{q'\in \chi }out(q',Z_\varGamma )\).

Uniform Strategies: A uniform strategy is one in which agents select the same actions in all states where they have the same information available to them. In particular, if agent \(a \in \varSigma \) is uncertain whether the current state is q or \(q'\), then a should select the same action in q and in \(q'\). Formally, a strategy \(\zeta _a\) for agent \(a \in \varSigma \) is called uniform if for any pair of states q, \(q'\) such that \(q \sim _a q'\), \(\zeta _a(q) = \zeta _a(q')\). A strategy \(Z_\varGamma \) is uniform if it is uniform for every \(a \in \varGamma \subseteq \varSigma \). Realistic modeling of strategic ability under imperfect information requires restricting attention to uniform strategies only.

3 Specification

To specify , four components are required: a behavior modeling machinery, a collective state of affairs (given to the MAS), the task allocating component, and the task responsibility component.

Given a CEGS \(\mathcal {M}=\langle \varSigma ,Q,Act,\varPi ,\pi ,\sim _1,\dots ,\sim _n,d,o \rangle \) that models the behavior of the multiagent system, a collective state of affairs \(G_q\) (given to MAS in state q) is a set of formulae from \(\mathcal {L}_{LTL}\).Footnote 4 Then the aim of the task allocation process is to ensure that all \(\varphi \in G_q\) hold. Finally, the task responsibility process ascribes a (backward-looking) degree of responsibility to agents given a history \(h \in \mathcal {H}\).

In this approach, \(\mathcal {M}\) is a standard component (adapted from [1]) for modeling the behavior of a MAS in imperfect information settings. Then \(G_q\) specifies the set of properties that are expected to be satisfied by the agents collectively (we call it the collective state of affairs). Then what each subgroup ought to do is determined by task allocation and who is responsible to what extent by task responsibility. We present the exact specification of both in upcoming sections. This means is built on a behavior-modeling CEGS, a local state of affairs, and allocates (forward-looking) tasks as well as (backward-looking) responsibilities to agent groups. Note that all the elements of are defined independently of any desirable properties. So, how an element should be specified such that desirable properties emerge is not intrinsic to the model but will be discussed in the following sections. This is to allow a level of flexibility and to enable capturing context-dependent concerns. supports task coordination using two forms of prospective and retrospective organizational reasoning. The former is about allocating tasks to agents (Sect. 4) while the latter is about verifying what went wrong/right and who is responsible to what extent (Sect. 5).

4 Allocating Tasks in

Following the specification of components, and given a local state of affairs \(G_q\) (to be fulfilled collectively by agents in the MAS), “who should do what, and why?” is the main question that we aim to answer in this sectionFootnote 5. We deem that the ascription of tasks to agents or agent groups (with the aim to fulfill a collective state of affairs) should take into account the temporal, strategic, and epistemic aspects of multiagent systems. Temporality is both about the specification of tasks (e.g., whether some property should be maintained or only achieved once) and also about the state of the environment (e.g., whether a task can be allocated at a current state \(q_1\) (today) or at potential states that follow \(q_1\) (tomorrow)). Then it is reasonable to allocate a task to who—either a single agent or a group of agents—is capable of fulfilling it. While some consider this as strategic ability, we emphasize the importance of knowledge in “being capable of doing something”. Basically, as highlighted by [1], the strategic ability of an agent group is limited to their knowledge of the system and its dynamics (e.g., in a physical confrontation, even if agent \(a_i\) is strong enough to capture an adversary agent \(a_j\), not knowing that \(a_j\) is located in front of \(a_i\), avoids it exercising its potential). This is why we focus on uniform strategies (see Sect. 2.2).

Prior to allocating tasks and building on the notion of a uniform strategy, we say a local state of affairs \(G_q\) is suitable for a multiagent system (the suitability principle) only if the grand coalition \(\varSigma \) has a uniform strategy in state q to ensure it (note that we are referring to components of a particular CEGS \(\mathcal {M}\) that models a given MAS). Then given a suitable \(G_q\), a task allocation is valid (the validity principle) only if we assume the compliance of agents with allocated tasks entail that \(G_q\).

In the following, we specify the task allocation component of and show its desirable properties.

Definition 1

Given a multiagent system \(\mathcal {M}\), a local state of affairs \(G_q= \varphi _1 \wedge \dots \wedge \varphi _m\), and the assignment of \(\varphi _i (1\,\le \, i \,\le \, m)\) to agent group \(\varGamma _i \,\subseteq \, \varSigma \), the assignment set \(\{\langle {\varphi _1, \varGamma _1}\rangle ,\dots ,\langle {\varphi _m, \varGamma _m}\rangle \}\) is a task allocation iff (1) \(\varGamma _i\) is a minimal group with a uniform strategy in q to ensure \(\varphi _i\) and (2) for any two intersecting groups \(\varGamma _i\) and \(\varGamma _j (1\le j \le m)\), \(\varGamma _i \cup \varGamma _j\) is a minimal group with a uniform strategy in q to ensure \(\varphi _i \wedge \varphi _j\).

As discussed earlier, this approach for allocating tasks captures the strategic abilities of agents and their epistemic limitations for allocating tasks. (We highlight that the allocation process is based on perfect information about agents, their abilities, and knowledge. Our reference to imperfect information is to the information that is available to involved agents in the MAS.) The following theorem shows that for a suitable state of affairs, there exists a task allocation that satisfies the two conditions in Definition 1. In q, we modelcheck to find minimal agent groups capable of ensuring propositional components of \(G_q\) and generate a task allocation that gives the task of ensuring each component \(\varphi _i\) (the ith components of \(G_q\)) to an agent group \(\varGamma _i\) which has a uniform strategy to ensure \(\varphi _i\). This procedure generates a valid allocation if \(G_q\) is a suitable state of affairs.

Theorem 1

Given a suitable \(G_q\), there exists a valid task allocation in q.

Proof

We provide a constructive proof by presenting a task allocation procedure based on \(ATL_{ir}\) model checking. First, for all \(\varphi _i \in G_q=\{\varphi _1 \wedge \dots \wedge \varphi _m\}\), we use standard \(ATL_{ir}\) model checking [23] and apply a minimality-checking loop to generate the set, denoted by \(\varPhi _i\), of minimal agent groups \(\varGamma \subseteq \varSigma \) with the ability to ensure \(\varphi _i\) from q. Given all \(\varPhi _i\), the set of allocation tuples \(\{\langle {\varphi _1, \varGamma _1}\rangle ,\dots ,\langle {\varphi _m, \varGamma _m}\rangle \}\) in which the two conditions of Definition 1 are satisfied is non-empty thanks to the suitability of \(G_q\).   \(\blacksquare \)

Note that we take the collective state of affairs and allocate each component to capable groups—with a uniform strategy to fulfill it. Recalling the notion of uniform strategy (in Sect. 2.1), given that the group has a collective strategy, each agent has an individual strategy that contributes to the fulfillment of the task. This way of allocating tasks to group, leaves it to the group to decide what ultimate individual action (in each state) individuals should take to see to it that the task is fulfilled. This is to see agents in an organizational setting as autonomous entities to whom we do not tell what exact action to take. We see each agent as a group member able to collaborate to execute a strategy, based on a repository of actions, such that the task that is allocated to the group is fulfilled. We later show how we can (retrospectively) ascribe a degree of responsibility to each individual based on what they did (outcome of collective actions) and what they had to do (allocated tasks).Footnote 6

As discussed, the notion of the collective state of affairs \(G_q\) is a local notion to specify what properties are valuable in an organizational setting. Hence they ought to be satisfied by agents in \(\varSigma \) collectively. \(G_q\) says what is expected to be satisfied being in state q assuming that it contains expectations that were given previously and are not yet satisfied but valuable. In other words, agents are not required to keep a repository of tasks. This enables the expression of real-life situations where dynamic task allocation is desirable (i.e., it allows changing the state of affairs as the system evolves, hence gives the ability to give a different task to a group). Our approach to consider a local state of affairs gives a form of deterministic Markov property [27] to task allocation in . In other words, local suitability can be extended and if satisfied globally (in all states) guarantees the existence of a valid task allocation in all states of MAS.

Proposition 1

If \(G_q\) is suitable for all states \(q \in Q\), the procedure presented in (the proof of) Theorem 1 generates a valid task allocation in all states regardless of the evolution of the system, represented by a materialized q-history \(h \in \mathcal {H}\).

Proof

Note that \(G_q\) is a local notion (on state q) and that its suitability is independent of any q-history h. Then to prove, we need to show that having a \(G_q\), suitable in all \(q \in Q\), there exists a valid task allocation in each q. This is given by Theorem 1.   \(\blacksquare \)

Under , agent groups to which we allocate a task may intersect. E.g., if we allocate \(\varphi _1\) to \(\varGamma _1\) and \(\varphi _2\) to \(\varGamma _2\), agents in \(\varGamma _1 \cap \varGamma _2\) ought to take a part in ensuring both \(\varphi _1\) and \(\varphi _2\). Then one may ask whether in such cases, agents in the intersection are supposed to choose between two alternatives and only satisfy one task while dismissing the other one. The following proposition shows that using the proposed procedure in Theorem 1, allocated tasks are not mutually exclusive.

Proposition 2

Given a suitable \(G_q\), there are no two exclusively satisfiable tasks allocated to a group.

Proof

Follows directly from the second condition (in Definition 1) that any generated allocation—by the procedure presented in Theorem 1—satisfies. Note that the concern is not only about mutual exclusivity in a logical sense, but in a strategic sense (i.e., that the available strategies for a group to fulfill two properties are coherent).   \(\blacksquare \)

In organizational settings, agents are assumed to be a part of a collaborative practice, hence ought to fulfill their set of allocated tasks. But a valid question is whether they have any rational reason to avoid fulfilling and deviate from their tasks. In other words, whether an allocation is stable (in game-theoretic terminology). The following theorem shows that a task allocation is stable as no group has a rational incentive for deviation.

Theorem 2

Given a suitable collective state of affairs \(G_q\), a task allocation under the procedure presented in Theorem 1 is stable in the sense that no agent group has a rational incentive to deviate from its allocated task(s).

Proof

Building on Proposition 2, for any allocated task to a group \(\varGamma \)—under the proposed procedure—any group \(\varGamma \) has a uniform strategy to fulfill the task. Hence, no group in \(\varSigma \) has a rational incentive to deviate from the allocation (i.e., to not fulfill the tasks). Note the assumption that agents are a member of the organization, hence prefer to deliver their tasks if they are able to do so.   \(\blacksquare \)

Note that we are focused on the availability of a “task-fulfilling” strategy to agent groups—assuming that allocated tasks ought to be fulfilled if such a strategy exists—and abstract from agents’ preferences.

Example 1

In our example (see Fig. 1), there are various ways (with different levels of control) which the parents can use to express their expectation. One way would be to have which is an explicit form with temporal limitations. Another more-relaxed form is . For both forms the first element can be allocated as a task to \(\{A,B\}\), the second one to \(\{C\}\), and the last one to \(\{A,C\}\). Note that for a strategy to be uniform for a group, it should be accessible to them from all the indistinguishable states. In this case: \(\{A,B\}\) has a strategy to ensure from both \(q_0\) and \(q_1\); \(\{C\}\) can ensure s either eventually (\(\diamond s\)) or in the state after the next (); and \(\{A,B\}\) can ensure tidiness.

Fig. 1.
figure 1

Set of agents \(\varSigma =\{A,B,C\}\) (Alex, Bob, Cathy), set of actions \(Act=\{ck,dr,cl,id\}\) (cooking, driving, cleaning, idle, and for any \(act \in Act\), \(\overline{act}\) denotes any action in \(Act \setminus \{act\}\)), and set of propositions \(\varPi =\{f,s,t\}\) (ready food, being at spot, tidiness). For any unmentioned action profile \(\alpha \) and arbitrary \(q \in Q\), we have that \(o(q,\alpha )=q\) (i.e., we avoided an \(\alpha \) self-loop on every node). To model epistemic limitations, we assume that cooking (act ck) is only possible at home while cleaning (act cl) is only possible at the picnic spot. To model epistemic limitations, some states are indistinguishable for some agents represented by dashed lines labeled with the agent(s) who can not distinguish the states that the dashed line connects.

Full size image

5 Ascribing Responsibility in

Assuming that the allocation of tasks to agents definitely results in the fulfillment of tasks—and in turn brings about the collective state of affairs—is unreasonable in real-life environments. This is because autonomous agents are not artifacts but entities that may opt to exercise their autonomy and do otherwise. In organizational settings, such undesirable behavior is possible. But in addition—and based on the assumption that agents are a member of the organization, hence expected to deliver their allocated tasks—we can ascribe a degree of responsibility to agents. In particular, to those who contributed to a collective state of affairs being unfulfilled. This form of reasoning is known in the literature on responsibility as backward-looking responsibility [31, 37]. Basically, the reasoner observes the materialized history of events/actions (that lead to a given outcome situation S) and with the knowledge about agents’ available actions, ascribes responsibility to agents who contributed to the occurrence of S or to those who could avoid \(\lnot S\) but apparently did not exercise their avoidance potential. The former causality-oriented approach is known as causal responsibility [12] based on the potential to bring about, while the latter is known as strategic responsibility [37] based on the potential to avoid. One may refer to this backward-looking form of responsibility reasoning as evaluating the blameworthiness if S is known to be a normatively undesirable state of affairs.

In our picnic scenario, imagine that the whole group arrives at the picnic spot with no food (states \(q_2\) or \(q_3\) in Fig. 1). Who is responsible for such an undesirable outcome? Which agent(s) or agent group(s) can be blamed? And to what extent? One can look at the history of events (i.e., who did what at any state in the chain of states that ends in the current state), check the list of allocated tasks in those states, and justifiably blame a group of agents that ought to deliver the task of preparing food. This procedure is in particular a justifiable one in imperfect information settings if the agents’ strategic ability and their epistemic limitations were taken into account in the preceding task allocation procedure.

To ascribe responsibility to agents, we adopt the approach described in [37]. The responsibility reasoning notion of [37] is in-line with our approach in as we both focus on imperfect information settings. Following this, we see a group \(\varGamma \) as being responsible for an outcome \(\varphi \) in state q given a history h if \(\varphi \) holds in q while ensuring \(\lnot \varphi \) was among the allocated tasks to \(\varGamma \) in a state (other than q) in h. Formally:

Definition 2

Given a multiagent system \(\mathcal {M}\), task allocation, and the materialized q-history h, an agent group \(\varGamma \) is q-responsible for \(\varphi \) iff (1) \(\varphi \) does not hold in state q and (2) \(\varphi \) is among the allocated tasks to \(\varGamma \) in a state \(q' \in h\) for \(q \ne q'\).

In this view, a group that is tasked to ensure \(\varphi \) is responsible for it until \(\varphi \) becomes true. Note that being responsible for \(\varphi \) does not imply any negative connotation here. (That is why we avoid using the negatively-loaded term “blameworthy” here.) This is crucial to note because a group might have the plan to bring about \(\varphi \) in a next state or maybe they are assigned a new task in the dynamic setting of . Moreover, note that a \(\varphi \) being unfulfilled in q directly implies that any state of affairs that contains \(\varphi \) is not satisfied. For instance, in our picnic scenario, having no food in \(q_2\) implies that the collective state of affairs “well-organized picnic” \(G_{q_0}=\{f,s,t\}\) that was given to the multiagent system in \(q_0\) is unsatisfied in \(q_2\). This notion of responsibility can be seen as a measure of the collective state of affairs satisfaction in organizational settings. If ensuring \(G_q\) is given to a MAS, a state in which no group is responsible for any \(\varphi \in G_q\) is a state where \(G_q\) is fulfilled completely.

Proposition 3

Given a suitable state of affairs \(G_q\), the task allocation, and the materialized history \(h= q, \dots ,q'\), we have that \(G_q\) is satisfied in \(q'\) if no agent group \(\varGamma \) is \(q'\)-responsible for any \(\varphi \in G_q\).

Proof

Having no group \(\varGamma \) being \(q'\)-responsible for any \(\varphi \in G_q\) implies that for all \(\varphi \), either of the two conditions in Definition 2 does not hold in \(q'\). As task allocation is applied, the second condition holds for all \(\varphi \). Thus the first condition does not hold for all \(\varphi \), i.e., that all the elements of \(G_q\) are satisfied in \(q'\).   \(\blacksquare \)

Theorem 3

Given a suitable \(G_q\), there exists a nonempty set of states \(S \subseteq Q\) such that for all \(q' \in S\), no group \(\varGamma \) is responsible for any arbitrary \(\varphi \in G_q\) based on history \(q, \dots ,q'\).

Proof

In q, such a set in which \(\mathop {\bigwedge }\limits _{\varphi \in G_q} \varphi \) holds is foreseeable as, for ensuring a suitable \(G_q\), a uniform strategy is available to \(\varSigma \).   \(\blacksquare \)

As we discussed, responsibility ascription is to agent groups. Then a problem that we face in multiagent systems—known as the responsibility gap problem—concerns situations where a group of agents is responsible for an outcome but the share of each individual agent is not clear [28]. In principle, the question is about the extent of responsibility of each agent for an unfulfilled task. This is a translation from group responsibility to individual responsibility. We highlighted that as we are dealing with tasks in , responsibility sharing techniques for MAS (e.g., [12, 37]) are not directly applicable. In , an agent might be in two different groups with different tasks (coalitional dynamics) and moreover, may get involved in different tasks as the system evolves (temporal dynamics). Note that if agent group \(\varGamma \) with n members is found to be responsible for a given \(\varphi \), sharing the responsibility equally is not a reasonable approach as each individual possesses different levels of knowledge and ability, and hence had different levels of contribution to \(\varphi \). A standard approach is to consider fairness propertiesFootnote 7:

Theorem 4

Given a suitable collective state of affairs \(G_q\), task allocation, and \(q'-\)history \(h\,=\,q, \dots ,q'\), the degree of \(q'-\)responsibility of agent \(a \,\in \, \varSigma \) for \(\varphi \in G_q\), denoted by \(\mathfrak {R}(a,\varphi ,h)\), satisfies the fairness properties if \(\mathfrak {R}(a,\varphi ,h)\,=\,\varPhi (a,\rho )\) where \(\varPhi \) returns the Shapley value of agents in the cooperative game \(\langle {\,}\rangle {\varSigma ,\, \rho }\) in which \(\rho (\varGamma \,\subseteq \, \varSigma )\) is equal to 1 if \(\varGamma ' \,\subseteq \, \varGamma \) is \(q'-\)responsible for \(\varphi \) based on h and 0 otherwise.

Proof

The game is such that—using the Shapley value—each agent receives a degree of responsibility with respect to its contribution to responsible groups.

   \(\blacksquare \)

Thanks to the properties of the Shapley value, this degree of responsibility is a fair way for bridging the responsibility gap and distributing the responsibility of each individual in . As a direct result we have:

Proposition 4

For a given \(\varphi \in G_q\) and history h, we have that \(\mathop {\sum }\limits _{a \in \varSigma } \mathfrak {R}(a,\varphi ,h) \in \{0,1\}\).

Proof

Having h, either q is a state in h or not. If not, then \(\varphi \) is not among the allocated tasks to any agent group in \(\varSigma \) hence the degree of responsibility for all agents \(a \in \varSigma \) is zero. The same holds if q is in h and \(\varphi \) holds in the last state of h. The only case in which some agent groups are responsible for \(\varphi \) based on h is when \(\varphi \) does not hold in the last state of h; and in this case, the summation is equal to one thanks to the efficiency property of the degree.   \(\blacksquare \)

Based on this result we have that in organizational settings, for any allocated but unfulfilled task, there exists a responsible group if the task manager follows . Note that as we are assuming suitability (for the collective state of affairs) and discussing the ascription of responsibility degrees in the context of task coordination, impossibilities for which no group is responsible are avoided automatically. The next property is about the evolution of the notion of task responsibility and the degree of responsibility though a given history.

Proposition 5

For a given \(\varphi \,\in \, G_q\) and history h, the notion of responsibility and its degree are non-monotonic through the temporal evolution of h: formally, (1) being \(q_i-\)responsible for \(\varphi \) (for a \(q_i \in h\)) does not imply being \(q_{i+1}-\)responsible for \(\varphi \). Moreover, (2) \(\mathfrak {R}(a,\varphi ,h'')\) (for \(h''=q,\dots ,q', \dots , q''\)) is not necessarily higher or lower than \(\mathfrak {R}(a,\varphi ,h')\) (for \(h'=q,\dots ,q'\) as a part the materialized history \(h''\)).

Proof

For part (1), we have that \(\varphi \) may hold in one state of the history but not in the next one. In the states where it holds, no group is responsible for it. For (2), we can rely on part (1) but also have that due to dynamism of , the task to satisfy \(\varphi \) can be given to new groups through h (e.g., to ensure a level of fault-tolerance). Therefore the number of responsible groups is not fixed temporally (through the history h).   \(\blacksquare \)

Note that is neither aware of nor requires agents’ preferences as it respects a separation of concerns in the process of responsibility ascription (i.e., it is not designed based on the knowledge about agents’ internal settings, hence is operational in multiagent organizational settings under imperfect information). Moreover, we assume that being involved in implies that the agent is expected to dedicate its resources (represented in terms of its available actions in each state) to the organization and is expected to fulfill its allocated tasks.

Example 2

Having the allocation of tasks according to Example 1 and the history \(q_0,q_2,q_3\), the collective state of affairs \(G_{q_0}\) is not yet fulfilled. Going back through the steps of history, the task of preparing food was allocated to \(\{A,B\}\) and they had a uniform strategy to avoid it remaining unfulfilled. They each have the degree of responsibility of 1/2 due to their symmetric contribution.Footnote 8

6 Discussion and Concluding Remarks

We discuss the relevance of task coordination under imperfect information, argue the implementability of by showing steps toward operationalization, and relate our contribution to past work.

Perfect vs. Imperfect Information Settings: Although assuming perfect information is realistic for closed environments (e.g., in production processes or data-base systems), in most real-life applications, an agent’s knowledge of the environment, hence of the consequences of its acts, is limited. In our model, we allow the representation of agents with imperfect information and consider uniform collective strategies to capture the epistemic aspect of the notion of strategic ability. This means we can both allocate tasks in imperfect information settings and ascribe responsibility in a justifiable manner. Note that is also operational in perfect information settings—simply by assuming an empty indistinguishability relation (in CEGS \(\mathcal {M}\)) for all the agents in \(\varSigma \). In this way, the presented complexity and experimental results in [16] for the perfect information scenarios can be applied to if one intends to deploy it in a perfect information task coordination case. In our running example, if agents had perfect information, we could dismiss indistinguishability relations (i.e., by deleting the dashed lines in Fig. 1). Then in the task allocation part of , agents may have more strategies available to ensure the components of a given state of affairs—as they are not epistemically limited. This in turn affects the responsibility ascription process.

Implementability: As we presented our task coordination concepts and tools using concurrent game structures, then the logical characterization of is standard. To that end, one can use the epistemic variant of ATL proposed in [22] that adds indistinguishably relations to explicitly specify the epistemic uncertainty of agents. This allows reasoning about the abilities and responsibilities of agent groups under imperfect information. Providing such a logical characterization of our notions also enables the systematic verification of the two parts of (for task and responsibility allocation). Building on this, one can use standard model-checking tools [25] to implement as an operational task coordination tool and in turn enable its application in real-life problems (e.g., in the context of business management or collaborative industrial systems).

Given a state of affairs to be ensured by the MAS, enables tasks to be allocated to agents or agent groups such that their fulfillment leads to the overarching state of affairs being ensured. For task allocation, is the first model that considers both the epistemic limitations and strategic abilities of agents. Moreover, we allow the allocation of tasks not only to individuals but also to agent groups. We argue that allocation is not enough if we deal with autonomous agents. Thus, following the task allocation, one can use to ascribe a degree of responsibility to agents with respect to a state of affairs. This work is the first to employ the notion of strategic responsibility for task coordination in MAS.

Our approach to allocate tasks to agents is complementary to (group) role assignment in robot systems and open societies [15, 17, 19, 38]. While they generally assume that roles are to be taken by agents, in we allocate tasks to agents based on their ability to ensure a task and accordingly see them as being responsible for the outcome. In this way can be used in combination with multiagent organizational frameworks such as \(\mathcal {M}oise\) [21] (more precisely, within each organizational unit and assuming the availability of knowledge about the unit to ).

In relation to the multiagent responsibility and accountability literature [5, 12, 35, 37], our work applies responsibility reasoning (in specific, the ATL-based notion of strategic responsibility) for task coordination. Based on ’s degree of responsibility, one can ascribe blameworthiness and sanctioning penalties to agent groups (e.g., to enforce a given norm in MAS). We also highlight a related but distinguishable approach to this problem that is based on the notion of causal responsibility in [2, 12, 18]. Basically, causal responsibility (as presented in [12]) ascribes a degree of responsibility to agents based on their potential to provide a situation while strategic responsibility (as presented in [37]) ascribes responsibility based on their ability to preclude. We see these two perspectives as complementarily applicable in different domains.

In , we dismissed incentivization. We see that an interesting extension is to consider rewarding agents per task fulfillment to provide strategy-proofness. Otherwise, an agent may strategically block its own strategies to avoid the allocation of a task. Rewarding can encourage agents to employ their most “effective” strategy, and by effectiveness we are referring to a strategy that enables them to fulfill as many tasks as possible. In principle, rewarding agents following the fulfillment of a task (and sanctioning otherwise) nudges the behavior of economically-motivated and rational agents towards the fulfillment of collective-level organizational goals. To address this, we aim to integrate norm-aware incentive engineering techniques [6, 7, 14] into and consider coalition forming aspects [10, 20]. In such a line, the degree of responsibility can be used as a basis to formulate normative notions of blame/praiseworthiness which in turn enables developing sanctioning/rewarding mechanisms. Moreover, in , we merely focused on physical actions of agents. Thus, another extension is to enrich the repository of actions by adding an explicit representation of communicative actions. Basically, through communicative actions, the agents’ epistemic level may change. This extends and enables us to reason about subcontracting, delegation, commitment-based agreements, and in general scenarios in which agents have mixed strategies, consisting of physical and communicative actions.