On Blame Attribution for Accountable Multi-Agent Sequential Decision Making
Year: 2022

Abstract:
Blame attribution is one of the key aspects of accountable decision making, as it provides means to quantify the responsibility of an agent for a decision making outcome. In this paper, we study blame attribution in the context of cooperative multi-agent sequential decision making. As a particular setting of interest, we focus on cooperative decision making formalized by Multi-Agent Markov Decision Processes (MMDPs), and we analyze different blame attribution methods derived from or inspired by existing concepts in cooperative game theory. We formalize desirable properties of blame attribution in the setting of interest, and we analyze the relationship between these properties and the studied blame attribution methods. Interestingly, we show that some of the well known blame attribution methods, such as Shapley value, are not performance-incentivizing, while others, such as Banzhaf index, may over-blame agents. To mitigate these value misalignment and fairness issues, we introduce a novel blame attribution method, unique in the set of properties it satisfies, which trade-offs explanatory power (by under-blaming agents) for the aforementioned properties. We further show how to account for uncertainty about agents’ decision making policies, and we experimentally: a) validate the qualitative properties of the studied blame attribution methods, and b) analyze their robustness to uncertainty. ... a body of people1, holding themselves accountable to nobody, ought not to be trusted by anybody. —Thomas Paine, A philosopher and a political activist.

text: ... a body of people1, holding themselves accountable to nobody, ought not to be trusted by anybody.
—Thomas Paine, A philosopher and a political activist.

heading: 1 Introduction
text: With the widespread usage of artificial intelligence (AI) in everyday life [1, 2, 3], accountability has become one of the central problems in the study of AI. Much recent research studied what constitutes accountability in the context of AI and how to design accountable AI systems [4, 5, 6], and recent policies and legislations [7] are increasingly highlighting the importance of accountability, aiming to provide guidelines for developing and deploying accountable AI systems.
Accountability is a relatively broad term, and it typically involves an actor (or multiple actors) justifying their decisions and facing consequences for actions taken [6, 8]. Hence, two critical aspects of accountability are explainability and blame attribution. Recent work proposed various methods for explaining, interpreting, understanding, and certifying algorithmic decision-making and its outcomes [9, 10, 11, 12, 13, 14]. In this paper we study the other critical aspect of accountability – blame attribution.
1Originally, and by modern standards outdated, Thomas Paine used phrasing with the word men.
35th Conference on Neural Information Processing Systems (NeurIPS 2021)
In multi-agent decision making, one of the central roles of blame attribution is assigning blame for undesirable outcomes or, broadly speaking, for the system’s inefficiency. Prior work on responsibility and blame in AI [15, 16, 17, 18] has recognized some of the core challenges in attributing blame, including the fact that disentangling agents’ contributions to the final outcome is not a trivial task. Such challenges are particularly prominent in sequential settings where past decisions influence the future ones [16].
In this paper, we consider the task of allocating a score to an agent, which represents the degree of its blame, and reflects its contributions to the total inefficiency of the multi-agent system. We focus on cooperative sequential decision making, formalized by multi-agent Markov decision processes (MMDPs) [19], where the outcome of interest is the expected discounted return of the agents’ joint policy. Concretely, given an MMDP and the agents’ joint policy (true or estimated), we ask: How to score each agent so that the agents’ scores satisfy desirable properties?
To answer this question, we turn to cooperative game theory and consider blame attribution methods that are derived from or inspired by existing concepts in the cost sharing, data valuation, and coalition formation literature [20, 21, 22, 23, 24, 25, 26, 27], such as core [28], Shapley value [29, 30], or Banzhaf index [31, 32]. Taking this perspective on blame attribution, we study blame attribution for accountable multi-agent sequential decision making. More concretely:
• We formalize desirable properties that blame attribution methods should satisfy in cooperative multi-agent sequential decision making. We identify properties that are typically not considered in the cost-sharing literature, yet are important for decision making. In particular, we introduce two novel properties: a) performance monotonicity, which states that, having fixed all the other agents to their policies, the blame assigned to an agent should not increase if the agent adopts a policy that results in a higher expected discounted return (implying that the method is performanceincentivizing); b) Blackstone consistency,2 which states that an agent should not receive a higher blame just because the agents’ policies are not fully known to the blame attribution procedure.
• We characterize the properties of the studied blame attribution methods. We show that some blame assignment methods, such as, Shapley value, are not performance-monotonic (and, hence, performance-incentivizing), while others, such as Banzhaf index, may over-blame agents. Motivated by these results, we introduce a novel blame attribution method that trade-offs explanatory power (by under-blaming agents) for the aforementioned properties.
• We provide algorithms for making the studied blame attribution methods Blackstone-consistent when the agents’ policies are estimated. We also characterize the effect of uncertainty on blame attribution methods.
• Using a simulation-based testbed, we experimentally analyze the studied blame attribution methods, their qualitative properties, as well as their robustness to uncertainty. The experiments showcase the importance of the robustness considerations we study and indicate that typically more efficient blame attribution methods (i.e., those that assign more blame in total) are less robust to uncertainty.

heading: 1.1 Other Related Work
text: Apart from the works mentioned in the previous paragraphs, our work relates to different areas of moral philosophy, law, and AI, and here we highlight some of the most relevant references. Research in moral philosophy and law has extensively studied the problem of blame attribution, both in terms of human actors [34, 35, 36], as well as AI actors [37, 38, 39, 40]. We take some of the well known principles in moral philosophy and law in determining properties relevant for blame attribution, e.g., Blackstone consistency is inspired by Blackstone’s ratio [33]. In AI, blame attribution has been studied through a more formal lens, utilizing causality [15, 16, 17] and/or game theory [18, 41], and primarily focusing on nuances related to defining notions and degrees of responsibility, blame, and blameworthiness. In contrast, we focus on cooperative sequential decision making, and analyze how different blame attribution methods from cooperative game theory fare under different blame attribution properties. Finally, our work is generally related to the credit assignment problem [42, 43], and more specifically to the credit assignment problem in multi-agent reinforcement learning [44, 45, 46]. However, our focus is not on supporting the learning processes of agents by reducing computational and statistical challenges of learning, but on evaluating the agents’ contributions to the system’s inefficiency, ideally in a fair and interpretable manner.
2This property is inspired by Blackstone’s ratio: “It is better that ten guilty persons escape than that one innocent suffer" [33].

heading: 2 Formal Setting
text: In this section, we describe our formal setting, based on multi-agent Markov decision processes (MMDPs), and we formally model the blame attribution problem in sequential decision making. This section also introduces a set of desirable formal properties of blame attribution methods.

heading: 2.1 Preliminaries
text: We consider a cooperative multi-agent setting, formalized as a class of MMDPsM with n agents {1, ..., n}. Each MMDP in this class is a tuple M = (S, {1, ..., n},A, R, P, γ, σ) [19], where: S is the state space; A = ×ni=1Ai is the action space, with Ai being the action space of agent i; R is the reward function R : S × A → R specifying the reward obtained when agents {1, ..., n} take a joint action; P specifies transitions with P (s, a, s′) denoting the probability of transitioning to s′ from s when agents {1, ..., n} take joint action a = (a1, ..., an); γ is the discount factor; and σ is the initial state distribution. S and A are finite and discrete. A (stationary) joint policy π is a mapping π : S → D(A), where D(A) is a probability simplex overA, with π(a|s) denoting the probability of taking joint action a in s. We assume that a joint policy π is factorizable into agents’ policies, πi, i.e., π(a|s) = π1(a1|s) · · ·πn(an|s). Therefore, we can define an agent i’s policy πi as a mapping from states to a distribution of agent i’s actions, i.e., πi : S → D(Ai). We denote the set of all policies by Π = ×ni=1Πi. We also define a standard performance measure. The expected discounted return of a joint policy π is defined as J(π) = E [∑∞ t=1 γ t−1R(st, at)|s1 ∼ σ, π ] , where the initial state s1 is sampled from σ, and the state-joint action pair of time-step t, (st, at), is obtained by executing joint policy π. We abuse our notation by denoting J(π′i, π−i) = J(π1, ..., π ′ i, ..., πn). Similarly, J(π′S , π−S) = J(π ′′) for some S ⊆ {1, ..., n}, where π′′i = πi if i /∈ S and π′′i = π′i if i ∈ S.

heading: 2.2 Blame Attribution
text: Our goal is to assign blame to agents for failing to jointly achieve optimal performance. Given the agents’ behavior policy, denoted by πb, the inefficiency of the considered multi-agent system can be defined as ∆ = J(π∗)− J(πb), where π∗ ∈ arg maxπ J(π) is an optimal joint policy. Similarly, we define the marginal inefficiency of a subset of agents S ⊆ {1, ..., n} as ∆S = J(π∗|π b S , π b −S)−J(πb), as well as the marginal inefficiency of an agent i as ∆i = J(π ∗|πb i , π b −i) − J(πb), where π∗|π b S (resp. π∗|π b
i ) denotes an optimal policy of S (resp. i) assuming all other policies are fixed, i.e.,
π ∗|πb S ∈ arg maxπS J(πS , π b −S) (resp. π ∗|πb i ∈ arg maxπi J(πi, π b −i)). A blame attribution method is a mapping Ψ :M×Π→ Rn≥0, where Ψ(M,πb) distributes blame for inefficiency ∆ by assigning score βi to agent i. The output of Ψ, i.e., the blame assignment, is denoted by β.
Uncertainty considerations. Since the agents’ behavior policy πb might not be known to the blame attribution procedure, we also define blame attribution under uncertainty as a mapping Ψ̂ : M×P(Π)→ Rn≥0 that outputs a blame assignment estimate β̂. Here, P(Π) represents a set whose elements express the knowledge about πb. Inspired by the literature on robust MDPs [47, 48, 49], we encode such knowledge with uncertainty sets P(πb), one associated to each state s, P(πb, s), defined by the set of probability measures on A. We assume that P(πb) is consistent with πb, i.e., πb(·|s) is in P(πb, s),34 and that every π(·|s) in P(πb, s) factorizes to π(a|s) = π1(a1|s) · · ·πn(an|s). Therefore, P(πb, s) identifies the set of plausible stochastic actions that agent i takes in state s.

heading: 2.3 Desirable Properties
text: Our goal is to specify functions Ψ and Ψ̂, such that the blame assignments β and β̂ satisfy desirable properties. In the following text we denote these properties byR. Below, we define properties that are taken from or inspired by the game theory literature [26, 50, 21], but translated to our setting5:
• Validity (RV ): We say that Ψ is valid if it never distributes more blame than the observed inefficiency ∆. More formally, Ψ satisfiesRV (resp. -RV ) if for every M and πb, ∑n i=1 βi ≤ ∆
(resp. ∑n i=1 βi ≤ ∆ + ), where β = Ψ(M,πb).
3Such P(πb) can be derived from data containing agents’ trajectories and be based on confidence intervals. 4πb(·|s) could be in P(πb, s) w.h.p., provided Blackstone consistency in Section 2.3 is similarly adjusted. 5Note that the terminology is slightly different.
• Efficiency (RE): A more strict condition is that the total distributed blame is equal to ∆. That is, Ψ satisfies RE (resp. -RE) if for every M and πb, ∑n i=1 βi = ∆ (resp. | ∑n i=1 βi −∆| ≤ ),
where β = Ψ(M,πb). • Rationality (RR): Similar to validity is rationality, which requires that blame distributed to any
subset of agents S is not greater than ∆S . That is, Ψ satisfiesRR (resp. -RR) if for every M , πb, and S ⊆ {1, ..., n}, ∑ i∈S βi ≤ ∆S (resp. ∑ i∈S βi ≤ ∆S + ), where β = Ψ(M,πb). • Symmetry (RS): We say that Ψ is symmetric if it treats equal agents equally, i.e., agents that equally contribute to the inefficiency should receive the same blame. More formally, Ψ satisfiesRS (resp. -RS) if for every M and πb, βi = βj (resp. |βi − βj | ≤ ) whenever ∆S∪{i} = ∆S∪{j} for all S ⊆ {1, ..., n}\{i, j}, where β = Ψ(M,πb). • Invariance (RI ): We say that Ψ is invariant if it assigns zero blame to agents who do not marginally contribute to inefficiency. More formally, Ψ satisfies RI (resp. -RI ) if for every M and πb, βi = 0 (resp. βi ≤ ) whenever ∆S∪{i} = ∆S for all S, where β = Ψ(M,πb).
Note that > 0 in the definitions of -R, and that we use these properties in our characterization result for blame attribution under uncertainty. Additionally, we consider two properties that relate the blame attribution output to the MMDP structure and the agents’ behavior policies.
• Contribution monotonicity (RCM )[51]: We say that Ψ is contribution-monotonic if the blame it assigns to an agent depends only on its marginal contributions and monotonically so. More formally, Ψ satisfiesRCM (resp. -RCM ) if for every two (M1, πb 1 ) and (M2, πb2), βi1 ≥ βi2
(resp. βi1 ≥ βi2− ) whenever ∆1S∪{i}−∆ 1 S ≥ ∆2S∪{i}−∆ 2 S for all S, where β 1 = Ψ(M1, πb 1 )
and β2 = Ψ(M2, πb2). • Performance monotonicity (RPerM ): We say that Ψ is performance-monotonic if it does not
assign greater blame to agent i for adopting a policy that results in an equal or higher performance, assuming the other agents’ policies fixed. More formally, consider any MMDP M , and any πb−i, πi and π′i such that J(πi, π b −i) ≤ J(π′i, πb−i). We say that Ψ satisfiesRPerM (resp. -RPerM ) if βi ≥ β′i (resp. βi ≥ β′i − ) where β = Ψ(M, (πi, πb−i)) and β′ = Ψ(M, (π′i, πb−i)).
The above definitions directly extend to Ψ̂ except that we require them to hold for all P(πb). Additionally, we identify the following property for Ψ̂:
• Blackstone consistency (RBC ): We say that Ψ̂ is Blackstone-consistent with Ψ if it never attributes more blame to an agent than Ψ. More formally, Ψ̂ satisfiesRBC(Ψ) if for any M , πb and P(πb), β̂i ≤ βi, where β = Ψ(M,πb) and β̂ = Ψ̂(M,P(πb)).

heading: 3 Game-Theoretic Approaches to Blame Attribution
text: In this section, we study blame attribution methods based on well known game theoretic notions, such as the core [28], Shapley value [29, 30], or Banzhaf index [31, 32]. We also introduce a novel blame attribution method, unique in the set of properties it satisfies. The proofs of our results can be found in the supplementary material.

heading: 3.1 Max-Efficient Rationality
text: We start with a relatively simple blame assignment method that puts rationality as a strict condition, and maximizes the efficiency of blame assignment under this constraint. We call this blame assignment method max-efficient rationality. More formally, max-efficient rationality can be defined via the following linear program:
ΨMER(M,π b) := max
β n∑ i=1 βi s.t. ∑ i∈S βi ≤ ∆S ∀S ⊆ {1, ..., n}, (P1)
where ∆S are precomputed. Max-efficient rationality is inspired by the notion of core, but unlike the core, max-efficient rationality does not require RE (efficiency) to hold. It is easy to show that the following properties are satisfied by any optimizer of (P1), ΨMER. Proposition 1. Every solution to the optimization problem (P1), i.e., ΨMER, satisfiesRV (validity), RR (rationality) andRI (invariance).
Since there might exist multiple optimal solutions to (P1), a tie breaking rule might be needed to decide on the method’s output, ΨMER. We account for this fact in the experiments from Section 5. Note that the constraints in (P1) are quite restrictive, leading to blame assignments that typically distribute very little blame in total. The amount of total blame assigned is important for explanatory power. Namely, a trivial blame attribution method that assigns the score of 0 to every agent satisfies all of the properties from the previous section exceptRE (efficiency), but provides no information regarding the agents’ contributions to the outcome.

heading: 3.2 Marginal Contribution
text: Another intuitive blame assignment method is what we refer to as marginal contribution. This method simply quantifies an agent’s potential to increase the performance of the system, assuming that the other agents keep their policies fixed. That is, the blame assigned to agent i is equal to βi = ∆i. The following properties hold: Proposition 2. ΨMC(M,πb) = (∆1, ...,∆n) satisfies RS (symmetry), RI (invariance), RCM (contribution monotonicity) andRPerM (performance monotonicity).
Unlike max-efficient rationality, marginal contribution does not satisfy validity, i.e., it can over-blame a group of agents by assigning them total score that exceeds the improvement they can achieve, i.e., ∆. Given that an agent’s marginal inefficiency is not always a good indicator of the agent’s influence on the system’s performance, this method can be highly inefficient (distributing very little blame) when coordination among agents is required, as we show in Section 5.

heading: 3.3 Shapley Value and Banzhaf Index
text: In the context of the sequential decision making setting studied in this paper, Shapley value can be defined as β = ΨSV (M,πb) such that
βi = ∑
S⊆{1,...,n}\{i}
wS · [ J(π ∗|πb S∪{i}, π b −S∪{i})− J(π ∗|πb S , π b −S) ] , (1)
where coefficients wS are set to wS = |S|!(n−|S|−1)!
n! . We restate (and in the supplementary material, prove the claim for our setting) a well known uniqueness result for Shapley value: Theorem 1. [51] ΨSV (M,πb) = (β1, ..., βn), where βi is defined by Eq. (1) and wS = |S|!(n−|S|−1)! n! , is a unique blame attribution method satisfyingRE (efficiency),RS (symmetry) and RCM (contribution monotonicity). Additionally, ΨSV satisfiesRV (validity) andRI (invariance).
As we show in Section 5, Shapley value does not satisfy properties RR (rationality) nor RPerM (performance monotonicity).
Banzhaf index, denoted by ΨBI , is similar to Shapley value, and in fact, it has the same functional form but different coefficients (wS = 12n−1 ), leading to a slightly different uniqueness result. The supplementary material discusses Banzhaf index and its properties in greater detail. Here, we note that Banzhaf index is equivalent to Shapley value for two agents. However, in general, Banzhaf index does not satisfyRE (efficiency), but a version of it, called 2-efficiency [52]. As it is the case with Shapley value, Banzhaf index does not satisfy RPerM (performance monotonicity) nor RR (rationality). Interestingly,RV (validity) might also not hold (see Section 5).

heading: 3.4 Average Participation
text: Motivated by the fact thatRPerM (performance monotonicity) is important for incentivizing good performance and RE (efficiency) is important for explanatory power, we introduce a novel blame assignment method, which can be seen as a combination of marginal contribution and Shapley value. We first show the following result, which shows that there is an inherent trade-off betweenRPerM andRE , assumingRS (symmetry) andRI (invariance) hold. Proposition 3. No blame attribution method Ψ satisfiesRE (efficiency),RS (symmetry),RI (invariance) andRPerM (performance monotonicity).
Given this result, we instead consider two new propertiesRAE (average efficiency) andRcPerM (cperformance monotonicity), which are weaker variants ofRE (efficiency) andRPerM (performance
monotonicity) respectively. Importantly,RAE is not satisfied by ΨMC andRcPerM by ΨSV . In addition, we also consider two variants ofRCM (contribution monotonicity): RcParM (c-participation monotonicity) andRRcParM (relative c-participation monotonicity). To define the new properties, we introduce a contribution function c : M× Π × {1, ..., n} → {0, 1} that indicates whether an agent is pivotal, i.e., marginally contributes to the inefficiency of some subset of {1, ..., n}:
c(M,πb, i) =
{ 0 if J(π∗|π b
S∪{i}, π b −S∪{i}) = J(π ∗|πb S , π b −S) ∀S ⊆ {1, ..., n}
1 otherwise .
Alternatively, an agent i is pivotal if and only if its Shapley value is strictly greater than 0, i.e., c(M,πb, i) = 1 [βi > 0], where β = ΨSV (M,πb) and 1 [.] is an indicator function. The new properties are then defined as follows:
• Average efficiency (RAE): Ψ satisfies RAE (resp. -RAE) if for every M and πb, ∑n i=1 βi =∑
S⊆{1,...,n} 1 2n−1 ·∆S (resp. | ∑n i=1 βi − ∑ S⊆{1,...,n} 1 2n−1 ·∆S | ≤ ), where β = Ψ(M,π b). • c-Performance monotonicity (RcPerM ): Consider any MMDP M , and any πb−i, πi and π′i s.t. J(πi, πb−i) ≤ J(π′i, πb−i) and c(M, (πi, πb−i), j) = c(M, (π′i, πb−i), j) for every j. We say that Ψ satisfies RcPerM (resp. -RcPerM ) if βi ≥ β′i (resp. βi ≥ β′i − ) where β = Ψ(M, (πi, π b −i)) and β′ = Ψ(M, (π′i, π b −i)). • c-Participation monotonicity (RcParM ): Ψ satisfies RcParM (resp. -RcParM ) if for every (M1, πb 1 ) and (M2, πb2) s.t. c(M1, πb1, i) = c(M2, πb2, i) for every i, βj1 ≥ βj2 (resp. βj1 ≥
βj 2 − ) whenever ∆1S∪{j} ≥ ∆ 2 S∪{j} for all S, where β 1 = Ψ(M1, πb 1 ) and β2 = Ψ(M2, πb2). • Relative c-participation monotonicity (RRcParM ): Ψ satisfiesRRcParM (resp. -RRcParM ) if for every (M1, πb1) and (M2, πb2) s.t. c(M1, πb1, i) = c(M2, πb2, i) for every i, βj1 − βj2 ≥ βk 1 − βk2 (resp. βj1 − βj2 ≥ βk1 − βk2 − ) whenever c(M1, πb 1 , j) = c(M1, πb 1 , k) and
∆1S∪{j} −∆ 2 S∪{j} ≥ ∆ 1 S∪{k} −∆ 2 S∪{k} for all S ∈ {1, ..., n}\{j, k}, where β
1 = Ψ(M1, πb 1 )
and β2 = Ψ(M2, πb2).
Before describing the main results of this subsection, we briefly outline the intuition behind the above definitions. RAE (average efficiency) is similar to RE (efficiency), however it requires less total blame to be distributed. Whereas RE requires that the total blame is equal to the total inefficiency ∆, RAE requires that the total blame is equal to the average marginal inefficiency of subsets of agents, i.e., the average value of ∆S .6 Compared toRPerM (performance monotonicity), RcPerM (c-performance monotonicity) additionally accounts for the pivotality of agents through contribution function c, treating each set of pivotal agents as a separate case. RcParM (c-participation monotonicity) accounts for agents’ pivotality in a similar manner. Moreover, RcParM resembles contribution monotonicity RCM , but instead of requiring blame monotonicity to hold w.r.t. the agent’s influence on the marginal inefficiency of subsets S (i.e., ∆S∪{i} −∆S), it considers blame monotonicity w.r.t. the marginal inefficiency of subsets that contain the agent (i.e., ∆S∪{j}). Relative c-participation monotonicityRRcParM is similar toRcParM , but its blame monotonicity requirement is based on a pairwise comparison of agents with the same pivotality degree. In particular,RRcParM requires that the blame increase is higher for an agent who is in subsets with a greater marginal inefficiency increase (i.e., βj1−βj2 ≥ βk1−βk2 whenever ∆1S∪{j}−∆ 2 S∪{j} ≥ ∆ 1 S∪{k}−∆ 2 S∪{k}).
Average participation: Now, we describe the new blame assignment method, which we call average participation. This blame assignment method can be defined as β = ΨAP (M,πb) such that
βi = ∑
S⊆{1,...,n}\{i}
w · c(M,π b, i)∑
j∈S c(M,π b, j) + 1
·∆S∪{i}, (2)
where coefficient w is set to w = 12n−1 . Intuitively, ΨAP equally distributes blame for the marginal inefficiency of a subset of agents among the pivotal agents in that subset. Hence, an agent i that is pivotal receives blame for each subset S ∪ {i} equal to ∆S∪{i} divided by the number of pivotal agents in S ∪ {i} and scaled by coefficient w. Agents that are not pivotal, obtain 0 blame. Average participation uniquely satisfies the following properties.
6This average does not include ∆∅, which is equal to 0. Note also that ∆ ≥ ∆S for every S ⊆ {1, ..., n}, so this average is upper bounded by ∆.
Theorem 2. ΨAP (M,πb) = (β1, ..., βn), where βi is defined by Eq. (2) and w = 12n−1 , is a unique blame attribution method that satisfiesRAE (average-efficiency),RS (symmetry),RI (invariance),RcParM (c-participation monotonicity) andRRcParM (relative c-participation monotonicity). Furthermore, ΨAP satisfiesRcPerM (c-performance monotonicity) andRV (validity).
Unlike marginal contribution, average participation is valid (never over-blames agents), however it satisfies a weaker version of performance monotonicity. Still, this version is not satisfied by Shapley value. On the other hand, Shapley value is efficient, unlike average participation, which satisfies a weaker requirement—average efficiency. We also showcase these trade-offs in Section 5.

heading: 4 Blame Attribution under Uncertainty
text: In this section, we study blame attribution methods that do not have direct access to πb. As mentioned in Section 2, we focus on the case where the knowledge about πb is defined by the uncertainty set P(πb), and it is defined state-wise so that each state is associated with a set of probability measures on A identifying plausible candidates for πb(·|s).7 We denote π ∈ P(πb) if π is plausible by P(πb).

heading: 4.1 Shapley Value under Uncertainty
text: In explaining approaches to handling uncertainty, we focus on Shapley value. Arguably, the simplest way to operate under uncertainty is to derive a point estimate of πb, denoted by π̂b,8 and apply ΨSV on this estimate to obtain blame assignment β̂ = ΨSV (M, π̂b). Albeit being simple, this approach does not satisfy desirable properties, most notably,RV (validity) andRBC (Blackstone consistency).
Validity. Now, note that β̂ = ΨSV (M, π̂b) satisfies ∑n i=1 β̂i = J(π
∗)− J(π̂b). Therefore, instead of relying on a point estimate π̂b, we could utilize a policy π̂b for which J(π∗)−J(π̂b) ≤ ∆. Namely, in that case β̂ = ΨSV (M, π̂b) results in a blame assignment that satisfiesRV (validity). Since this inequality holds for a solution to the optimization problem maxπ∈P(πb) J(π), we obtain:
Proposition 4. Let π̂b be a solution to the optimization problem maxπ∈P(πb) J(π). Then Ψ̂SV,V (M,P(πb)) = ΨSV (M, π̂b) satisfiesRV (validity).
Blackstone consistency. As we show in Section 5, although Ψ̂SV,V is valid, it might not be Blackstone consistent w.r.t. ΨSV . In particular, although the total blame is never overestimated, an agent i might receive higher blame than it would receive under ΨSV . To ensure Blackstone consistency, we can assign blame to agent i equal to minπ∈P(πb) βi
π s.t. βπ = ΨSV (M,π). Together with Eq. (1), this implies that agent i’s blame is obtained by solving
min π∈P(πb) ∑ S⊆{1,...,n}\{i} wS · [ J(π ∗|π S∪{i}, π−S∪{i})− J(π ∗|π S , π−S) ] , (P2)
where wS = |S|!(n−|S|−1)! n! and π ∗|π S ∈ arg maxπ′S J(π ′ S , π−S). We have the following result:
Proposition 5. Let βii be the minimum value of the objective in (P2). Then Ψ̂SV,BC(M,P(πb)) = (β11 , ..., β n n) satisfiesRV (validity) andRBC(ΨSV ) (Blackstone consistency w.r.t. ΨSV (M,πb)).
Note that Ψ̂SV,BC distributes less total blame than Ψ̂SV,V , since it takes the worst case perspective for each agent separately, while under Ψ̂SV,V the blame assigned to all agents is computed with the same joint behavior policy. Moreover, the objective function in (P2) is more complex than in classical robust MDP settings [47, 48], making classical approaches for robust MDPs hard to apply. In practice, we can relax (P2) and optimize a lower bound of the objective; this preserves RBC(ΨSV ), but at the expense of distributing less blame to the agents. In our experiments, we solve minπ∈P′(πb) J(π ∗|π S∪{i}, π−S∪{i}) and maxπ∈P′(πb) J(π ∗|π S , π−S) for each subset S and with appropriately chosen P ′(πb) ⊇ P(πb) (see the supplementary material), and we apply Eq. (1) to 7Such definition implies a rectangularity of the uncertainty set [47, 49]. 8For example, this estimate can be derived from data containing the agents’ trajectories.
obtain the blame assignment. This implies that agent i’s blame is obtained by solving∑ S⊆{1,...,n}\{i} wS · [ min π∈P′(πb) J(π ∗|π S∪{i}, π−S∪{i})− max π∈P′(πb) J(π ∗|π S , π−S) ] .
Other Blame Attribution Methods. Similar approaches also work for other blame assignment methods discussed in Section 3. For example, and focusing on Blackstone consistency, Ψ̂BI,BC(M,P(πb)) can be obtained in the same way as Ψ̂SV,BC(M,P(πb)), but with wS =
1 2n−1 , while Ψ̂MC,BC(M,P(π b)) can be implemented as Ψ̂MC,BC(M,P(πb)) = (∆̃1, ..., ∆̃n) where ∆̃i = minπ∈P′(πb) J(π ∗|π i , π−i)−maxπ∈P′(πb) J(π). Implementing Blackstone consistent Ψ̂MER,BC(M,P(πb)) and Ψ̂AP,BC(M,P(πb)) is more nuanced, and we discuss it in the supplementary material.

heading: 4.2 Characterization Result
text: Notice that the described Blackstone consistent methods Ψ̂(M,P(πb)) are not guaranteed to satisfy the properties that their counterparts Ψ(M,πb) satisfy. However, as long as Ψ̂(M,P(πb)) and Ψ(M,πb) output similar enough blame assignments, properties that hold under Ψ(M,πb) will approximately hold under Ψ̂(M,P(πb)). More formally, we have the following results.
Theorem 3. Consider Ψ̂ and Ψ s.t. ∥∥∥Ψ̂(M,P(πb))−Ψ(M,πb)∥∥∥
1 ≤ for any M , πb, and P(πb).
Then if Ψ satisfies a propertyR ∈ {RV ,RE ,RR,RS ,RI ,RAE}, Ψ̂ satisfies -R. Moreover, if Ψ satisfies a propertyR ∈ {RCM ,RPerM ,RcPerM ,RcParM ,RRcParM}, Ψ̂ satisfies 2 -R.
This theorem allows us to quantify the robustness of the blame attribution methods—the closer Ψ̂ is to Ψ, the more robust it is to uncertainty. Interestingly, a trivial blame attribution method that assigns 0 blame to all the agents is robust in this sense. However, as we already mentioned, this trivial blame assignment is not informative as it does not attribute any blame. In fact, if agents receive no penalties for bad behavior, such a blame attribution method might have adverse effects. We provide a broader discussion on the negative side-effects of under-blaming in the supplementary material. Importantly, this example suggests that efficiency (in a broad sense, i.e., how much blame is being distributed) and robustness are sometimes at odds, which we also demonstrate in the experiments.

heading: 5 Experiments
text: To demonstrate the efficacy of the studied blame attribution methods, we consider two environments, Gridworld and Graph, depicted in Fig. 1 and Fig. 2. Both environments are adapted from [53] and modified to be multi-agent. The experiments evaluate blame attribution methods along three axis:
• Performance monotonicity: First, we test blame attribution methods for theRPerM (performance monotonicity) property, which we deem important for accountability. To do that, we consider the gridworld environment: this is a two-agent environment in which one of the agents, A2, optimizes its policy using a model of the other agent, A1. Importantly, by controlling the correctness of A2’s model of A1, we can validate whether a blame attribution method satisfiesRPerM . Namely, if A2 does not receive the minimum blame when its model of A1 is the correct model, the corresponding method is not performance incentivizing, i.e., it does not satisfyRPerM . • Coordination: Second, we evaluate the efficacy of blame attribution methods when a higher degree of coordination among agents is needed to yield improvements over the baseline behavior. For this, we consider the graph environment, which includes configurations where an agent cannot improve the joint performance by unilaterally changing its policy. Thus, this environment is suitable for evaluating whether blame attribution methods incorporate more nuanced counterfactual reasoning.
• Robustness: Finally, we evaluate the robustness of blame attribution methods under uncertainty. In this case, both environments (Gridworld and Graph) are used for testing purposes, and we control for the level of uncertainty over the agents’ behavior policies.
The supplementary material provides more details on the experimental setup and implementation. Below we provide a more detailed description of the considered environments and discuss our findings.
Environment 1: This is a gridworld environment, in which two agents control the same actor but with different priorities. In the single-agent version of the environment, an agent, agent A1, controls the movement of the actor. In our multi-agent version, there is an additional agent, agent A2, who can intervene and override A1’s actions. The two agents select their actions simultaneously. Cells denoted with S are the initial states, blank cells indicate areas of small negative reward, F cells indicate areas of slightly increased cost and H cells are areas of severe penalty. The cell denoted by G is the terminal state of the environment and has a positive
reward. When agent A2 intervenes in some state, the actor takes the action that an optimal policy would select in the single-agent mode, but also pays a cost of
S S S S S F S S H S H S S S F H H H H S S H H F H F S S F F F H H G
Fig. 1. Gridworld
intervention C. The behavior policy πb1 of agent A1 is parameterized by variable α, which specifies the probability that A1 takes an action determined by an optimal single-agent policy, instead of its personal policy. The personal policy of A1 is a mixture of an optimal single-agent policy for correctly specified costs and a single-agent policy that is optimal but for misspecified costs of F andH cells—it assumes that they have the same cost as the blank cells. A2’s behavior policy πb2 optimizes the expected discounted return and is trained with a model of A1 specified by the true personal policy of A1 and variable α′ (not necessarily equal to α). A2 is meant to rectify potential mistakes of A1 that could inflict cost greater than C. InRPerM experiments we set α = 0.4. In robustness experiments, we only consider uncertainty over the personal policy of A1, and we set α = 0.2 and α′ = 0.5.
Performance monotonicity: Fig. 3a validates our theoretical results regardingRPerM (performance monotonicity). More specifically, methods ΨAP and ΨMC assign the minimum blame to A2 when it acts optimally w.r.t. the true policy ofA1 , i.e., when α′ = α. However, this is not the case for methods ΨSV and ΨBI , which implies that these methods are not incentivizing A2 to act optimally w.r.t. its belief about A1. ΨMER and ΨBI assign the same blame to A2 as ΨMC and ΨSV , respectively.
Environment 2: This is a graph environment in which 4 agents simultaneously select actions. The graph consists of one starting and one terminal node, as well as 8 intermediate nodes that can be grouped according to their index number; nodes with even index number are located on the upper level of the graph and nodes with odd index number on the lower level. At each time-step every agent -1
chooses to take either action 0 and move to the upper level or action 1 and move to the lower level. We test multiple variants of this environment, each of which defines a different reward function. In all variants, the reward at each time-step is +1 if some formation constraint is satisfied and −1 if not. In the first set of experiments (Coordination), we consider 4 different formation constraints: in formation constraint m ∈ {1, ..., 4}, at least m agents need to select action 1 for the constraint to be satisfied. Each behavior policy πbi takes action ai = 0 in every node. In the second set of experiments (Robustness), we consider one formation constraint that is satisfied if the agents are arranged equally between the two levels. In states where agents are balanced between the levels, each behavior policy πbi takes the action from the previous time-step with probability pi; in unbalanced states, the action that leads to the level with the least number of agents is taken with probability pi.
Coordination: Fig. 3e shows how much blame in total the blame attribution methods assign for the four different levels of required coordination (m = 1, ..., 4). Observe, that when the constraint can be satisfied by every agent (m = 1), ΨMC violatesRV (validity). For m = 2, ΨMER and ΨMC assign zero blame to all agents, while ΨBI violates RV (validity). Although always valid, ΨAP assigns significantly less blame as m increases. ΨSV is always efficient, and its total blame does not vary with m. ΨSV , ΨBI , ΨMC and ΨAP do not satisfyRR (they assign more total blame than ΨMER). Robustness: We test the robustness of the blame attribution methods by controlling the amount of uncertainty in the estimates of the agents’ behavior policies. To model uncertainty, we consider maximum estimation error max, and to obtain uncertainty sets P(πb), we sample (uniformly at random) π̂bi (s) such that 1 2
∥∥π̂bi (s)− πbi(s)∥∥1 ≤ max. Moreover, P(πb, s) contains all policies π such that 12
∥∥π̂bi (s)− πi(s)∥∥1 ≤ max. In our experiments, we take π̂b to be the point estimate of πb. Comparing estimation approaches: Fig. 3b and 3f show how the approaches for estimating Ψ̂SV from Section 4 fare under different levels of uncertainty. The point estimate approach typically over-blames an agent and the amount of over-blaming increases with the level of uncertainty. Ψ̂SV,BC never over-blames any agent, but it becomes less efficient (in distributing blame) as max increases (Fig. 3f). Ψ̂SV,V is more efficient than Ψ̂SV,BC , but violatesRBC (Blackstone consistency) (Fig. 3b).
Comparing attribution approaches: Fig. 3c and 3g show for each consistent blame attribution method Ψ̂ from Section 4 the L1 distance between its output and the output of its counterpart Ψ (“targeted assignment”). Fig. 3d and 3h show the total blame assigned by these methods. Ψ̂AP,BC consistently outperforms the other methods in terms of the L1 distance from its “targeted assignment”. Compared to Ψ̂AP,BC , Ψ̂SV,BC is consistently better in terms of efficiency (in distributing blame). Similar, albeit less prominent effects can be seen when comparing Ψ̂AP,BC and Ψ̂BI,BC . These results indicate a tendency where efficiency (in distributing blame) and robustness are at odds, as we also discuss in Section 4.2. Ψ̂MER,BC and Ψ̂MC,BC assign zero total blame even for smaller max, indicating that they are the least robust to uncertainty.

heading: 6 Conclusion
text: In summary, the focus of our work is to provide an overview of possible computational approaches for attributing blame in multi-agent sequential decision making. We discuss the strengths and weaknesses of different methods in order to guide practitioners and policy makers in designing tools that support accountability. We conclude that there is no single best choice for blame attribution methods, since there are inherent trade-offs among properties that one might consider important. Looking forward, we recognize several research directions that could address the limitations of our results, some of which we highlight here. a) In this work we primarily focused on the agents’ joint return as the outcome of interest. However, it is often important to pinpoint actual causes that led to more fine grained outcomes. Utilizing a causal perspective would be beneficial in this regard and could link our results to prior work (e.g., [16]). b) We considered model-based approaches to blame assignment. Learning blame attribution directly from data (e.g., with model-free counterfactual RL) might be more practical in settings where an approximate model is hard to obtain. c) More generally, ensuring scalability both in the number of agents and the the richness of environments is one of the most important steps for making this work more widely applicable. We deem approaches from multiagent RL as suitable candidate solutions for resolving this problem. d) We primarily studied blame assignment properties that are taken from or closely relate to those from the game theory literature. This list could be extended and include more principles from moral philosophy and law. For example, in this paper, we adopted a consequentialist approach to blame attribution, focusing on the outcomes of the agents’ behavior. Alternatively, one could take a deontological perspective, and focus on the alignment of an agent’s behavior with a set of rules. We further discuss different perspectives on blame attribution in the supplementary material. Finally, we would like to draw particular attention to the fact that there is no universal prioritization of properties that applies to all blame attribution problems and hence treating any generic analysis like ours as panacea without further justification, might have a negative impact to the agents that are being blamed. To that end, we would like to emphasize that we see this work not as a final solution to the blame attribution problem, but as a starting point that shows challenges and trade-offs in distributing blame.

Review summaries:
In the context of MMDPs, this work presents an overview of blame attribution methods from the game theoretic literature, together with a study of desirable properties. It then contributes a novel blame attribution method to mitigate some of the identified issues. All the methods are compared in an empirical study and analysed in terms of robustness in the face of uncertainty.