Whether it be assigning teachers to classes [Kraus et al., 2020], or employees (nurses) to tasks (wards/shifts) [Warner and Prawda, 1972], task allocation is essential for the smooth function of human-human teams. In the context of indivisible tasks, the goal of task allocation is to assign individual agents of a team to a subset of tasks such that a pre-defined set of metrics are optimized. When the cost-information about all the team members and a performance measure is known upfront, one can capture the trade-off between some notion of social welfare (such as fairness, envy-free, etc.) and team efficiency (or common rewards) [Bertsimas et al., 2012]. In a distributed setting, agents may have to negotiate back-and-forth to arrive at a final allocation [Saha and Sen, 2007]. In the negotiation, agents can either choose to accept an allocation proposed by other agents or reject it; upon rejection, agents can propose an alternative allocation that is more profitable for them and, given their knowledge, still acceptable to others. While distributed negotiation-based allocations will at least keep the agents happy with their lot (since they got what they negotiated for), it tends to have two major drawbacks for human negotiators. First, an agent may not be fully aware of their teammates’ costs and the performance metrics, resulting in the need for iteratively sharing cost information. Second, the process can be time-consuming and can increase the human’s cognitive overload, leading to sub-optimal solutions.
In contrast, a centralized allocation can be efficient, but will certainly be contested by disgruntled agents who, given their incomplete knowledge, may not consider it to be acceptable. Thus, a centralized system needs to be ready to provide the user with an explanation. As discussed in [Kraus et al., 2020], such explanations can aid in increasing people’s satisfaction [Bradley and Sparks, 2009] and maintain the system’s acceptability [Miller, 2018]. In a multi-agent environment such as task allocation, providing explanations is considered to be both important and a challenging problem [Kraus et al., 2020].
To address these challenges, we blend aspects of both the (centralized and distributed) approaches and propose AITA, an Artificial Intelligence-powered Task Allocator. Our system (1) uses a centralized allocation algorithm patterned after negotiation to come up with an allocation that explicitly accounts for the costs of the individual agents and overall performance, and (2) can provide contrastive explanation when a proposed allocation is contested using a counterfactual. We assume AITA is aware of all the individual costs and the overall performance costs.1 Use of a negotiation-based mechanism for coming up with a negotiation-aware explicable allocation helps reuse the inference process to provide contrastive explanations. Our explanations have two desirable properties. First, the negotiation-tree based explanation by AITA has a graphical form that effectively distills relevant pieces from a large amount of information (see Figure 1); this is seen as a convenient way to explain information in multi-agent environments [Kraus et al., 2020]. Second, the explanation, given it is closely tied to the inference process, acts as a certificate
Figure 1: AI Task Allocator (AITA) comes up with a negotiation-aware explicable allocation for a set of two humans– 0 and 1. In this allocation, human 0 is assigned tasks 1, 3 and 4 and agent 1 is assigned tasks 2 and 5. A dissatisfied human 1 questions AITA with a counterfactual allocation
, where he/she just needs to do task 5 (they believe task 5 is much more difficult and will take similar effort compared to doing all the 4 others). AITA then explains why the original proposed allocation (i.e.
) is better than the counterfactual allocation (i.e.
). The graph of the negotiation tree can be given as a dialogue ”if human 1 proposes the allocation
, it will be rejected and AITA will offer
, which will then be rejected and human 0 will propose a counter offer
which will then will have to be accepted by all. This final allocation would have a higher cost for you (human 1) than the first proposed allocation. Hence, the counterfactual allocation will eventually result in worse-off allocation for human 1.
that guarantees explicability to the human (i.e. no other allocation could have been more profitable for them while being acceptable to others). While works like [Kraus et al., 2020] recognize the need for such negotiation-aware and contestable allocation systems, their work is mostly aspirational. To the best of our knowledge, we are the first to provide concrete algorithms for the generation and explanation of allocation decisions. To evaluate our work, we conduct human studies in three different task allocation scenarios and show that the allocations proposed by AITA are deemed fair by the majority of subjects. Users who questioned AITA’s allocations, upon being explained, found it understandable and convincing in two control cases. Further, we consider an approximate version of the negotiation-based algorithm for larger task allocation domains and, via numerical simulation, show how underestimation of a teammate’s costs and different aspects of incompleteness affect explanation length.
In this section, we situate our work in the landscape of multi-agent task allocation, explicable decision making and model reconciliation explanations.
Task allocation
As mentioned above, challenges in task allocation are either solved using centralized or distributed approaches; the later are more considerate of incomplete information settings. Centralized approaches often model the allocation problem as a combinatorial auction [Hunsberger and Grosz, 2000; Cramton, 2006]. In human teams, members often have incomplete knowledge about fellow team members and overall performance costs. Thus, a proposed allocation may not seem reasonable to the human. Given existing centralized approaches, there is no way for the human to initiate dialog. Moreover, regardless of optimality or accuracy, a centralized decision making system should be contestable On the other hand, distributed methods allow agents to autonomously negotiate and agree on local deals [Chevaleyre et al., 2010; Chevaleyre et al., 2006], finally to reach a consensus– an allocation that is Pareto Optimal [Brams and Taylor, 1996; Saha and Sen, 2007; Endriss et al., 2006; Endriss et al., 2003]. Beyond negotiation mechanisms, works have also explored the use of bargaining games to model bilateral (i.e. two-agent) negotiation scenarios [Erlich et al., 2018; Fatima et al., 2014; Peled et al., 2013].
Explicable Decision Making
Effective human-aware AI systems should generate decisions that are aligned with human expectations. In this regard, explicability is defined based on the alignment of an AI agent’s decision to a human’s expectations [Zhang et al., 2017]. For planning problems, there exist numerous ways, such as syntactic difference, learned labeling function, and cost difference, to calculate this alignment [Kulka- rni et al., 2019; Zhang et al., 2017; Olmo et al., 2020; Sreedharan et al., 20]. While [Sengupta et al., 2018] investigates explanations when planning with a team of humans, none of these works consider explicability when the decision is of interest to multiple humans who have individual preferences and expectations about other humans. In our work, we address this challenge and try to come up with a negotiation-aware explicable allocation that is within a bounded distance of all human’s optimal allocation and Pareto optimal in nature.
Model Reconciliation Explanations
Human-aware AI systems are often expected to be able to explain their decisions [Miller, 2018]. To generate the various types of explanations, several computation methods exist in AI, ranging from explaining decisions of machine learning systems [Ribeiro et al., 2016; Melis and Jaakkola, 2018; Rosenfeld and Richardson, 2019; Anjomshoae et al., 2019; Mualla et al., 2022] to explaining sequential decisions by planners [Chakraborti et al., 2020]. In [Lyons et al., 2021; van der Waa et al., 2021], the authors identify the need for allowing dialog and being able to provide causal explanations as core principles of explanation in decision making systems. While recent works enable humans to contest black-box decisions [Kluttz et al., 2022; Aler Tubella et al., 2020] and provide causal explanation for an observed behavior [Madumal et al., 2020], our work is the first to exhibit both these characteristics in the context of a task-allocation system with multiple humans stakeholders. The need for explanations in our work arises out of the incomplete knowledge the human has about their teammates and the team’s performance metric. We subscribe to the idea of model reconciliation as explanations and enable AITA (similar in spirit to what [Sreedharan et al., 2018] for planning problems) to come up with contrastive explanation when the human deems the proposed task-allocation inexplicable and contests it with a counterfactual.
Task allocation problems are categorized as mixed-motive situations for humans (especially in setting where agents are ought to fulfill their tasks and cannot dismiss it). They are cooperative in forming a team but in getting the assignment they are selfish and considering their own interest. So, for task assignment humans are selfish but at the same time in order to hold a bargain in the team and keep the team they need to consider other teammates and be cooperative. In other words, they are selfish but there is a bound to their selfishness, and the bound comes so the team will not be broken due to selfishness.
Our task allocation problem can be defined using a 3-tuple where A = {0, 1, . . . , n} where n denotes the AI Task Allocator (AITA) and
denotes the n humans,
denotes m indivisible tasks that need to be allocated to the n humans, and
denotes the cost functions of each agent (preferences over tasks, skills and capability of doing tasks are characterized in cost function– eg. cost of infinity for being incapable in doing a task).
represents the overall performance cost metric associated with a task allocation outcome o (defined below).
For a task t, we denote the human i’s cost for that task as . Let O denote the set of allocations and an allocation
represent a one-to-many function from the set of humans to tasks; thus,
. An outcome o can be written as
where each
denotes the human performing task i. Further, let us denote the set of tasks allocated to a human i, given allocation o, as
. For any allocation
, there are two types of costs for AITA:
(1) Cost for each human i to adhere to o. In our setting, we consider this cost as .
(2) An overall performance cost .
Example. Consider a scenario with two humans {0, 1} and five tasks . An allocation outcome can thus be represented as a binary (in general, base-n) string of length five (in general, length m). For example,
represents a task allocation in which agent 0 performs the three tasks
and 1 performs the remaining two tasks
. The true cost for human 0 is
, while the true cost for 1 is
.
Negotiation Tree A negotiation between agents can be represented as a tree whose nodes represent a two-tuple (i, o) where is the agent who proposes outcome o as the finalallocation. In each node of the tree, all other agents
can choose to either accept or reject the allocation offer o. If any of them choose to reject o, in a turn-based fashion2, the next agent i + 1 makes an offer
that is (1) not an offer previously seen in the tree (represented by the set
, and (2) is optimal with regards to agent i + 1’s cost among the remaining offers
. This creates the new child
and the tree progresses either until all agents accept the offer or all outcomes are exhausted. Note that in the worst case, the negotiation tree can consist of
nodes, each corresponding to one allocation in O. Each negotiation step, represented as a child in the tree, increases the time needed to reach a final task allocation. Hence, similar to [Baliga and Serrano, 1995], we consider a discount factor (given we talk about costs as opposed to utilities) as we progress down the negotiation tree. Although we defined what happens when an offer is rejected, we did not define the criteria for rejection. The condition for rejection or acceptance of an allocation o can be defined as follows.
where represents a negotiation-aware explicable al- location as per agent i.
In this section, we first formally define a negotiation-aware explicable allocation followed by how it can be computated.
Definition–Negotiation-Aware Explicable Allocation: An allocation is considered explicable by all agents iff, upon negotiation, all the agents are willing to accept it. Formally, an acceptable allocation at step s of the negotiation, denoted as , has the following properties:
1. All agents believe that allocations at a later step of the negotiation will result in a higher cost for them.
2. All allocations offered by agent i at step before s, denoted as
, is rejected at least by one other agent. The opt in the subscript indicates that the allocation
at step
has the optimal cost for agent i at step
. Formally,
We now describe how AITA finds a negotiation-aware explicable allocation.
Negotiation-Aware Explicable Allocation Search The negotiation process to find an explicable allocation can be viewed as an sequential bargaining game. At each period of the bargaining game, an agent offers an allocation in a round-robin fashion. If this allocation is accepted by all agents, each agent incurs a cost corresponding to the tasks they have to accomplish in the allocation proposed (while AITA incurs the team’s performance cost). Upon rejection (by even a single agent), the game moves to the next period. Finding the optimal offer (or allocation in such settings) needs to first enumerate all the periods of the sequential bargaining game. In our case, this implies constructing an allocation enumeration tree, i.e. similar to the negotiation tree but considers what happens if all proposed allocations were rejected. In the generation of this allocation enumeration tree, we assume the humans, owing to limited computational capabilities, can only reason about a subset of the remaining allocations. While any subset selection function can be used in all the algorithms presented in this paper, we will describe a particular one in the next section.
Given that the sequential bargaining game represents an extensive form game, the concept of Nash Equilibrium allows for non-credible threats. In such settings a more refined concept of Sub-game Perfect Equilibrium is desired [Osborne and others, 2004]. We first define a sub-game and then, the notion of a Sub-game Perfect Equilibrium.
Sub-game: After any non-terminal history, the part of the game that remains to be played (in our context, the allocations not yet proposed) constitutes the sub-game.
Sub-game Perfect Equilibrium (SPE): A strategy profile is the SPE of a perfect-information extensive form game if for every agent i and every history h (after which i has to take an action), the agent i cannot reduce its cost by choosing a different action, say
, not in
while other agents stick to their respective actions. If
denotes the outcome of history h when players take actions dictated by
, then
.
Given the allocation enumeration tree, we can use the notion of backward induction to find the optimal move for all agents in every sub-game [Osborne and others, 2004]. We first start from the leaf of the tree with a sub-tree of length one. We then keep moving towards the root, keeping in mind the best strategy of each agent (and the allocation it leads to). We claim that if we repeat this procedure until we reach the root, we will find a negotiation-aware explicable allocation. To guarantee this, we prove two results– (1) an SPE always exists and can be found by our procedure and (2) the SPE returned is an explicable allocation.
Lemma There exists a non-empty set of SPE. An element of this set is returned by the backward induction procedure.
Proof Sketch. Note that the backward induction procedure always returns a strategy profile; in the worst case, it corresponds to the last allocation offered in the allocation enumeration tree. Each agent selects the optimal action at each node of the allocation enumeration tree. As each node represents the history of actions taken till that point, any allocation node returned by backward induction (resultant of optimal actions taken by agents), represents a strategy profile that is an SPE by definition. Thus, an SPE always exists.
Corollary The allocation returned by backward induction procedure is an acceptable allocation.
Proof Sketch. A proof by contradiction shows that if the allocation returned is not an acceptable allocation, then it is not the SPE of the negotiation game, contradicting Lemma.
Given the introduced algorithm, AITA, with the correct information about the costs, and considering the limited computational capability of the humans, cames up with a negotiation-aware explicable allocation and proposed it to the human.
Counterfactual Allocation In scenarios where the human has (1) access to all the true costs of them and others and (2) computation capabilities to reason about a full negotiation tree, they will simply realize that AITA’s allocation is explicable and does not need an explanation. However, for many real world settings, a human may not be fully aware of the utility functions of the other humans [Saha and Sen, 2007]. So in our setting, we formalize this by assuming a human i is only aware of its costs and has noisy information about all the other utility functions
and the performance costs (when j = n). We represent i’s noisy estimate of j’s cost as
. For a task t, we denote the human i’s perception of j’s cost as
. Given the incomplete information setting, a human’s perception of costs for an allocation o relates to their (true) cost
, noisy idea of other agent’s costs
, and noisy idea of the overall team’s performance cost
. Given human i’s limited computational abilities, and knowledge about
, and
(the latter two being inaccurate),
might not be equal to
that AITA proposes. Therefore, a counterfactual allocation may raise by human i who may be able to come up with an allocation that they think has lower cost for them and will be accepted by all other players. Note that human may assume the centralized agent may make inadvertent errors but not deliberate misallocation and there is no consideration about deception, misuse or irrationality in this work.
Formally, we define the notion of an optimal counterfactual as follows.
The optimal counterfactual for a human i is an alternative allocation , given AITA’s proposed allocation o, that has the following properties.
1. is in the set of allocations regarding their limited computational capability (this implies that
)
2. has lower cost in
)
3. is an SPE in the allocation enumeration tree made from allocations from o given their computational capability.
Explanation as a Negotiation Tree
We show that when an optimal counterfactual exists for a human
, AITA can come up with an effective explanation that refutes it, i.e. explains how the counterfactual
can later result in an acceptable allocation that is not better than o.
We thus propose to describe a negotiation tree, which starts with the counterfactual at its root and excludes the original allocation o, as an explanation. This differs from the human’s negotiation tree because it uses the actual costs as opposed to using the noisy cost estimates.3 Further, AITA, with no limits on computation capabilities, can propose allocations that are not bound by the subset selection function. We finally show that an SPE in this tree results in an SPE that cannot yield a lower cost for the human i than o. At that point, we expect a rational human to be convinced that o is a better allocation than the counterfactual
. Note that a large allocation problem does not imply a long explanation (i.e. a negotiation tree of longer path from root to lowest leaf). In turn, a larger problem does not necessarily make an explanation verbose. We can now define what an explanation is in our case.
Explanation. An explanation is a negotiation tree (note that this negotiation tree can be cast as a natural language or dialogue) with true costs that shows the counterfactual allocation will result in a final allocation
such that
.
Even before describing how this looks in the context of our example, we need to ensure one important aspect– given a counterfactual against o, an explanation always exists.
Proposition Given allocation o (the explicable allocation offered by AITA) and a counterfactual allocation (offered by i), there will always exist an explanation.
Proof Sketch: We showcase a proof by contradiction; suppose an explanation does not exist. It would imply that there exists that reduces human i’s cost (i.e.
) and is accepted by all other players after negotiation. By construction, o was an explicable allocation and thus, if a human was able to reduce its costs without increasing another agent’s cost, all agents will not have accepted o. As
is also the resultant of a sub-game perfect equilibrium strategy of the allocation enumeration tree with true costs, AITA would have chosen
. Given AITA chose o, there cannot exist such a
An Example of Limited Computational Capabilities: Subset Selection Function An example of subset function can be assuming that given a particular allocation outcome , a human will only consider outcomes
where only one task in o is allocated to a different human j. In the context of our example, given allocation
, the human can only consider the three allocations
and
; outcomes are one Hamming distance away. With this assumption in place, a human is considered capable of reasoning about a negotiation tree with
allocations
Table 1: Options selected by participants for the three different domains used in the human studies.
(as opposed to ) in the worst case.4 While there can be other ways to assume subset function that shows human limited computational capability. The described 1-edit distance function will be used in Experimental Results as an assumption for limited computational capability of human.
In this section, we try to examine whether the proposed explicable allocation is perceived to be fair and the effectiveness of the contrastive explanations generated by AITA. For this, we consider two different human study experiments. In one setting, if a user selects an allocation is unfair, we ask them to rate our explanation and two other baselines (relative case). In the other case, we simply provide them our explanation (absolute case). We then consider the effect of different kinds of inaccuracies (about costs) on the explanation length for a well-known project management domain [Certa et al., 2009].
Human Subject Studies We briefly describe the study setup for the two human studies.
Relative Case In this setting, we consider two different task allocation scenarios. The first one considers cooking an important meal at a restaurant with three tasks and two teammates– the chef and the sous-chef. The second one considers dividing five tasks associated with a class project between a senior grad and a junior grad/undergrad student. In the first setting, the human subject plays the role of a sous-chef and are told they are less efficient at cooking meals and may produce a meal of low overall quality (the performance cost is interpreted as the customer ratings seen so far). In the second setting, the human subject fills in the role of the senior student who is more efficient at literature review, writing reports and can yield a better quality project (as per the grading scheme of an instructor). We recruited a total of 38 participants of whom 54.3% were undergraduate and 45.7% were graduate students in Computer Science & Engineering and Industrial Engineering at our university . All of them were made to answer a few filter questions correctly to ensure they fully understood the scenarios.
In the study, we presented the participants with AITA’s proposed allocation and counterfactual allocations that adhere to the one-hamming distance subset selection function defined above. This let us consider two and three counterfactual allocations for the cooking and the class project domains respectively.5. When the human selects a counterfactual, implying that AITA’s proposed allocation is inexplicable, we present them with three explanations. Besides our negotiation-tree based explanation, we showcase two baseline explanations– (1) A vacuous explanation that simply states that the human’s counterfactual won’t be accepted by others and doesn’t ensure a good overall performance metric, (2) A verbose explanation that provides the cost of all their teammates and the performance metric for all allocations.
Absolute Case Setup In this case, we considered a task allocation scenario where two research students– a senior researcher and a junior researcher– are writing a paper and the three tasks relate to working on different parts of the paper. In this setting, we gathered data from 40 graduate students. Similar to the previous case, the subjects have to select whether the AITA’s proposed allocation is fair or select between either of the two counterfactual allocations (each adhering to the subset selection constraint). In contrast to the previous case, upon selecting a counterfactual, the subject is only presented with the negotiation-tree explanation.
Results In Table 1, we see that a majority of the participants selected AITA’s allocation as fair across all the three different domains. This shows that our formally defined negotiation-aware explicable allocation does indeed appear fair to participants. Given that a set of the participants felt that the allocation is unfair, we were able to establish a scenario where they desired explanations. Instead of having them calculate a counterfactual, we presented them with options they would might want to use as a counterfactual. We noticed that the highest selected counterfactual was the optimal counterfactual, calculated using the SPE mechanism over the human’s negotiation tree in the background (that is generated assuming the human’s computational capabilities are limited). For the cooking and paper writing domains, the result was statistically significant, highlighting that our computational methods are indeed able to come up with the optimal counterfactual that is in line with how humans would come up with a counterfactual. The least selected option was the other sub-optimal counterfactual allocations.
For participants who asked for explanations by providing a counterfactual, we had two settings– relative and absolute. In the relative case, they were asked to rate the comprehensibility and convincing power of the three explanations on a scale of . In absolute case, only our explanation was provided to them. We observed that the negotiation tree was judged to be understandable and moderately convincing on average in the absolute setting. In the cumulative setting, results in both the cooking and the class project domain show that our explanation is the most convincing one. It is also perceived as the most understandable explanation, but shared the stage with the Vacuous explanation (the average scores and additional metrics are available in the supplementary file).
Statistical Significance To further compare our negotiation-tree based explanation with the other two– vacuous and verbose– explanations, we performed one-way ANOVA and a non-parametric Kruskal-Wallis tests with Bonferroni correction. The results of both ANOVA test (F(2, 24) = 8.96, p = 0.001), and Kruskal-Wallis test (p = 0.003) show that (1) the three explanations are different in term of convincing power and (2) the negotiation-tree based explanation is the most convincing while the vacuous explanation is the least convincing (rank sum: 172.5 > 140 > 65.5). However, ANOVA (F(2, 24) = 0.04, p = 0.96) and Kruskal-Wallis (p = 0.68) tests show that all the three explanations are not greatly different when it comes to human understanding. So, for understanding, we further performed pair-wise comparison of explanations with pairwise Mann-Whitney tests. Along similar lines, this test also didn’t show any significant difference between the pairs (p = 0.63, 0.42 and 0.73). Finally, we used the TOST (equivalent test) to evaluate if three explanations are equivalent in terms of understanding. TOST showed that all three explanations are all equal in terms of understanding with 90% confidence interval and
in
. Therefore, we can conclude that while our negotiation-tree based explanation is the most convincing one, it is similar to the other in terms of understandable rating by humans.
Impact of Noise on Explanations For this study, we use the project management scenario from [Certa et al., 2009] in which human resources are allocated to R&D projects. We modify the original setting in three ways. First, we consider two and four humans instead of eight for assigning the five projects, allowing a total of possible allocations. It allows for explanations of reasonable length where allocations can be represented as 5-bit binary strings (see Fig- ure 1). Second, we only consider the skill aspect, ignoring the learning abilities of individuals and social aspects of an allocation. This was mostly done because we could not confidently specify a relative prioritization of the three. We use the skill to measure the time needed, and in turn the cost, for completing a project (more the time needed, more the cost). There are a total of
actual costs, 5 for each human (the detail costs in supplementary material), and 10 additional costs representing the noisy perception of one human’s cost by their teammate. Third, we consider an aggregate metric that considers the time taken by the two humans to complete all the tasks. Corresponding to each allocation, there are 32 (true) costs for team performance. With these costs, as shown in Figure 1, the negotiation-aware explicable allocation is
, the optimal counterfactual for agent 1 is
which is revoked by AITA using an explanation tree of length three.
Impact of Norm-bounded Noise. The actual cost of each human i as a vector of length m. A noisy assumption can be represented by another vector situated
(in
norm) distance away. By controlling
, we can adjust the magnitude of noise a human has. In Figure 2, we plot the effect of noise on the average explanation length. The noisy cost vectors are sampled from the
norm ball within
radius scaled by highest cost in the actual cost vectors [Calafiore et al., 1998].6 The y-axis indicates the length of the replay negotiation tree shown to the human. Even though the maximum length of explana-
Figure 2: Mean length of explanations as the amount of noise added to the actual costs increases.
tion could be , we saw the maximum explanation length was 8. Given that every noise injected results in a different scenario, we average the explanation length across ten runs (indicated by the solid lines). We also plot the additive variance (indicated by the dotted lines). The high variance on the negative side (not plotted) is a result of the cases where either (or both) of the human(s) human team members didn’t have an optimal counterfactual and thus, the explanation length was zero.
We initially hypothesized, based on intuition, that an increase in the amount of noise will result in a longer explanation. The curve in red (with ) is indicative that this is not true. To understand why this happens, we classified noise into two types– Optimistic Noise (ON) and Pessimistic Noise (PN)– representing the scenarios when a human overestimates or under-estimates the cost of the other humans for performing a task. When a human overestimates the cost of others, it realizes edits to a proposed allocation will lead to a higher cost for other agents who will thus reject it. Thus, optimal counterfactual ceases to exist and thus, explanations have length zero (reducing the average length). In the case of PN, the human underestimates the cost of teammates. Thus, upon being given an allocation, they often feel this is inexplicable and find an optimal counterfactual demanding explanations. As random noise is a combination of both ON and PN (overestimates costs of some humans for particular tasks but underestimates their cost for other tasks etc.), the increase in the length of explanations is counteracted by zero length explanations. Hence, in expectation, we do not see an increase in explanation length as we increase the random noise magnitude. As per this understanding, when we increase
and only allow for PN, we clearly see an increase in the mean explanation length (shown in green).
When , there is no noise added to the costs, i.e. the humans have complete knowledge about the team’s and the other agent’s costs. Yet, due to limited computational capabilities, a human may still come up with a counterfactual that demands explanation. Hence, we observe a mean explanation length of 1 even for zero noise. This should not be surprising because, when coming up with a foil, a human only reasons in the space of
allocations (instead of
allocations).
Figure 3: As the number of agents about whom a human has complete knowledge (co-workers whose costs you know) increases, the mean length of explanations decreases.
Incompleteness about a subset of agents. In many realworld scenarios, an agent may have complete knowledge about some of their team-mates but noisy assumptions about others. To study the impact of such incompleteness, we considered a modified scenario project-management domain [Certa et al., 2009] with four tasks and four humans. We then choose to vary the size of the sub-set about whom a human has complete knowledge. In Fig. 3, we plot the mean length of explanations, depending upon the subset size about whom the human has complete knowledge. On the x-axis, we plot the size of the subset and on the y-axis, we show the relative explanation length that equals to explanation length divided by the longest explanation () we can have in this setting. We consider five runs for each sub-set size and only pessimistic noise (that ensures a high probability of having a counterfactual and thus, needing explanations). We notice as the number of individuals about whom a human has complete knowledge increases, the mean relative explanation length (times the max explanation length) decreases uniformly across the different magnitude of noise
. Even when a human has complete knowledge about all other agent’s costs, happens whenever the size of the sub-set is
(three in this case), it may still have some incompleteness about the team’s performance costs. Added with limited computational capabilities (to search in the space of 16 allocations), they might still be able to come up with counterfactual; in turn, needing explanations. Thus, the third set of bar graphs (corresponding to the label 3 (100.00%) on the x-axis) has a mean of
relative explanation length.
In this paper, we considered a task allocation problem where AITA, a centralized AI Task Allocator comes up with a negotiation-aware explicable allocation using a simulated negotiation based approach, which are popular in distributed task allocation settings, for a team of humans. When the humans have limited computational capability and incomplete information about all costs except their own, they may be dissatisfied with AITA’s proposed allocation and question AITA using counterfactual allocations that they believe are explicable. We show that in such cases, AITA is able to come up with a negotiation tree that (1) is representative of the inference methodology used and (2) explains that if the counterfactual was considered, it would result in final allocation that is worse-off than the one proposed. With human studies, we show that the negotiation-aware allocation appears as fair to majority of humans while for the others, our explanations are understandable and convincing. We also perform experiments to show that when agents either overestimate the cost of other agents or have accurate information about more agents, the average length of explanations decreases.
Acknowledgments. This research is supported in part by ONR grants N00014-16-1-2892, N00014-18-1-2442, N00014-18-1-2840, N00014-9-1-2119, AFOSR grant FA9550-18-1-0067, DARPA SAIL-ON grant W911NF-19-2-0006, and a JP Morgan AI Faculty Research grant.
[Aler Tubella et al., 2020] Andrea Aler Tubella, Andreas Theodorou, Virginia Dignum, and Loizos Michael. Contestable black boxes. In International Joint Conference on Rules and Reasoning, pages 159–167. Springer, 2020.
[Anjomshoae et al., 2019] Sule Anjomshoae, Amro Najjar, Davide Calvaresi, and Kary Fr¨amling. Explainable agents and robots: Results from a systematic literature review. In 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montreal, Canada, May 13–17, 2019, pages 1078–1088. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
[Baliga and Serrano, 1995] Sandeep Baliga and Roberto Serrano. Multilateral bargaining with imperfect information. Journal of Economic Theory, 67(2):578–589, 1995.
[Bertsimas et al., 2012] Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. On the efficiency-fairness trade-off. Management Science, 58(12):2234–2250, 2012.
[Bradley and Sparks, 2009] Graham L Bradley and Bever- ley A Sparks. Dealing with service failures: The use of explanations. Journal of Travel & Tourism Marketing, 26(2):129–143, 2009.
[Brams and Taylor, 1996] Steven J Brams and Alan D Tay- lor. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press, 1996.
[Calafiore et al., 1998] G Calafiore, F Dabbene, and R Tempo. Uniform sample generation in l/sub p/balls for probabilistic robustness analysis. In Proceedings of the 37th IEEE Conference on Decision and Control (Cat. No. 98CH36171), volume 3, pages 3335–3340. IEEE, 1998.
[Certa et al., 2009] Antonella Certa, Mario Enea, Giacomo Galante, and Concetta Manuela La Fata. Multi-objective human resources allocation in r&d projects planning. International Journal of Production Research, 47(13):3503– 3523, 2009.
[Chakraborti et al., 2020] Tathagata Chakraborti, Sarath Sreedharan, and Subbarao Kambhampati. The emerging landscape of explainable ai planning and decision making. arXiv preprint arXiv:2002.11697, 2020.
[Chevaleyre et al., 2006] Yann Chevaleyre, Paul E Dunne, Ulle Endriss, J´erˆome Lang, Michel Lemaitre, Nicolas Maudet, Julian Padget, Steve Phelps, Juan A RodriguezAguilar, and Paulo Sousa. Issues in multiagent resource allocation. Informatica, 30(1), 2006.
[Chevaleyre et al., 2010] Yann Chevaleyre, Ulle Endriss, and Nicolas Maudet. Simple negotiation schemes for agents with simple preferences: Sufficiency, necessity and maximality. Autonomous Agents and Multi-Agent Systems, 20(2):234–259, 2010.
[Cramton, 2006] P Cramton. Introduction to combinatorial auctions. p. cramton, y. shoham, r. steinberg, eds., combinatorial auctions, 2006.
[Endriss et al., 2003] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. On optimal outcomes of negotiations over resources. In AAMAS, volume 3, pages 177–184, 2003.
[Endriss et al., 2006] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Negotiating socially optimal allocations of resources. Journal of artificial intelligence research, 2006.
[Erlich et al., 2018] Sefi Erlich, Noam Hazon, and Sarit Kraus. Negotiation strategies for agents with ordinal preferences. arXiv preprint arXiv:1805.00913, 2018.
[Fatima et al., 2014] Shaheen Fatima, Sarit Kraus, and Michael Wooldridge. The negotiation game. IEEE Intelligent Systems, 29(5):57–61, 2014.
[Hunsberger and Grosz, 2000] Luke Hunsberger and Bar- bara J Grosz. A combinatorial auction for collaborative planning. In Proceedings fourth international conference on multiagent systems, pages 151–158. IEEE, 2000.
[Kluttz et al., 2022] Daniel N Kluttz, Nitin Kohli, and Deirdre K Mulligan. Shaping our tools: Contestability as a means to promote responsible algorithmic decision making in the professions. In Ethics of Data and Analytics, pages 420–428. Auerbach Publications, 2022.
[Kraus et al., 2020] Sarit Kraus, Amos Azaria, Jelena Fiosina, Maike Greve, Noam Hazon, Lutz Kolbe, TimBenjamin Lembcke, Jorg P Muller, Soren Schleibaum, and Mark Vollrath. Ai for explaining decisions in multi-agent environments. 34(09):13534–13538, 2020.
[Kulkarni et al., 2019] Anagha Kulkarni, Yantian Zha, Tathagata Chakraborti, Satya Gautam Vadlamudi, Yu Zhang, and Subbarao Kambhampati. Explicable planning as minimizing distance from expected behavior. In AAMAS, 2019.
[Lyons et al., 2021] Henrietta Lyons, Eduardo Velloso, and Tim Miller. Conceptualising contestability: Perspectives on contesting algorithmic decisions. Proceedings of the ACM on Human-Computer Interaction, 5(CSCW1):1–25, 2021.
[Madumal et al., 2020] Prashan Madumal, Tim Miller, Liz Sonenberg, and Frank Vetere. Explainable reinforcement learning through a causal lens. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 2493–2500, 2020.
[Melis and Jaakkola, 2018] David Alvarez Melis and Tommi Jaakkola. Towards robust interpretability with self-explaining neural networks. In Advances in Neural Information Processing Systems, pages 7775–7784, 2018.
[Miller, 2018] Tim Miller. Explanation in artificial intelli- gence: Insights from the social sciences. Artificial Intelligence, 2018.
[Mualla et al., 2022] Yazan Mualla, Igor Tchappi, Timotheus Kampik, Amro Najjar, Davide Calvaresi, Abdeljalil Abbas-Turki, St´ephane Galland, and Christophe Nicolle. The quest of parsimonious xai: A human-agent architecture for explanation formulation. Artificial Intelligence, 302:103573, 2022.
[Olmo et al., 2020] Alberto Olmo, Sailik Sengupta, and Subbarao Kambhampati. Not all failure modes are created equal: Training deep neural networks for explicable (mis) classification. arXiv preprint arXiv:2006.14841, 2020.
[Osborne and others, 2004] Martin J Osborne et al. An introduction to game theory, volume 3. Oxford university press New York, 2004.
[Peled et al., 2013] Noam Peled, Sarit Kraus, et al. An agent design for repeated negotiation and information revelation with people. In Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
[Ribeiro et al., 2016] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should i trust you?: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135–1144. ACM, 2016.
[Rosenfeld and Richardson, 2019] Avi Rosenfeld and Ariella Richardson. Explainability in human–agent systems. Autonomous Agents and Multi-Agent Systems, 33(6):673–705, 2019.
[Saha and Sen, 2007] Sabyasachi Saha and Sandip Sen. An efficient protocol for negotiation over multiple indivisible resources. In IJCAI, volume 7, pages 1494–1499, 2007.
[Sengupta et al., 2018] Sailik Sengupta, Tathagata Chakraborti, and Subbarao Kambhampati. Ma-radar–a mixed-reality interface for collaborative decision making. ICAPS UISP, 2018.
[Sreedharan et al., 20] Sarath Sreedharan, Tathagata Chakraborti, Christian Muise, and Subbarao Kambhampati. Expectation-aware planning: A unifying framework for synthesizing and executing self-explaining plans for human-aware planning. AAAI, 20.
[Sreedharan et al., 2018] Sarath Sreedharan, Siddharth Srivastava, and Subbarao Kambhampati. Hierarchical expertise level modeling for user specific contrastive explanations. In IJCAI, pages 4829–4836, 2018.
[van der Waa et al., 2021] Jasper van der Waa, Elisabeth Nieuwburg, Anita Cremers, and Mark Neerincx. Evaluating xai: A comparison of rule-based and example-based explanations. Artificial Intelligence, 291:103404, 2021.
[Warner and Prawda, 1972] D Michael Warner and Juan Prawda. A mathematical programming model for scheduling nursing personnel in a hospital. Management Science, 19(4-part-1):411–422, 1972.
[Zhang et al., 2017] Yu Zhang, Sarath Sreedharan, Anagha Kulkarni, Tathagata Chakraborti, Hankz Hankui Zhuo, and Subbarao Kambhampati. Plan explicability and predictability for robot task planning. In ICRA, pages 1313– 1320. IEEE, 2017.
Table 1: Human study scores for our negotiation-tree based explanations compared to the two baselines.
Table 2: Agent’s true costs for completing a task.
We will ask you about how understandable and convincing each explanation is after presenting it. Feel free to scroll back and forth and revise your ratings after seeing all
The allocation offered by you is not a better allocation because (1) it will not be accepted by your coworker and (2) is not of better overall quality.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
The overall quality score for each allocation is given below (task order: Buying stuff, Appetizer, Main dish). e.g. C,Y,C represents an allocation where the first and third task is allocated to your Co-worker (C) and the second task is allocated to You (Y). ---C,C,C = 9.4 C,C,Y = 6.2 C,Y,C = 8.6 C,Y,Y = 5.2 Y,C,C = 8.2 Y,C,Y = 5 Y,Y,C = 7.2 Y,Y,Y = 4 ---
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
In explanation 3, why the final cost for you is 8.41 while the hours needed to do the task is 8 hour? *
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
We will ask you about how understandable and convincing each explanation is after presenting it. Feel free to scroll back and forth and revise your ratings after seeing all the explanations.
The allocation offered by you is not a better allocation because (1) it will not be accepted by your teammate and (2) is not of better overall quality.
The overall quality score for each allocation is given below (task order: Buying stuff, Appetizer, Main dish). e.g. C,Y,C represents an allocation where the first and third task is allocated to your Co-worker (C) and the second task is allocated to You (Y). ---C,C,C = 9.4 C,C,Y = 6.2 C,Y,C = 8.6 C,Y,Y = 5.2 Y,C,C = 8.2 Y,C,Y = 5 Y,Y,C = 7.2 Y,Y,Y = 4 ---
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
In this scenario, there are ..... tasks and ..... students in the team for allocating those tasks. *
How many hours do you think your ** teammate needs to analyze the experimental results **? *
We will ask you about how understandable and convincing each explanation is after presenting it. Feel free to scroll back and forth and revise your ratings after seeing all
The allocation offered by you is not a better allocation because (1) it will not be accepted by your teammate and (2) is not of better overall quality.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
For your teammate, ---Doing literature review takes 8 hours Coding and getting experimental results takes 11 hours Analysis and reasoning of the results takes 6 hours Writing the report takes 7 hours Making the presentation and presenting it takes 3 hours ---
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
presenting it. Feel free to scroll back and forth and revise your ratings after seeing all the explanations.
The allocation offered by you is not a better allocation because it will not be accepted by your teammate and is not of better overall quality.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
For your teammate, ---Doing literature review takes 8 hours Coding and getting experimental results takes 11 hours Analysis and reasoning of the results takes 6 hours Writing the report takes 7 hours Making the presentation and presenting it takes 3 hours ---
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
In explanation 3, how much is the cost related to your time and effort spent in negotiating to arrive at a consensus (i.e. till an allocation is approved)? *
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
We will ask you about how understandable and convincing each explanation is after presenting it. Feel free to scroll back and forth and revise your ratings after seeing all the explanations.
The allocation offered by you is not a better allocation because (1) it will not be accepted by your teammate and (2) is not of better overall quality.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
For your teammate, ---Doing literature review takes 8 hours Coding and getting experimental results takes 11 hours Analysis and reasoning of the results takes 6 hours Writing the report takes 7 hours Making the presentation and presenting it takes 3 hours ---
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
Understandable here just means how much you understand what AITA is saying; NOT if you are convinced by it.
# Literature review takes 3 hours # Coding and getting experimental results takes 10 hours # Analysis and reasoning of the results takes 5 hours # Writing the report takes 4 hours # Making the presentation and presenting it takes 3 hours
In case you didn't really like any of the allocations shown above or feel you have a better allocation in mind, we would be happy to hear about it.
We will need to record all the responses provided by the participants during the study. Your consent to participate in this study is completely voluntary.
To protect your privacy, responses from participants will never be used individually while compiling or presenting results of the study. The results of this study may be used in reports, presentations, or publications only in aggregate form.
Please provide your email and continue with the study if you agree to take part in this study. Please answer all questions.
If you want to give a score to this explanation from 1 to 5 how much have you convinced by this explanation? *