Counterfactual Explanations Under Model Multiplicity and Their Use in Computational Argumentation

1 Introduction

Counterfactual reasoning is often leveraged in eXplainable AI (XAI) to shed light on the decision-making process of AI models (e.g. decision trees [Tolomei et al., 2017] and neural networks [Wachter et al., 2017]). In particular, counterfactual explanations (CXs) help users understand the outputs of a model by revealing how minimal changes in its inputs would alter the model's decisions. CXs are often advocated as being useful because they can provide actionable insights into AI models and empower recourse recommendations to users that are negatively affected by the models' decisions. For example, to understand a loan rejection for an applicant asking for £15k to be repaid over 5 years, a CX may suggest a longer repayment period, thus showing the user what needs to be changed for the loan to be approved.

While CXs are widely advocated in XAI for explaining individual models [Guidotti, 2024a], recent work has highlighted the challenges arising when determining CXs in model multiplicity scenarios, where equally performing models that slightly differ in their internals can be obtained for the same task [Black et al., 2022]. Indeed, under model multiplicity, CXs computed for individual models may fail to provide valid recourse with the other models [Leofante et al., 2023; Jiang et al., 2024], thus raising questions about their justifiability as explanations. The following example illustrates the problem.

Example 1. Consider a simple loan application scenario modelled by binary features LoanTermOver10Years, i.e., whether the loan term exceeds 10 years (1) or not (0), and LoanAmountBelow10k, i.e., whether the amount to be borrowed is below £10k (1) or not (0). Assume an individual represented by input x = [0, 0] applies for a loan and the bank uses three equally performing classifiers in F ={f1, f2, f3} to predict whether the loan should be granted. Let y1 =f1(x)=0, y2 =f2(x)=0 and y3 =f3(x)=0 be the classifier's outputs for x as shown below, left:

Then, the loan may be rejected. Suppose the applicant requests an explanation for the rejection and a CX x′ =[0, 1] is produced as shown above, right, intuitively encoding 'if-only the applicant were to request less than £10k then their loan would be accepted'. The choice of x′ is based on it being a valid CX for f1, but, since x′ is still rejected by f2 and f3, it is unclear whether x′ is the best CX under model multiplicity since it only changes one model's prediction. ◻

In this paper, we take the view that computing CXs under model multiplicity requires fine-grained reasoning about the outputs of multiple models simultaneously, and propose a novel approach for this. Specifically, we focus on Multiplicity Decision Frameworks (MDFs) where individual model decisions are first-class citizens and propose novel definitions of CXs based on explicit, nested quantification over (groups of) models in the MDFs, as illustrated next.

Example 2. Continuing from Example 1, we observe that x′ encodes the following explanation, which we call an ∃∀-CX for x: there exists at least one (non-empty) group G = {f1} of models among those in F, such that (i) all models in G agree on the outcome for x, and (ii) x′ is a valid CX for x and (all models in) G. Other CXs may exist, e.g. x′′ = [1, 0] for which f1(x′′ ) = f2(x′′ ) = f3(x′′ ) = 1, which we call a ∀∀-CX for x as it captures the following intuition: (i) all models in F agree on the outcome for x, and (ii) x′′ is a CX for x in all models in F. Such x′′ is intuitively stronger, and potentially more informative, than x′ as it better captures the behaviour of the three models. ◻

In addition to qualitative notions of CXs as in the earlier example, we define quantitative notions of CXs intuitively capturing the number of subsets G of F in which all functions fi ∈ G: (1) agree on fi(x), and (2) differ in the output for x and x′ , i.e., fi(x) ≠ fi(x′ ).

We then study the computational properties of our novel notions and the benefits they provide under model multiplicity, e.g. depending on the quantity of models that change their output, and pointing to trade-offs between the CXs' benefits and their cost to action.

While our notions of CXs are applicable to MDFs with a wide range of AI models, in this paper we explicitly study instantiations thereof in settings where decision models are represented by argumentation frameworks (AFs) as in Computational Argumentation (CA) (see [Atkinson et al., 2017] for an overview). Within CA, the multiplicity that we target may result from the emergence of different AFs with the same arguments (e.g. as in argumentation for case-based reasoning when choosing different default arguments [Cyras et al., 2016; Gould et al., 2024]). Further, this multiplicity naturally arises in AFs that adopt a possible-world semantics, e.g. incomplete AFs [Baumeister et al., 2018; Baumeister et al., 2021].

Contributions. In summary, our main contributions are:

• a general framework for counterfactual reasoning under multiplicity, formalising novel qualitative and quantitative notions of CXs based on explicit, nested quantification;
• a categorization of qualitative definitions of CXs, based on how well they capture multiplicity, and the definition of natural decision problems related to their computation;
• instantiations of our general framework inCAgiving novel notions of CXs for incomplete AFs and AFs for case-based reasoning, and the study of the complexity of the decision problems for these instantiations;
• an illustrative exploration of the applicability of our CA instantiation within legal and healthcare contexts.

2 AGeneral Theoretical Framework

In this section we define qualitative and quantitative notions of CXs for generic Multiplicity Decision Frameworks (MDFs), dealing with model multiplicity, and making use of the following notation. Given two functions f1 ∶ D1 → C1 and f2 ∶ D2 → C2, we say that f1 and f2 are similar if they share the same domain and codomain (i.e., D1 = D2 and C1 = C2). Given similar functions f1, . . . , fn, we simply denote D and C their domain and codomain, respectively. Given a set F = {f1, . . . , fn} of functions, we denote with pow(F) the powerset of F.

Definition 1 (MDF). A Multiplicity Decision Framework (MDF) consists of a set F = {f1, . . . fn} of similar functions that, for any input instance x ∈ D, returns the output F(x) = {yi = fi(x) ∣ i ∈ {1, . . . , n}} ∈ C n .

Note that the output of an MDF may be passed to a method producing a single output for each input as is done in several machine learning contexts, e.g. using majority voting [Black et al., 2022]. In these contexts, if a CX is computed posthoc for the single output, then issues concerning the CX's justifiability may emerge, as we have seen in Example 1. In this paper we take the view that CXs for MDFs should be more granular and allow to reason ex-ante about (sets of) decisions corresponding to different elements in the MDF's output explicitly. In the remainder of this section, we define new qualitative and quantitative notions of CXs, where individual model predictions are first-class citizens.

2.1 AQualitative Approach to CXs

We consider four notions of CXs, based on choosing (i) subsets of the set of functions in an MDF such that the functions all agree on the output for a given input, and (ii) CXs that are valid for all or some of the functions in the chosen subsets while being 'close enough' to the input, according to a distance metric d ∶ D×D → N , as standard in the XAI literature when defining CXs [Guidotti, 2024a].

Definition 2 (νµ-CX). Let F = {f1, . . . fn} be an MDF, x ∈ D an input and ν,µ ∈ {∀, ∃} be two quantifiers. Given a threshold δ ∈ N, we say that x′ ∈ D is a νµ-CX for x, F and δ iff d(x, x′ ) ≤ δ and

• for ν = ∀ and µ ∈ {∀, ∃}: ν fi, fj ∈ F. fi(x) = fj(x) and µfk ∈ F. fk(x′ ) ≠ fk(x);
• for ν = ∃ and µ ∈ {∀, ∃}: ν G ∈ pow(F) ∖∅. fi(x) = fj(x) for all fi, fj ∈ G and µfk ∈ G. fk(x′ ) ≠ fk(x);

Intuitively, for ∀∀-CXs and ∀∃-CXs, all functions agree on the output for the given input, and the CXs offer valid recourse for all/some functions in F, resp.; instead, for ∃∀- CXs and ∃∃-CXs, only some functions in F need to agree on the output for the given input, and the CXs offer valid recourse for these functions.

Note that Definition 2 captures proximity by means of a threshold δ. This is to ease the discussion on computational properties later in the paper, as is often the case in the XAI literature, e.g. [Leofante et al., 2023; Mohammadi et al., 2021]. However, we will also consider optimal counterfactuals, formalised as follows. In the remainder, the set of νµ-CXs for x, F and δ is denoted as νµ(x,F, δ). Moreover, x′ ∈ νµ(x,F, δ) is said to be optimal iff there is no x′′ ∈ νµ(x,F, δ) such that d(x,x′′ ) < d(x,x′ ). The set of optimal νµ-CXs for x, F and δ is denoted as ˜ νµ(x, F, δ).

Informally, Definition 2 allows to specify CXs for subsets of F that can be chosen dynamically by using the quantifiers ν and µ, as illustrated in the following example.

Example 3. Consider the MDF introduced in Example 1. Formally, we have F = {f1, f2, f3} with fi ∶ {0, 1}2 → {0, 1} for any i ∈ {1, 2, 3} and thus D = {0, 1}2 , C = {0, 1}3 . Consider the distance metric d([a1, a2], [b1, b2]) = ∣a1-b1∣+∣a2b2∣, and threshold δ = 2. Then, given the input x = [0, 0], the (optimal) νµ-CX of x w.r.t. F and δ are described in the last column of the following table.

It holds that functions fis (with i ∈ {1, 2, 3}) classify the input instance x = [0, 0] (resp., x′′ and x′′′ ) with fi(x) = 0 (resp., fi(x′′ ) = fi(x′′′ ) = 1). Thus, x′′ and x′′′ are ∀∀-CXs for x, F and δ. However, among x′′ and x′′′ , only the former is optimal, due to having a lower distance from x (as d(x, x′′ ) = 1 < d(x, x′′′ ) = 2). ◻

We will focus on two decision problems regarding νµCXs, i.e., existence and verification, as follows.

Definition 3 (Existence). Let F = {f1, . . . fn} be an MDF, x ∈ D be an input, δ a distance threshold, and ν, µ ∈ {∀, ∃} be two quantifiers. Eνµ (resp. ˜Eνµ ) is the problem of deciding whether there exists a νµ- (resp., ˜ νµ-) CX for x, F and δ.

The following proposition states the relations between the existence problems, also synthesized in Figure 1.

Proposition 1. The following relations hold:

• (a) E∀∀ implies E∀∃ (resp., ˜E∀∀ implies ˜E∀∃ );
• (b) E∀∃ implies E∃∀ (resp., ˜E∀∃ implies ˜E∃∀ );
• (c) E∃∀ and E∃∃ (resp., ˜E∃∀ and ˜E∃∃ ) are equivalent;
• (d) ˜Eνµ and Eνµ are equivalent, for any ν,µ ∈ {∃,∀};
• (e) The inverse of relations (a) and (b) does not hold.

Note that (d) is trivial, as the existence of a νµ-CX for x, F and δ implies the existence of an optimal νµ-CX for x, F and δ, and vice versa, for any fixed ν,µ ∈ {∀, ∃}.

Definition 4 (Verification). Let F = {f1, . . . fn} be an MDF, x,x′ ∈ D be two inputs, δ a distance threshold, and ν,µ ∈ {∀, ∃} be two quantifiers. Vνµ (resp., ˜Vνµ ) is the problem of checking whether x′ is a νµ- (resp., ˜ νµ-) CX for x, F and δ.

Differently from the case of the existence problem, the optimality constraint makes the problems Vνµ and ˜Vνµ nonequivalent. That is, ˜Vνµ implies Vνµ , while the vice-versa may not hold as there may exist some νµ-CX for x, F and δ that is not optimal, as illustrated next.

Example 4. Continuing from Example 3, for any pair of quantifiers ν,µ ∈ {∃,∀} it holds that (x,x′′ ,F, δ = 2) and (x,x′′′ ,F, δ) are true instances of Vνµ , as both x′′ and x′′′ belongs to νµ(x,F, δ). However, as d(x,x′′ ) < d(x,x′′′ ), we have that (x, x′′ ,F, δ) is the only true instance of ˜Vνµ . ◻

The relationships between verification problems are outlined below and summarised in Figure 1.

Proposition 2. The following relations hold:

• (a) V∀∀ implies V∀∃ ;
• (b) V∀∃ implies V∃∀ ;
• (c) V∃∀ and V∃∃ (resp., ˜V∃∀ and ˜V∃∃ ) are equivalent;
• (d) ˜Vνµ implies Vνµ , for any ν,µ ∈ {∃,∀};
• (e) The inverse of relations (a) and (b) does not hold.

2.2 AQuantitative Approach to CXs

Our qualitative notions of CXs offer limited insight into the numerical strength of an explanation in terms of multiplicity. Moreover, when the functions in F do not all agree on the outcome for x, the qualitative notions cannot distinguish the type of CX. For illustration, assuming f3(x) = 1 in the previous example, we would no longer be able to distinguish between x′ and x′′ , as they collapse to be both ∃∀-CXs for x.

Here, we introduce a novel, entirely quantitative definition of CXs, making use of the following notation. We denote with F(x,x′ ) = ∣{G ∈ pow(F). fi(x) = fj(x) and fi(x′ ) ≠ fi(x) for all fi, fj ∈ G}∣ the number of subsets G of F in which all functions fi ∈ G: (1) agree on fi(x), and (2) differ in the output for x and x′ , i.e., fi(x) ≠ fi(x′ ). We illustrate this notation next.

Example 5. Consider the MDF F = {f1, f2, f3} and inputs x = [0, 0] and x′ = [0, 1] of Example 3 having distance d(x, x′ ) = 1 ≤ δ = 2. We have that F(x,x′ ) = ∣{∅, {f1}}∣ = 2. When considering x′ = [1, 0] (or x′ = [1, 1]) we have that F(x,x′ ) = ∣pow(F)∣ = 23 = 8. ◻

Definition 5 (k-CX). Let F = {f1, . . . fn} be an MDF, x ∈ D an input, δ ∈ N a threshold, and k ∈ N+ a positive integer. We say that x′ ∈ D is a k-CX for x, F and δ iff d(x, x′ ) ≤ δ and F(x,x′ ) ≥ k.

The set of k-CXs for x, F and δ is denoted as k(x,F, δ). Moreover, x′ ∈ k(x,F, δ) is said to be optimal iff there is no x′′ ∈ k(x,F, δ) such that d(x,x′′ ) < d(x,x′ ). The set of optimal k-CX for x, F and δ is denoted as ˜ k(x, F, δ).

Example 6. Continuing from the previous example, we have that x′ and x′′ = [1, 1] are the only 8-CXs for x, F and δ. Moreover, only x′ is optimal, i.e., ˜8(x,F, δ) = {x′ }. ◻

The natural quantified versions of the existence and verification problems follow.

Definition 6 (Quantified Existence). Let F = {f1, . . . fn} be an MDF, k ∈ N, x ∈ D be an input, and δ a threshold. Ek (resp., ˜Ek ) is the problem of deciding whether there exists a k- (resp., ˜ k-) CX for x, F and δ.

Definition 7 (Quantified Verification). Let F = {f1, . . . fn} be an MDF, k ∈ N, x, x′ ∈ D be two inputs, and δ a threshold. Vk (resp., ˜Vk ) is the problem of checking whether x′ is a k(resp., ˜ k-) CX for x, F, and δ.

The next proposition states the relations between the existence and verification problems, also synthesized in Figure 1.

Proposition 3. Let F = {f1, . . . fn} be an MDF, x an input, and δ a threshold. The following relations hold:

• (a) V2n and V∀∀ (resp., ˜V2n and ˜V∀∀ ) are equivalent;
• (b) E2n and E∀∀ (resp., ˜E2n and ˜E∀∀ ) are equivalent;
• (c) E∃∃ and E∃∀ (resp., ˜E∃∃ and ˜E∃∀ ) are equivalent to Ek=1 (resp., ˜Ek=1 );
• (d) V∃∃ and V∃∀ (resp., ˜V∃∃ and ˜V∃∀ ) are equivalent to Vk=1 (resp., ˜Vk=1 ).

3 An Argumentative Setting

We now instantiate our framework within the context of Computational Argumentation (CA), choosing specifically Abstract Argumentation (AA) as the underlying form of CA [Bench-Capon and Dunne, 2007]. We first give some core background in AA (Section 3.1), specifically on the AA Framework (AF) [Dung, 1995], followed by the corresponding instantiations of the notions introduced in Section 2 (Section 3.2). We then illustrate the emergence of model multiplicity in AA with two case studies: with incomplete AF [Baumeister et al., 2018; Fazzinga et al., 2020] (Section 3.3) and with AA-CBR [Cyras et al., 2016; Gould et al., 2024], when an AF is used to perform case-based reasoning (Section 3.4). Finally, we study the computational complexity of the existence and verification problems we have defined in the argumentative setting we consider (Section 3.5).

3.1 Background on AFs

Let A a set of arguments, which we call universal. An Abstract Argumentation Framework (AF) [Dung, 1995] is a pair ⟨A,R⟩, where A ⊆ A is a set of arguments and R ⊆ A × A is a set of attacks: if (a, b) ∈ R then we say that a attacks b. Given an AF Λ = ⟨A,R⟩ and a set S ⊆ A of arguments, the sets of defeated and acceptable arguments w.r.t. S are as follows (where Λ is understood):

• Def(S) = {a ∈ A ∣ ∃(b, a) ∈ R. b ∈ S};
• Acc(S) = {a ∈ A ∣ ∀(b, a) ∈ R. b ∈ Def(S)}.
• Then, S ⊆ A is said to be (i) conflict-free iff S ∩Def(S) = ∅;

and (ii) admissible iff it is conflict-free and S ⊆ Acc(S).

Different semantics have been proposed to characterize collectively acceptable sets of arguments, called extensions [Dung, 1995]. Specifically, S⊆A is an extension called:

• complete (co) iff it is admissible and S = Acc(S);
• preferred (pr) iff it is a ⊆-maximal complete extension;
• stable (st) iff it is a preferred extension s.t. S∪Def(S)=A;
• grounded (gr) iff it is a ⊆-minimal complete extension.

Example 7. Let Λ = ⟨A,R⟩ be an AF where A = {a, b, c} and R = {(a, b), (b, a), (b, c), (c, c)}. AF Λ has three complete extensions: E1 = ∅, E2 = {a}, E3 = {b}, where E2 and E3 are preferred, E3 is stable, and E1 is grounded. ◻

The set of complete (resp. stable and grounded) extensions of an AF Λ will be denoted by co(Λ) (resp. pr(Λ), st(Λ), gr(Λ)). With a small abuse of notation, we also use gr(Λ) to denote the grounded extension.

Several decision problems can be associated to an AF Λ under semantics σ, including the verification problem, denoted as Vσ,Λ(S), that checks whether a given set S of arguments belongs to σ(Λ). For illustration, considering the AF Λ of Example 7, V st,Λ(S = {b}) returns true as S ∈ st(Λ).

Figure 2: iAF ∆ of Example 8 and its completions Λi with i ∈ {1, 2, 3}. (Dashed) nodes/arrows represent (uncertain) arguments/attacks, respectively.

The complexity of the above problems has been investigated (see [Dvor´ak and Dunne, 2017] for a survey).

3.2 Argumentative MDFs and CXs

Argumentative Multiplicity Decision Frameworks are MDFs comprising argumentative functions able to solve argumentative queries about decision problems in the argumentation frameworks (AFs in this paper) underpinning the functions, as follows. Note that, from now on, for uniformity with Section 2, we use x to denote a set of arguments in A.

Definition 8 (AA-MDF). An AA Multiplicity Decision Framework (AA-MDF) is an MDF with F = {f1, . . . fn} consisting of argumentative functions fi(x) = Pσi,Λi i (x) whose input is a set of arguments x ⊆ A, and whose output is a boolean answer to the question Pσi,Λi i (x), where: P is a decision problem; σi is a semantics; and Λi is an AF.

Thus, two functions in an AA-MDF are similar in that they share the same domain (i.e., the universal set of arguments A) and the same codomain (i.e., a boolean value corresponding to the output of an argumentative decision problem).

Qualitative and quantitative CXs for AA-MDFs are then as in Section 2, but using the following concrete distance metric whereby the distance between two sets of arguments is the number of changes needed to make them equal.

Definition 9 ( Symmetric Difference Distance Metric). Let Λ = ⟨A,R⟩ be an AF. Given two sets x ⊆ A and x′ ⊆ A of arguments, the symmetric difference distance metric d(x, x′ ) between x and x′ is given by d(x, x′ ) = ∣x ∖ x′ ∣ + ∣x′ ∖ x∣.

Considering, e.g., the sets x = {a, b},x′ = {b} and x′′ = {a}, it holds that d(x,x′ ) = d(x,x′′ ) = 1. We note that a similar distance metric is commonly adopted in several works within logic-based explainable AI to compare vectors of (binary) features [Barcel´o et al., 2020; Alfano et al., 2025; Guidotti, 2024b].

3.3 AA-MDFs and CXs with Incomplete AF

For our first case study, consider incomplete AFs (iAFs), i.e., tuples ⟨A,B,R,T⟩, where A and B are disjoint sets of arguments, and R and T are disjoint sets of attacks between arguments in A ∪ B. Arguments in A and attacks in R are said to be certain, while arguments in B and attacks in T are said to be uncertain [Baumeister et al., 2018; Fazzinga et al., 2020]. Certain arguments/attacks in A/R are definitely known to exist, while uncertain arguments/attacks in B/T are not known for sure: they may or may not occur.

An iAF compactly represents alternative AF scenarios, called completions. A completion for an iAF ∆ = ⟨A, B, R, T ⟩ is an AF Λ = ⟨A′ , R′ ⟩ such that A ⊆ A′ ⊆ A∪B and R ∩ (A′ × A′ ) ⊆ R′ ⊆ (R ∪ T ) ∩ (A′ × A′ ).

Verification problems for iAF have been investigated in [Baumeister et al., 2018; Fazzinga et al., 2020]. Given an iAF ∆ = ⟨A, B, R, T ⟩, a set of arguments x ⊆ (A ∪ B), and a semantics σ ∈ {gr, co, pr, st}, the possible/necessary verification problem under σ (denoted as PVσ,∆/NVσ,∆) consists in deciding whether x is a σ-extension in any/all completions of ∆, respectively.

Example 8. Consider a legal situation where a defendant, Alex, is accused of robbery. Bob, a potential witness, says that they possibly saw Alex. It is unclear whether Bob will testify or whether the jury will consider Bob's eventual testimony. This situation can be modelled by the iAF ∆ of Figure 2 (left), where statements 'Alex will not be found guilty' and 'Bob will testify' are represented by arguments a and b, respectively. The iAF ∆ has three completions Λ1, Λ2, and Λ3 (see Figure 2) capturing alternative scenarios. x = {a} is a stable extension for all the three completions (i.e., NV st,∆(x) holds), while x′ = {b} is a stable extension in only one of the three completions (i.e., PV st,∆(x′ ) holds). ◻

However, if PV/NV problems are false, a user may want to know the reasons. For instance, assume the user is interested in knowing whether both Bob will testify and Alex will not be found guilty. As x = {a, b} is neither a possible nor necessary extension, an interesting question is why not. To answer such questions we make use of an AA-MDF where argumentative function fi(x) solve the problem Vσi,Λi i (x), as outlined next. Example 9. Consider the iAF ∆ of Example 8. To capture such multiplicity , an AA-MDF F = {f1, f2, f3} (see Figure 3) can be instantiated, where functions fi(x) = V st,Λi (x) return true if x ∈ st(Λ). Thus:

• for x = {a, b}, f1(x) = f2(x) = f3(x) = 0, intuitively capturing the fact that {a, b} is not a stable extension in any of the three AFs;
• for x′ = {b}, f1(x′ ) = 1 and f2(x′ ) = f3(x′ ) = 0, intuitively capturing the fact that {b} is a stable extension only for AF Λ1; and
• for x′′ = {a}, f1(x′′ ) = f2(x′′ ) = f3(x′′ ) = 1, intuitively capturing the fact that {a} is a stable extension in all of the three AFs.

Assume the Symmetric Difference Distance Metric (cf. Definition 9), and a threshold δ = 2. It holds that x′′ = {a} belongs to ˜ νµ(x, F, δ), for any ν, µ ∈ {∃, ∀}, intuitively capturing the notion 'if only you remove {b} from x = {a, b}, then you can conclude that x′′ is a stable extension in all completions, which tells us that if only Bob does not testify, then Alex will not be found guilty in any possible scenarios.' ◻

Thus, counterfactual reasoning in AA-MDF encodes explanations in the form of minimal changes to the input set of arguments to obtain a different outcome (i.e., an extension).

Further, we illustrate the usefulness of the resulting instances of our quantitative notions of CXs.

Example 10. Continuing from Example 9, we have that F(x,x′ ) = ∣{∅, {f1}}∣ = 2, while F(x,x′′ ) = ∣pow(F)∣ = 23 = 8. Thus, for δ = 2, we have that x′ and x′′ belong to ˜2(x,F, δ), while only x′′ belongs to ˜8(x,F, δ). Intuitively, x′′ captures an explanation of the form: 'if only you remove {b} from x then you can conclude that x′′ is a stable extension independently of the chosen set of scenarios'. ◻

Finally, qualitative and quantitative problems in AA-MDF naturally instantiate their MDF counterparts (cf. Definitions 3-4 and 6-7), where x and x′ denote sets of arguments.

Example 11. Considering the AA-MDF of Example 9, it holds that for any ν,µ ∈ {∃,∀}: (x,F, δ) is a true instance of ˜Eνµ and Eνµ ; and (x,x′′ ,F, δ) is a true instance of ˜Vνµ and Vνµ . Moreover, (x,x′ ,F, δ) is a true (resp. false) instance of ˜V∀∃ (resp. ˜V∀∀ ). Also, quantitatively, for k-CXs, we have that for any k ∈ {1, . . . , 8}: (x,F, δ) is a true instance of ˜Ek and Ek ; and (x,x′′ ,F, δ) is a true instance of ˜Vk and Vk . Finally, (x,x′ ,F, δ) is a true instance of ˜Vk and Vk , for k ∈ {1, 2}. ◻

3.4 AA-MDFs and CXs with AA-CBR

We now show how our AA-MDFs can be applied with Preference-Based Abstract Argumentation for Case-Based Reasoning (AA-CBR-P) [Gould et al., 2024], which is a binary classification model using an AF as a reasoner constructed from labelled data points, known as cases, and user preferences. In AA-CBR-P, cases are structured with a characterisation (e.g. a set of features) and a labelled outcome. A casebase is a set of past cases, and can be ordered by how exceptional cases are as determined by a provided sequence of preorders defined over the characterisations. An AF can be obtained from the casebase whereby arguments are cases and attacks occur between cases of opposing outcomes from more exceptional to less exceptional cases; an additional constraint ensures minimal difference between the cases to avoid unnecessary attacks. When defining attacks, we apply the preorders in the sequence lexicographically. Thus, preferences are applied based on how the preorder sequence is specified. Different preferences naturally introduce multiplicity of AFs. An unlabelled new case, N, can be classified by adding it to the AF using a notion of irrelevance. We then compute the grounded semantics. If a default case is accepted, we assign its outcome to the new case; otherwise, we assign the opposing outcome. For example, we may characterize cases by sets of high-priority and low-priority features, with case A considered more exceptional than case B if either A has a superset of high-priority features or they have the same set of highpriority features and A has a superset of low priority features. Different stakeholders may consider which features are high or low priority differently.

Example 12. Consider assessing patients in good (+) or poor health (-) within a simple medical setting. Patients may display weight loss (feature a), maintain a healthy diet (feature b), suffer from a chronic condition (feature c), experience appetite loss (feature d), and engage in regular exercise (feature e). When conducting this assessment, three clinicians consider the same set of past patients as their casebase, Dcb, to assess a new patient, N, who presents with all features. However, differing clinicians will prioritise each feature in their assessment differently, with clinician 1 considering a and d as high-priority features and b, c, and e as low-priority features; clinician 2 considering feature c as a high-priority feature and a, b, d and e as low-priority features; and clinician 3 considering d as a high-priority feature and a, b, c and e as low-priority features. Figure 4 showcases the AA-CBR-P models for each clinician. All three models include the default case, C0, in the grounded extension and, therefore, predict that the new case N is in poor health (-). ◻

The clinicians may be convinced that the patient is healthy despite what the models suggest. We can leverage AA-CBR-P as an interpretable argumentative model to generate CXs that can modify the models to accommodate this. This form of counterfactual can be viewed in the light of contestability , which is necessary to identify and repair incorrect predictions or faulty reasoning in algorithmic decision systems [Leofante et al., 2024].

To do so, we can leverage an AA-MDF with the problem P gr,Λi i (x) = [C0 ∈ gr(AFPi (x ∩Dcb,N))], where AFPi (.) is a function constructing the AF with AA-CBR-P using clinician i's preferences, x is the input set of arguments, Dcb is the casebase and N is a new case. We can identify which subsets of the casebase can be used to change the outcome using the symmetric distance metric (Definition 9), δ = 5 and letting x = Dcb. Intuitively, this asks the counterfactual question of which past patients need to be disregarded from each clinician's casebase for the new patient to be predicted as healthy.

The following table showcases (a subset of) possible CXs.

We see two possible ˜ ∀∀-CXs, which require removing two arguments from the casebase to convince all three clinicians to change their outcome for the new case. The first ˜ ∀∀-CX {C1,C2,C4,C6} states that if arguments C3 and C5 are removed from the casebase, then all three clinicians will predict that the patient is in good health. Similarly, the second ˜ ∀∀- CX {C1,C3,C4,C6} requires removing arguments C2, C5.

However, disregarding two arguments from the casebase may be extreme, and comes at a greater cost than if we remove solely C5 or solely C2. Both scenarios convince two out of three of the clinicians to change their prediction but with only a single argument removed. These are optimal ˜ ∀∃- CXs. Our novel CX notions can, therefore, empower a user with a choice between a 'stronger' CX that convinces more clinicians to change their minds or a 'weaker' CX in which fewer clinicians change their minds, but with a smaller and more palatable cost to action.

3.5 Computational Complexity

The parametric nature of AA-MDF is influenced by three key aspects: 1) the class of AFs used, 2) the specific argumentation problem considered, and 3) the semantics applied. These aspects result in numerous possible combinations, making it infeasible to fully address the complexity of all variants. Thus, we focus on a single source of multiplicity, reserving the exploration of other dimensions for future research. Particularly, we focus on multiplicity that comes from choosing multiple AFs, as in the case of Sections 3.3 and 3.4. Moreover, to limit multiplicity in the number of extensions, we adopt the grounded semantics, also motivated from the AA-CBR instance where the grounded semantics is used for data classification. As argumentative queries/functions, we choose U gr,Λ, that is a small variant of the verification problem (i.e., V gr,Λ) returning true iff the input set of arguments x is contained in the grounded extension of Λ (this last choice is also motivated from the AA-CBR instance). Note that, this different choice of problem does not impact on the complexity results, as problems U and V can both be solved in PTIME [Dvor´ak and Dunne, 2017].

Theorem 1. The problems Eνµ and ˜Eνµ are in PTIME for any ν, µ ∈ {∃, ∀}.

Theorem 2. The problems Vνµ and ˜Vνµ are in PTIME for any ν, µ ∈ {∃, ∀}.

From the previous theorems we can conclude that, independently of the quantification, computing a CX in the chosen setting of interest can be done in PTIME. However, this can not generally hold when moving the attention to the quantified versions, as stated in the following theorems.

Theorem 3. The problems Ek and ˜Ek are in PTIME for k ∈ {1, 2n }; and in NP for k /∈ {1, 2n }.

Theorem 4. The problems Vk , ˜V1 , and ˜V2n are in PTIME; while ˜Vk is in coNP for any k /∈ {1, 2n }

Thus, these results demonstrate the trade-off between the granularity of the CX and its complexity; specifically, the finer the granularity, the greater the complexity.

4 RelatedWork

Model multiplicity has been the subject of recent research efforts within the trustworthy machine learning community [Black et al., 2022]. Researchers have shown that among equally accurate models, there could be different fairness characteristics [Wick et al., 2019; Coston et al., 2021], interpretability levels [Rudin, 2019; Semenova et al., 2022] and even inconsistent explanations [Fisher et al., 2019; Mehrer et al., 2020; Marx et al., 2023]. More central to this work, a Mixed-Integer Linear Programming encoding method has been proposed to compute CXs that are provably valid for all feed-forward neural networks in an ensemble [Leofante et al., 2023]. This approach corresponds to a specific instantiation of our framework, namely ∀∀ CXs. Different from us, their work focuses on deep learning models, and their encoding does not apply to our setting in this paper.

Meanwhile, argumentation has been advocated by prominent works in the explainable AI literature [Miller, 2019] as a useful mechanism for explanation, given that a majority of statements made in explanations have been shown to actually be argumentative claim-backings [Antaki and Leudar, 1992]. This has given rise to a whole sub-field of works known as argumentative explainable AI (see [Cyras et al., 2021; Vassiliades et al., 2021; Guo et al., 2023] for overviews), where argumentation is used for explaining AI models. This range of methods includes those explaining argumentative reasoning mechanisms themselves, e.g. [Ulbricht and Wallner, 2021; Brewka and Ulbricht, 2019; Saribatur et al., 2020; Fan and Toni, 2014; Amgoud, 2024; Borg and Bex, 2024; Kampik et al., 2024; Yin et al., 2024]. However, these methods generally assume access to the underlying AF and thus do not qualify as post-hoc explanations. Moreover, while some methods also touch upon counterfactual reasoning [Fan and Toni, 2014; Amgoud, 2024; Borg and Bex, 2024; Kampik et al., 2024; Yin et al., 2024; Alfano et al., 2024], none explicitly consider the challenge posed by model multiplicity, which we address in this paper for the first time.

Within the realm of model multiplicity, an argumentationbased solution to the problem of aggregation to address model multiplicity, while factoring in CXs has been proposed [Jiang et al., 2024]. Their solution is in the spirit of an ∃∀ instance of our approach whereby F is a set of machine learning models for binary classification. Moreover, their aggregation strategy relies on the availability of CXs, while our goal here is to define CXs for the whole set of functions.

5 Conclusions and FutureWork

We introduced a novel method for addressing the challenges of counterfactual reasoning in Multiplicity Decision Frameworks (MDFs). We proposed qualitative and quantitative definitions of CXs for MDFs, categorized by the degree of satisfaction, which indicates the strength of the explanation. Our framework is defined generally, supporting any instance in which model multiplicity arises and providing a path to resolving individual CXs that would otherwise conflict.

Further, we have instantiated our novel framework within abstract argumentation, obtaining the Argumentative Multiplicity Decision Frameworks (AA-MDFs), that are MDFs comprising argumentative functions able to solve argumentative queries about decision problems. While our notion of AA-MDF is designed to capture a wide range of sources of multiplicity in abstract argumentation, it could be naturally extended to address diverse scenarios in which other forms of argumentation are needed. An example amounts to structured argumentation frameworks [Besnard et al., 2014], where the structural composition of arguments may introduce variations. Variations can also stem from differences in preferences used during the construction of argumentation frameworks, such as in preference-based abstract argumentation for case-based reasoning [Gould et al., 2024] or ASPIC+ [Modgil and Prakken, 2014], amongst others. Furthermore, it accounts for distinct choices of argumentation semantics applied within the same framework, which can yield varying conclusions. Additionally, our framework could accommodate multiplicity arising from different choices of probabilities associated to argumentative structures. As future work it would be interesting to instantiate our AA-MDFs in the case of probabilistic AFs since here, as in iAFs, multiplicity arises from the different AFs referred to as possible worlds [Dung and Thang, 2010; Li et al., 2011].

We also provided novel notions of CXs for incomplete AFs and AFs for case-based reasoning, as well as analyzed the complexity of decision problems related to counterfactual existence and verification. Further, we have exemplified the potential of our approach in three different real-world, highstakes scenarios (i.e., financial, legal, and healthcare) where the validity of recourse recommendations may be critical.

An interesting direction for future research is the investigation of properties of our CXs, as done for (non-post-hoc) explanation strategies in the CA literature [Ulbricht and Wallner, 2021; Jiang et al., 2024; Borg and Bex, 2024]. Moreover, we plan to undertake further analyses of MDFs in argumentation, both within the settings we have described and others, e.g. when multiplicity amounts to alternative dialectical strengths for the same arguments in Quantitative Bipolar AFs [Baroni et al., 2018], due to different choices of initial intrinsic strengths for the arguments or different gradual semantics [Baroni et al., 2019].

As a further line for future work, we plan to instantiate MDFs to other AI domains with pronounced multiplicity, such as ensemble models typically used in machine learning.

Acknowledgments

Alfano was supported by the PNRR MUR project PE0000013-FAIR and project Tech4You ECS0000009. Gould was supported by UK Research and Innovation [UKRI Centre for Doctoral Training in AI for Healthcare grant number EP/S023283/1]. Leofante was supported by Imperial College London through the Imperial College Research Fellowship scheme. Rago and Toni were partially funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 101020934) and by J.P. Morgan and the Royal Academy of Engineering under the Research Chairs and Senior Research Fellowships scheme (grant agreement no. RCSRF2021\11\45).