A Game-Theoretic Account of Responsibility Allocation

1 Introduction

The notion of responsibility is fundamental in the study of multi-agent interaction. Allocation of responsibility is a means by which we regulate interactions in society, by declaring whether an action by a person in an interactive setting should be praised or blamed. In multi-agent interactions, ascertaining who is to be held responsible and by which degree can be difficult; thus, there is a need for formal frameworks for responsibility allocation.

We work in the framework of "folk ethics" conception of moral responsibility [Braham and van Hees, 2012; Braham and van Hees, 2018]. In this setting, the locus of responsibility resides with the individual rather than a collective and purely on her actions and their consequences rather than identities, attitudes, norms, or values. A person is ascribed responsibility for a given outcome if three conditions are met. First, the person has agency: they are able to plan and act intentionally and can distinguish the setting of the interaction and outcomes. The second is causal relevance: there is a causal link between the actions and the outcome-to be elaborated below. The third is the possibility to act otherwise: We use our evaluation of actual and potential actions and its consequences on the outcome. However, our approach is descriptive in the sense that we do not analyze normative aspects such as values, virtues, intent, or morality underlying the actions of the agents [Scanlon, 1998].

In this paper, we provide a game-theoretic account of responsibility allocation in a multi-agent interaction setting. We model multi-agent interaction as a game of imperfect information in extensive form [Kuhn, 1953; Owen, 1995] between n individually rational players. Players are assumed to be rational in a weak sense: they are aware of the game, the other players, their own actions, and the outcome. In particular, we shall assume agency. We study both forward and backward notions of responsibility [van de Poel, 2011]. A forward notion looks at the game as a whole and ascribes responsibilities to players based on all potential plays. A backward notion looks at a play and ascribes responsibility to each player for that play. We approach responsibility allocation to individual agents in two steps. First, we look at coalitions of players and define notions of forward and backward responsibilities for a coalition. Second, we define a value function from coalitions to their responsibilities, and define the individual allocation as a power index of this value function [Owen, 1995].

For the first step, we distinguish between causal and strategic backward responsibility, which correspond to the responsiblity-as-cause and responsibility-as-capacity notions of [van de Poel, 2011]. Intuitively, a coalition is causally backward responsible for an outcome along a play if there is a different strategy the coalition could have adopted that would have avoided the outcome, against the same strategy of the other players. Strategic backward responsibility strengthens the requirement: the coalition should be aware, given their epistemic state, of this ability to affect the outcome. Our key technical result is a relationship between forward and strategic backward responsibility: in a game of perfect recall, a coalition is forward responsible for an outcome iff it contains a strategically backward responsible coalition for every play with the outcome, and is minimal with respect to this property (Theorem 1). Moreover, we show that all forms of responsibility of a coalition can be checked in polynomial time (Theorem 2).

For the second step, our approach follows [von Neumann, 1928], and relies on a transition from non-cooperative games to cooperative values. While there are different measures of value in a cooperative game, we pick the Shapley value [Shapley, 1953] for its familiarity and its canonicity. Thus, we ascribe quantitative measures of responsibility in order to compare the relative responsibility of agents for an outcome. As a motivation we show that our modeling choices allow us to precisely talk about various aspects of many well-known scenarios from the moral philosophy and causality literature.

The condition for causal dependence is often tested in a framework of actual causality [Halpern and Pearl, 2005; Halpern, 2015] (henceforth HP, after its proponents) or the NESS test [Hart and Honor´e, 1959]. HP provides a formal model for causal contribution to an outcome and models institutional rules as structural equations. We believe that structural equations are too weak to naturally model several situations of interest, such as agency, knowledge, or temporal sequentiality. Consider the prototypical example in which Suzy and Billy both throw stones at a bottle. Suzy's stone hits first and the bottle breaks [Halpern, 2016]. Who should be responsible? The description of the problem or the structural equations do not clarify if either Suzy or Billy knew if the other threw a rock, or if Billy's strategy to throw was conditional, knowing that Suzy had indeed thrown already. These nuances are easily modeled in our setting due to the additional modeling power of extensive form games.

In a technical sense, we can embed structural equations into our framework, and our causal backward responsibility is exactly the but-for condition in causal reasoning (Theorem 3). HP's actual causality goes beyond but-for-causes: in the above example, HP considers Suzy to be responsible - but not Billy - by interposing a counterfactual world in which Suzy does not throw, Billy does throw, but still Billy's stone does not hit the bottle (where we use Halpern's modified version [Halpern, 2015]). We find this problematic: the intervention (Billy's stone not hitting the bottle) is not an agent to whom we can ascribe agency. Because of the symmetry of the players, and our insistence on comparing strategies with other agent strategies, we hold both equally responsible. We believe HP's allocation of backward responsibility solely to Suzy is not uncontroversial: replace Suzy and Billy with two assassins who simultaneously (and without knowledge of the other) shoot a person. Even if the laws of physics decide which bullet reaches first, in moral or legal considerations, we would hold both assassins responsible. A second advantage of games over structural equations is that responsibility of a coalition can be computed in polynomial time; thus, checking if an individual is responsible is in NP, as opposed to the harder class DP for HP.

Full proofs can be found in the technical report [Baier et al., 2021].

Other RelatedWork. Close to our work, [Braham and van Hees, 2012] give an account of moral responsibility as normal form games with pure strategies (the model is one-shot, perfect-information). Models of (qualitative and quantitative) responsibility have been studied for non-probabilistic Kripke structures with games of possibly infinite duration

(see, e.g., [Chockler et al., 2008; Beer et al., 2009; Bulling and Dastani, 2013; Yazdanpanah and Dastani, 2016]). Quantitative measures of influence in causal models [Chockler and Halpern, 2004] have generated a fruitful strand in the causality literature [Aleksandrowicz et al., 2014; Chockler, 2016; Friedenberg and Halpern, 2019]. A detailed comparison with other accounts of responsibility is the content of Section 5. Shapley-like values have been used to allocate responsibility [Friedenberg and Halpern, 2019; Yazdanpanah et al., 2019], and recently been rediscovered for the explanation of machine learning models [ˇStrumbelj and Kononenko, 2014; Lundberg and Lee, 2017].

2 Preliminaries

In this section we recall some basic definitions from noncooperative game theory (see, e.g., [Owen, 1995]). We rely on von Neumann's framework of extensive form games [von Neumann, 1928] with the only exception that leaves are not labeled with payoff vectors, but a binary variable E or ¬E indicating whether a certain event has occured or not.

Definition 1 (Extensive form game). A finite n-player game G in extensive form consists of the following data:

1. a finite directed tree T , called the game tree, whose vertices are called the states of G;
2. a partition of the non-terminal states of T into sets P0, P1, ..., Pn;
3. for s ∈ Pi a finite set of actions Act(s) that is in bijection with the successors of s;
4. for s ∈ P0 a probability distribution p(s) over Act(s);
5. a partition Pi = ˙⋃I∈Ii I into information sets such that Act(s) = Act(s′ ) for all s, s′ in the same information set I, and p(s) = p(s′ ) if additionally s, s′ ∈ P0;
6. for each leaf s of T a labeling l(s) ∈ {E, ¬E}.

Intuitively, the game is played as follows. One starts at the root s0 of T . If the current state s belongs to P0, then the next state is chosen by a random player called Nature according to p(s). If the current state s belongs to Pi, then player i chooses a successor state by choosing an action from Act(s). The intended meaning of the information set I is that player i cannot distinguish the states in I and must choose an action independent of the specific state in I. A play in G is a path from the root to a terminal state, and the set of plays is denoted by Plays(G). The plays that run through state s or information set I are denoted by Playss(G) and PlaysI(G). A play ending in a state with label E is called an E-play.

Throughout, we will restrict our attention to games of perfect recall, in which, intuitively, no player forgets his own history of actions. This is a reasonable assumption in many real-world scenarios, especially those of short duration. It also captures the intuition in a setting of responsibility that an agent should have known information available. For a state s let histG(s) = I0a0I1a1...ak-1Ik be the sequence of information sets visited and actions taken on the path from the root of T to s. Given C ⊆ {1, ..., n} let histG(s,C) be the subsequence obtained from histG(s) by removing each Ij and action aj that is not under control of a player in C.

Definition 2 (Perfect recall). A game G has perfect recall if for each player i and any two states s, s′ in the same information set of player i we have histG(s, {i}) = histG(s′ , {i}).

In the presence of uncertainty that comes with nonsingleton information sets, players may prefer to act randomly instead of deterministically. We will be allowing behavioral strategies throughout [Kuhn, 1953].

Definition 3 (Strategies). A (behavioral) strategy for player i is an element σi = {σI}I∈Ii ∈ ∏I∈Ii Dist(Act(I)). It is pure if each σI is a Dirac distribution. A strategy profile is a set {σi}ni=1 , where each σi is a strategy for player i.

A play ρ is consistent with a strategy profile σ = {σi} if for every information set I on ρ the chosen action has positive probability in σI. Taking only consistent plays induces subsets Playsσs (G) ⊆ Playss(G) and PlaysσI (G) ⊆ PlaysI (G).

3 Responsibility in Non-cooperative Games

We now identify three qualitative notions of responsibility which we present in decreasing order of their logical strength.

3.1 Forward Responsibility

The individual responsibility of player i will be an average of the marginal contribution of i to coalitional responsibility, i.e., the responsibility of a group of players C. We first formalize that the players in C act collaboratively.

Definition 4 (Game induced by a coalition). Let G be an nplayer game and C ⊆ {1, ..., n}. The 2-player game GC is obtained from G as follows: The two players C and C are in control of the states in PC = ⋃i∈C Pi and PC = ⋃i∈{1,...,n}\C Pi. Two states s, s′ ∈ PC belong to the same information set in GC if and only if they belong to the same information set in G and histG(s, C) = histG(s′ , C). Similarly for C. The labeling of terminal states remains unchanged, as do the states and distributions in control of player Nature.

The information sets are the coarsest refinement of the existing information sets such that GC is a game of perfect recall. The rationale for this is that the coalition C will share knowledge among its members; states that are indistinguishable by one player in C can become distinguishable by C because another player in the coalition can tell them apart.

Example 1 (Matching pennies). Two players independently choose heads or tails, and E is the event that they made opposite choices. This game is depicted in Figure 1, where the notation s : i expresses that state s is in control of player i, dashed lines connect states in the same information set, and the red leaves indicate E-plays. If we did not refine the information sets in GC, C = {1, 2} could not distinguish s1 and s2 even though a coalition member chose the action that produces the branches to these states. Thus enforcing perfect recall in GC is necessary to model epistemic knowledge in the coalitional setting.

Definition 5 (Forward responsibility). Let G be an n-player game. We say that C ⊆ {1, ..., n} is forward responsible (henceforth f-responsible) for E if (F) there is a strategy σ of the player C in GC such that all plays in Playsσ (GC) have label ¬E, and C is minimal with respect to property (F).

Being f -responsible means that C wins the game GC under the reachability objective ¬E, and this condition is not satisfied for any proper subset of C. In order to illustrate Definition 5 and the subsequent notions of responsibility, we use the following toy scenario as running example. More interesting cases are postponed to the collection gathered in Section 4.

Example 2. Player 1 first decides between mode A and mode B. In mode A, players 2 and 3 independently choose a side of a coin as in Figure 1. In mode B, Nature tosses a coin, the result is revealed, and then player 3 chooses a side. The variable E denotes the event where the two sides of coins are not the same. See Figure 2 for a visualization of this game.

No single player is f -responsible. This is obvious for players 1 and 2, and for player 3 this is due to the non-trivial information set {s3, s4}: the strategy that enforces ¬E in one of the states prevents it in the other. The coalition {1, 3} is f - responsible since player 1 can choose to move into mode B, and player 3 responds according to what is revealed to him by Nature. Likewise {2, 3} is f -responsible.

3.2 Strategic Backward Responsibility

In contrast to the preceeding section, backward responsibility is defined relative to a given play ρ ending in E. We distinguish between strategic backward responsibility and causal backward responsibility. Informally speaking, strategic backward responsibility means that C had the power to prevent E as the play ρ evolved given its epistemic knowledge:

Definition 6 (Strategic backward responsibility). The set C is strategically backward responsible (henceforth s-responsible) for E based on an E-play ρ if (S) there exist a state s on ρ and a strategy σ of the player C in GC such that:

1. ρ is consistent with σ until s is reached, and
2. all plays in PlaysσI (GC) have label ¬E, where I is the information set of s,

and C is minimal with respect to property (S).

Clearly, each f -responsible coalition, or even any coalition C satisfying property (F) contains an s-responsible coalition based on any E-play. In order to show property (S) for C one can simply take s to be the initial state and take the strategy for C that globally enforces ¬E.

Example 3. Consider again our running example depicted in Figure 2. First let ρ be one of the two E-plays ending in s8 and s9. No single player is s-responsible for E based on one of these plays. However, the coalitions {1, 3} and {2, 3} are s-responsible for E based on ρ since they are f-responsible. Based on the two E-plays ending in s12 and s13, the single player 3 is strategically backwards responsible for E since he could have chosen differently in s5, respectively, s6.

Theorem 1 (Relating forward and backward responsibility). In a game of perfect recall, a coalition C ⊆ {1, ..., n} is fresponsible for E if and only if it contains an s-responsible coalition for E based on all E-plays, and is minimal with respect to this property.

Remark 1. Theorem 1 would not hold without the refinement of information sets in GC illustrated in Example 1.

3.3 Causal Backward Responsibility

A set of players might have caused E unknowingly and even inadvertently. For example, in the simple 2-player matching pennies scenario depicted in Figure 1, imagine that player 1 picks heads and player 2 picks tails. Both players may be held responsible for the result since changing their individual actions would have prevented it. However, they were simply not aware of this fact. The lack of knowledge that renders a strategic sense of responsibility implausible in this scenario refers to the uncertainty of the opponent's strategy (which also entails the uncertainty that comes with non-singleton information sets). Causal backward responsibility leverages this lack of knowledge by fixing a strategy profile for the opposing coalition. Intuitively, the coalition C guesses the strategy of C and thus attains the hypothetical knowledge to anticipate the actions of C.

Definition 7 (Causal backward responsibility). Let σ be a strategy profile in G such that Playsσ (G) contains an Epath ρ. Let (σC, σC ) be the strategy profile induced by σ in GC. Then C ⊆ {1, ..., n} is causally backward responsible (henceforth c-responsible) for E based on ρ and σ if (C) there exists a strategy σ′C for C in GC such that all plays in Playsσ′C ,σC (GC) that are also consistent with Nature's random choices on ρ have label ¬E, and C is minimal with respect to property (C).

Intuitively, C satisfies condition (C) if C's actions made a difference to the outcome when everything else is held fixed: The E-path ρ consistent with the strategy profile contains a state from which the coalition C could have employed a different strategy that enforces reaching ¬E provided that C's guess on the opponent's strategy was right. Fixing strategies might seem like a far-fetched setup. We illustrate in Section 4 that many scenarios naturally determine a strategy profile, and we show in Section 5 that this canonically corresponds to fixing a context for a causal model.

Example 4. Consider once more the scenario depicted in Figure 2. In the following denote the Dirac distribution over Act(s) concentrated on a by s ↦→ a. Based on the strategy profile σ1 given by s0 ↦→ B, s1 ↦→ h2, {s3, s4} ↦→ h3, s5 ↦→ t3, s6 ↦→ t3 and the play ending in s12, players 1 and 3 are c-responsible for E; player 1 can prevent E by switching to A since players 2 and 3 make identical choices in mode A, and player 3 can prevent E by choosing heads in s5. The reader is invited to check that every single player is c-responsible for E based on the strategy profile σ2 given by s0 ↦→ A, s1 ↦→ h2, {s3, s4} ↦→ t3, s5 ↦→ h3, s6 ↦→ t3.

The example illustrates that c-responsibility is an approach to identify 'causes' for E irrespective of epistemic information available to the players. A comparison to Halpern and Pearl's actual causes is given in Section 5.

Proposition 1 (From strategic responsibility to causal responsibility). Let σ be a strategy profile and let ρ ∈ Playsσ (G) be an E-play. If C is s-responsible for E based on ρ, then C contains a c-responsible coalition for E based on ρ and σ.

3.4 Quantifying Responsibility

All responsibility notions considered so far are qualitative. We now take the analysis one step further and quantify how much responsibility each individual player has. For this we employ the Shapley value for cooperative games [Shapley, 1953], i.e., games defined by a function g : 2n → R, where g(C) represents the common gain (or cost, depending on the situation) which coalition C can achieve collaboratively.

The responsibility notions {f, s, c} (i.e., forward, strategically backward, causally backward) in an extensive form game naturally induce cooperative games. Let t ∈ {f , s, c}; if t = s we assume that an E-play ρ is fixed, and if t = c, we further assume that a strategy profile σ is fixed (which we suppress from the notation for readability). We define the induced cooperative game gG,t : 2n → R by setting gG,t(C) to be 1 if C contains a t-responsible coalition for E (based on ρ, resp. σ) and to be 0 otherwise.

Definition 8 (Responsibility value). The responsibility value respG,t(i) of player i in an n-player extensive form game G is the Shapley value of i in the induced cooperative game gG,t, i.e.,

where Sn denotes the set of permutations on {1, ..., n} and π≥i = {j ∈ {1, ...n} | π(j) ≥ π(i)}.

We have respG,t(i) > 0 if and only if player i belongs to a t-responsible coalition, i.e., if i leaves the coalition, then it is not t-responsible anymore. Moreover, we have ∑i respG,t(i) = respG,t({1, ..., n})-respG,t(∅) by a simple telescope sum argument, and this value is 1 unless C = ∅ is t-responsible or C = {1, . . . , n} is not t-responsible. Apart from these latter exceptional cases, the responsibility value measures the relative responsibility of each player against the other players within a given game. It is not intended to be compared across different types of responsibility, across plays, or even models.

The exceptional cases above are the only instances in which our theory allows responsibility voids [Braham and van Hees, 2018], i.e., respG,t(i) = 0 for every player i. This is not unintended: If C = ∅ is t-responsible, then all plays must have label ¬E, meaning that (as far as the event E is concerned) the actions of the agents are irrelevant. If C = {1, . . . , n} is not t-responsible, then ensuring ¬E is impossible, and if the game does not involve randomization, this means that no play has label ¬E. We present a scenario involving responsibility voids in Example 8.

Example 5. In our running example of Figure 2 we have respG,f (1) = respG,f (2) = 1/6 and respG,f (3) = 2/3. Based on a play ending in s8 or s9, the same value arise for respG,s(i). If ρ ends in s12 or s13, then respG,s(3) = 1 and respG,s(i) = 0 for i = 1, 2. Based on the strategy profile σ2 of Example 4 we have respG,c(i) = 1/3 for every player.

3.5 Computational Complexity

Remarkably, the complexity of deciding responsibility for a coalition is polynomial time. Our algorithm is based on the polynomial time procedure for solving two-player zero-sum games [Koller and Megiddo, 1992; von Stengel, 1996].

Theorem 2 (Complexity of deciding responsibility). Given an n-player game, a coalition C ⊆ {1, ..., n}, and t ∈ {f, s, c}. If t = s we assume that an E-path ρ is fixed, and if t = c, we further assume that a strategy profile σ is fixed. It is decidable in polynomial time whether C is t-responsible for E (based on ρ, resp., σ).

A straightforward consequence of Theorem 2 is that deciding whether respG,t(i) > 0 belongs to NP, and computing respG,t(i) belongs to #P.

4 Examples

We now illustrate our notion of responsibility allocation on several examples in the moral philosophy literature.

Example 6 (Bystanders). Consider a car accident with three victims in immediate need of first aid. There are four bystanders 1, 2, 3, 4 who arrive in this order and who can help one of the victims (we implicitly assume that if one victim is already being helped, and another bystander decides to help, then she helps an unassisted victim). Let E be the event where at least one victim dies. Then a coalition is fresponsible if it contains exactly three players, and we get respG,f (i) = 1/4, which just means that they have globally the same power. Consider the play where bystanders 1 and 3 help and the others do not help. Then the only s-responsible coalition is {4}. Hence respG,s(4) = 1, which is a numerical interpretation of the fact that 4 knows that she can (or must) make the difference for the remaining victim to survive, while player 2 does not have this certainty.

Next consider the scenario in which 1 helps, but the others do not help irrespective of any previous actions. Then respG,c(1) = 0, respG,c(i) = 1/3 for i = 2, 3, 4, which explains that the remaining bystanders are equally responsible for the death of the victims. Finally imagine that bystander 4 would have helped if bystander 3 had helped (the bystander effect), but 2 and 3 never help. In this scenario we get respG,c(1) = 0, respG,c(2) = respG,c(4) = 1/6, and respG,c(3) = 2/3 which puts more causal responsibility on 3's shoulders for not being an exemplar to 4.

Example 7 (Marksmen). Ten marksmen form a firing squad for the execution of a prisoner. They know that exactly one of them has a live bullet in his rifle, but they do not know which one. All ten have (at least theoretically) the choice of firing or not. This is modeled as a game where Nature first chooses the player i∗ that has the live bullet and then the marksmen concurrently shoot or not. Let E be the event that the prisoner dies, and consider an E-play ρ (i.e., i∗ shoots). Due the uncertainty introduced by Nature, only the coalition consisting of all marksmen is f-responsible, respectively, s-responsible for E based on ρ, and hence respG,f (i) = respG,s(i) = 1/10. However, we always have respG,c(i∗ ) = 1 independent of the strategies of the other nine marksmen - i.e. the one with the live bullet carries the entire causal responsibility.

Example 8 (Bogus prevention). A person P is protected by a bodyguard B, who suspects a poisonous attack and puts an antidote into P's coffee. Indeed, an assassin A tries to poison P, but the poison is neutralized by the antidote. Consider the event E that P survives. Based on the play ρ and strategies described above, no single player is f- or s-responsible, but B is c-responsible, while A is not. Now consider the alternative model in which A, seeing B's action, poisons the coffee exactly if B chose to put in the antidote, which determines a strategy σA (e.g., because A and B are old friends, and A wants B to be considered important by P). Suppose that B puts in the antidote, thus determining a strategy σB (inducing the same path ρ as above). Based on these strategies no individual player is c-responsible for P's survivial! We emphasize this point since all versions of Halpern-Pearl's theory do consider B putting in the antidote an actual cause of P's survival, even though the structural equations determined by this model and context already preclude P 's death.

5 Comparison to Other Approaches

We now provide a detailed comparison of our notions with related approaches to responsibility allocation.

Causal Models

An influential formal concept of causality is Halpern and Pearl's notion of actual causes in causal models [Halpern and Pearl, 2005]. In a nutshell, a causal model M consists of variables U ∪ V and functions FX that determine the values for the variables X ∈ V depending on the other variables. A context for M is a tuple ⃗u specifying values for U, which induce unique values for V. A causal formula is of the form [⃗Y ← ⃗y]ϕ, where ϕ is a Boolean combination of statements about the values of the variables in V, and [⃗Y ← ⃗y] denotes the act of forcing ⃗Y ⊆ V to have values ⃗y. This intervention may or may not affect the values of other variables in V. If ϕ becomes a true statement upon evaluating all variables according to context ⃗u, an intervention [⃗Y ← ⃗y], and the functions FX, then we write (M, ⃗u) |= [⃗Y ← ⃗y]ϕ.

A but-for cause for ϕ is a minimal set of variables ⃗X ⊆ V such that (M, ⃗u) |= ( ⃗X = ⃗x), (M, ⃗u) |= ϕ, and there exist alternative values ⃗x′ for ⃗X such that (M, ⃗u) |= [ ⃗X ← ⃗x′ ]¬ϕ. The intuition is that but for the variables in ⃗X, the formula ϕ would not hold. In fact, [Halpern and Pearl, 2005] define a larger class of actual causes for which the axioms above are generalized to allow for witnesses of the but-for condition. In [Baier et al., 2021] we present a translation of a causal model M to an extensive form game G(M) with players V such that a formula ϕ induces a labeling E(ϕ) of G(M) and a context ⃗u naturally induces a path ρ⃗u and a strategy profile σ⃗u . Then:

Theorem 3. For a causal model Mwith context ⃗u, ⃗X ⊆ V is c-responsible for E(ϕ) based on ρ⃗u and σ⃗u in G(M) iff ⃗X = ⃗x is a but-for cause for ϕ in (M, ⃗u).

It is arguably a feature of Halpern and Pearl's framework that it can ascribe actual causality to a larger class of events than but-for causes, e.g., it can distinguish the two players in the Suzy-Billie rock-throwing example from the introduction. It is noteworthy, though, that in this case (and many others, cf. [Halpern, 2015]) the structural model approach distinguishes Suzy as the sole actual cause based on auxiliary variables that are not actions of independent players. In the rock-throwing model the witness is Billy's rock not hitting the bottle rather than Billy's throwing. But the fact that Billy's rock did not hit the bottle is not a decision made by Billyit just happened on the basis of previous actions as dictated by the structural equations. Auxiliary variables do not entail agency nor the possibility to act otherwise (compare the introduction). Our intention is to locate responsibility exclusively within and against (the actions of) autonomous players.

Degree of Responsibility and Blame

Chockler and Halpern assign to actual causes (in the original definition [Halpern and Pearl, 2005]) a degree of responsibility which tries to measure how crucial the cause is to the effect [Chockler and Halpern, 2004]. It is essentially defined as the inverse of the size of a minimal set of interventions such that swapping the cause's value flips the truth value of the effect. It is noteworthy that the degree of responsibility is designed to be comparable across models, while the responsibility value measures the responsibility of each player against the other players within a given model.

Translated to our approach, the degree of t-responsibility of a player would be the inverse of the size of the smallest t-responsible coalition that she belongs to. In our running example, all three players would have degree of f -responsibility 1/2, since {1, 3} and {2, 3} are f-responsible. However, the fact that 3 belongs to both is ignored. Our responsibility value, on the other hand, takes all t-responsible coalitions into account in which the player participates. This captures the idea that belonging to many responsible coalitions makes the player less dependent on others and hence more powerful.

Concurrent Game Structures

The work closest to ours is [Yazdanpanah et al., 2019], where notions of forward and backward responsibility are defined in the context of concurrent game structures. However, there are several differences: First, they do not consider a causal notion of backward responsibility, and their backward responsibility does not take the epistemic state appropriately into account:

An alternative strategy of a responsible coalition is required to bring about an alternative outcome only from a single state on the play, not from all states in the same information set. For example, in their Figure 2, the second player E2 is backward responsible based on the play q0q1q4 (he can avoid the red states from q1), but not based on the play q0q2q6, even though he acted in exactly the same way based on exactly the same knowledge. Second, their notion of backward responsibility is asymmetric: In a game with two players choosing simultaneously and independently from the same set of actions based on the same knowledge, it can happen that they perform identical actions, but one is backward responsible and the other one is not. Third, while [Yazdanpanah et al., 2019, Theorem 3.3] states that backward responsibility is equivalent to forward responsibility from all states on a play, our Theorem 1 states that forward responsibility is equivalent to strategic backward responsibility on all plays. This is a crucial shift of perspective that has-to the best of our knowledge-not been proved before for similar notions of responsibility. In fact, it responds to a central philosophical question left open in prior work: the relation between general (or type-level) responsibility and specific (or token-level) responsibility.

Proof-theoretic Approaches

The work [Broersen, 2011] as well as the series of papers [Naumov and Tao, 2020a; Naumov and Tao, 2020b; Naumov and Tao, 2020c] provide proof-theoretic approaches to responsibility (there called blameworthiness, a term we avoid as it typically involves normative features). They define modal logics with various forms of responsibility modalities and sound and complete axiomatizations for the logical systems. Instead, we take an operational, model-theoretic approach. The computational complexity of their formalizations is left open. Given the semantics of the blameworthiness modalities of [Naumov and Tao, 2020a; Naumov and Tao, 2020b; Naumov and Tao, 2020c], one can expect at least PSPACEhardness (or even undecidability) for checking blameworthiness in these formalisms. Known complexity results about (original or Chellas's) STIT formulas also point to PSPACEhardness for the notions of [Broersen, 2011]. The above papers do not provide a quantitative version of responsibility assigned to individuals or a way to compare responsibilities.

6 Conclusion

We have argued that extensive form games provide a conceptually convenient formal framework for responsibility ascription with just the right trade-off between expressiveness and tractability. We have defined qualitative (coalitional) and quantitative (individual) responsibility notions. Through a set of examples, we demonstrate that our notions capture intuitive responsibility ascription in many subtle examples.

Acknowledgements

This work was funded by DFG grant 389792660 as part of TRR 248 - CPEC, the Cluster of Excellence EXC 2050/1 (CeTI, project ID 390696704, as part of Germany's Excellence Strategy), DFG-projects BA-1679/11-1 and BA1679/12-1, and the European Research Council under the Grant Agreement 610150 (ERC Synergy Grant ImPACT)