Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR

1 Introduction

There has been substantial development of algorithmic systems that make recommendations or decisions about highimpact issues such as healthcare, homelessness, recidivism and parole, and social services [Eubanks, 2018; Azizi et al., 2018]. The General Data Protection Regulations (GDPR) [Parliament and Council of the European Union, 2016] declare that individuals subjected to an automated decision have a right to an explanation of the decision. While the legal scope of such a right is an active topic of debate, there is widespread consensus on the importance of implementing such a concept [Selbst and Powles, 2018; Wachter et al., 2017a] and research on explanations is a central direction in the field of explainable AI (XAI) [Guidotti et al., 2018].

For example, consider an optimization-based automated medical scheduling system that assigns an individual to an appointment three months in the future. The individual may ask a question such as "Why can't I be seen next month?"

In this paper, we adopt the approach of counterfactual explanations [Wachter et al., 2017b] by deriving the minimal change to the world that would have resulted in the alternative indicated by the questioner. We develop an approach to generate counterfactual explanations for optimization-based decisions using a generalization of inverse combinatorial optimization [Heuberger, 2004]. Under some restrictions, we show how to formulate the inverse problem and, further, how to solve it under two common objective functions: the sum of weighted binary variables and the sum of weighted integer variables. Our solution techniques demonstrate that the computational effort to produce an explanation is equivalent to that of the original optimization problem in the former case and a log-factor more expensive than that in the latter case.

In the next section, we provide background on counterfactual explanations and inverse optimization before turning to our formal problem definition in Section 3. Sections 4 and 5 present our contributions w.r.t. the two objective functions and we then discuss the limitation of our work and relate it to existing work in the final sections.

2 Background

2.1 Counterfactual Explanations in XAI

A large part of XAI, especially in machine learning (ML), has focused on explaining decision by making the internal logic of an algorithm more understandable [Burrell, 2016]. A common approach is to generate local approximations of opaque models (e.g., neural networks) with interpretable models (e.g., linear models or decision trees) from which the impact of features on decisions is easier to comprehend [Ribeiro et al., 2016; Simonyan et al., 2013]. This approach has been criticized as insufficient in generating the explanations envisioned by the GDPR, since it does not explicitly describe the circumstances under which a different decision would have been reached. Such a lack makes it difficult to contest the decision and to act to change it, two key goals for user-centered explanations [Wachter et al., 2017b].

A different line of research in XAI addresses these issues with counterfactual explanations [Wachter et al., 2017b] which have the following form: given that a set of facts resulted in decision x, decision ¯x would have been made had these facts been changed in a particular way and the rest of the world had remained unchanged. Using our appointment scheduling example: the individual's medical acuity level was 3 and the appointment was scheduled in three months; had the acuity level been 5 (i.e., more acute), the appointment would have been scheduled next month.

More precisely, a counterfactual is situation that is "contrary to the facts": an imagined alternative to a past event. Counterfactual reasoning invokes a comparison between the imagined event and the factual event [Epstude and Roese, 2008]. By this definition, a counterfactual explanation involves two counterfactuals. First there is a counterfactual question, "Why decision x and not ¯x?", with the imagined decision ¯x being the first counterfactual. The explanation then provides a set of hypothetical facts, different from the original facts, as the second counterfactual. To distinguish between the two counterfactuals, we refer to decision ¯x as the foil and the hypothetical facts as the counterfactual values, using similar terminology toMiller [2019]. Further, it is typically preferable for such an explanation to minimally perturb the facts that led to the original decision.

As a counterfactual explanation explicitly addresses what needs to happen for a decision to be different and avoids the internal logic of the algorithm, such an explanation is better suited for explanations for users [Wachter et al., 2017b].

2.2 Inverse Combinatorial Optimization

Standard (or, forward) optimization searches for an optimal assignment of variables given a model consisting of an objective function, constraints, and parameters. Inverse optimization, in contrast, starts with a model, initial parameter values, and a known solution, and finds the minimal change to the parameter values that would make the solution optimal [Demange and Monnot, 2014; Heuberger, 2004].

To formulate the forward and inverse problems, let x ∈ X ⊆ Rn be a decision vector subject to a feasible set X, c ∈ C ⊆ Rn be an initial parameter vector subject to feasible set C, and f : C × X → R be the objective function. It is assumed that the components of c are present only in the objective, not in any constraints. The minimization variant of the forward problem 〈X, c, f〉 is to find an optimal x∗ such that f(c, x∗ ) = min{f(c, x) : x ∈ X}.

In the inverse problem, defined w.r.t. a norm ‖·‖, we are given a solution ˆx ∈ X that we wish to make optimal by minimally modifying the parameter vector. Let ¯ c ∈ C be the modified parameter vector. The inverse optimization problem is then

In partial inverse optimization [Demange and Monnot, 2014], we are no longer given a full solution ˆx, but instead a partial solution ¯xpi ∈ R for i ∈ I ⊆ {1, . . . , n} and, similarly, must find minimally perturbed parameters. The partial inverse optimization problem is identical to the above model with the additional constraint: ˆxi = ¯xpi , ∀ i ∈ I.

3 ProblemDefinition

Let x∗ be an optimal solution to an instance of a (forward) optimization problem, 〈X, c, f〉. Assume we are asked a counterfactual question "Why is x∗ not different?" such that this difference can be expressed by a foil constraint set, ψ, that x∗ does not satisfy. In our medical scheduling example, this question might be "Why isn't my appointment scheduled next month?", and ψ would represent the constraint that the patient's procedure is in the next month.

Let Xψ ⊆ X represent all points in X that satisfy ψ. Any point in Xψ is a foil (as per Section 2.1), because it represents a counterfactual decision the user has asked about. We assume Xψ ̸= ∅. Let Xcψ = X \ Xψ be the complement of Xψ, and any point in Xcψ be called a factual solution (by definition, x∗ ∈ Xcψ ). An explanation is then generated by finding the counterfactual parameters ¯ c ∈ C that cause a foil to become optimal while minimally perturbing the initial parameters c. We therefore define the Nearest Counterfactual Explanation (NCE) problem for some norm ‖·‖ as:

The explanation, then, is: "If the parameters had been ¯ c instead of c, the alternative decision would have been reached."

This formulation is a novel generalization of both inverse optimization and partial inverse optimization, since it allows a foil to be described with a constraint set, not only a (partial) set of value assignments. For example, a patient can ask why they are not seen in a given time interval, as opposed to only asking why they are not seen on a given day.

3.1 Restrictions

General inverse optimization is computationally difficult, especially with discrete variables [Demange and Monnot, 2014], and the literature is still developing robust solution approaches. We make the following restrictions here to make progress on a subspace that nonetheless includes a number of interesting problems, including our medical example.

1. We limit ψ to one constraint on one component of x with the form ψ : xj ≤ m0 or ψ : xj ≥ m0, j ∈ [n], m0 ∈ N0. 1 We are interested in explanations for one individual, often modeled with a single variable and parameter, xj and cj, and our explanations consider only changes to cj, and not the other components of c. This restriction means that an explanation is about a characteristic of the questioner as opposed to others that the questioner may have no knowledge of. It also protects the privacy of others as their real and counterfactual parameter values are not revealed in an explanation.
2. For the original parameters, c, all foils are strictly suboptimal solutions, i.e. ∄x ∈ Xψ such that min{f(c, x) : x ∈ X} = min{f(c, x) : x ∈ Xψ}. We do not address cases where the foil is an alternative optimal solution to the original problem because such a situation produces

1 We use [n] to denote the interval of values {1, . . . , n}.

the unsatisfying explanation: "The foil is just as suitable as the initial decision, but was not selected due to arbitrary details of the algorithm (e.g., tie breaking)."

1. The components of c and ¯ c appear only in the objective function, not in any constraints. Therefore, any x ∈ X remains feasible for all values of c and ¯ c.
2. There exists at least one feasible foil: Xψ ̸= ∅.

We return to these restrictions in more depth in Section 6. We now address the NCE problem for two common objective functions: the weighed sum of binary variables and the weighted sum of general integer variables.

4 Weighted Sum of Binary Variables

Consider a problem where a subset of individuals are chosen from a group, for example, to receive some service. For such a problem, a natural model is to represent each individual as a binary variable where the 1 represents provision of the service and where some individual measure of the importance of each individual is represented by a scalar value. The appropriate objective function is to maximize the sum of the quality of the chosen individuals and the obvious foil question from an individual is "Why wasn't I selected for the service?"

Definition 4.1 (Weighted Sum of Binary Variables (WSBV)). Let x ∈ X ⊆ {0, 1}n be a binary decision vector, c ∈ Nn0 a vector of integer parameters such that c is not present in any constraints that define X, and c · x = ∑ni=1 cixi be a scalar product of two vectors in Rn . 2 The WSBV maximization problem is max{c · x : x ∈ X}.

Let NCE0-1 be the NCE problem for WSBV. We are given a WSBV instance 〈X, c〉 and a foil constraint ψ. Because x is a binary vector and due to restriction 1, ψ must have the form ψ : xj = 1 or ψ : xj = 0. Let ¯ c ∈ Nn0 be the modified parameter vector, which is identical to c with the exception of component ¯ cj replacing cj, since we are only interested in that one parameter. Thus, using the L1 norm, we define the NCE0-1 problem asmin

Rather than solving a general inverse optimization problem, we can solve this problem in closed-form given optimal solutions to the original problem and to the original problem plus ψ. Intuitively, any reduction in the objective function value incurred by the foil must be exactly compensated by the increase in ¯ cj in order for the foil to be optimal.

Let the following function denote the difference between the optimal foil and optimal factual solution

Since Xψ ⊆ X, it holds that ∆Xψ (y) ≥ 0 for any ψ, X ⊆ {0, 1}n , and y ∈ Nn0 . We prove the validity of our closed form approach for the case when ψ : xj = 1, but it can easily be modified for the case of ψ : xj = 0, as well as the minimization variant of a WSBV problem.

2 Since it is obvious from the context, we write c · x instead of cT · x to avoid multiple superscript indices.

Theorem 1. The 〈X, c, ψ〉 NCE0-1 problem, with ψ : xj = 1 and a non-empty foil set Xψ ̸= 0 has an optimal solution ¯ c∗j = cj +∆Xψ (c).

Proof. By restriction 2, none of the optimal solutions of 〈X, c〉 satisfy ψ. 3 In this case we can write

Since the foil constraint has the form ψ : xj = 1, for each x ∈ Xcψ we have xj = 0. Recalling that ¯ c is identical to c everywhere except the coordinate j, for every ¯ c we have that

Similarly, for each x ∈ Xψ we must have xj = 1 and that the contribution of the non-j components must be identical for every ¯ c, such that

Next, note that by (7) we have that for every solution ¯ c of an NCE 〈X, c, ψ〉 problem, it holds that ∆Xψ (¯ c) = 0. Thus,

Therefore, we have ¯ cj = cj +∆Xψ (c). It is clear that ¯ cj ∈ N0, because both c ∈ N0 and x ∈ N0, and therefore ∆Xψ (c) ∈ N0. Optimality follows from uniqueness of ¯ c.

Theorem 1 shows that the computational effort required to form an explanation arises solely from re-solving the original problem with the added constraint xj = 1. As mentioned, the proof can easily be modified when the foil constraint is ψ : xj = 0, to give the optimal solution ¯ c∗j = cj -∆Xψ (c).

4.1 The Scope of Explanations forWSBV

We now show two examples of explanations that can be generated as a result of solving NCE0-1. In the 0-1 knapsack problem (KP) we are given a knapsack capacity W ∈ N and a set of items [n] ⊆ N, with each item i ∈ [n] associated with a weight wi ∈ N, a profit ci ∈ N, and a binary variable xi ∈ {0, 1} set to 1 iff the item is included in the knapsack. The 0-1 KP is max{∑ni=1 xici : ∑ni=1 xiwi ≤ W}, that is, to select a subset of items such that the sum of the profits of the selected items is maximized and the sum of their weights does not exceed the knapsack capacity.

KP problems are used for many real-life applications, for instance for capital budgeting decisions and our example of providing a limited service [Kellerer et al., 2013]. Using the NCE0-1, the explanation for a person not receiving a service can be "Because the benefit of offering you this service was only cj . If it had increased to ¯ c∗j , you would have been offered the service." Conversely, a person who was offered the service can assess how much their benefit cj can decrease before the service is assigned to someone else.

3 The theorem is also true, if somewhat trivially, without restriction 2, by setting ¯ c∗j = cj.

Another important class of WSBV problems is the weighted MaxSAT problem [Li and Manya, 2009]. We are given a conjunction of n disjunctive clauses, with each clause i ∈ [n] associated with a weight ci ∈ N and a binary variable xi ∈ {0, 1} that is assigned 1 iff the clause is satisfied. The objective is to maximize the total weight of the satisfied clauses, max ∑ni=1 xici. Using our explanation technique, we can ask "Why is clause j not satisfied?", and receive an explanation "Because the weight of this clause was only cj. If it increased to ¯ c∗j , it would be satisfied."

5 Weighted Sum of Integer Variables

We now consider a problem class that includes the medical appointment scheduling example introduced above. In such a problem, the goal is to schedule appointments to maximize some form of health outcome which is often approximated by the minimization of the acuity-weighted sum of appointment times. A foil question from an individual would have the form of asking why their appointment was not scheduled at some other time (e.g., earlier).

Definition 5.1 (Weighted Sum of Integer Variables (WSIV)). Let x ∈ X ⊆ Nn0 be an integer decision vector and c ∈ Nn0 an integer parameter vector, such that c is not present in the constraints that define X. A WSIV minimization problem is of the formmin{c · x : x ∈ X}.

We define the explanation problem NCEN0 . Given is a WSIV instance 〈X, c〉 and a foil constraint ψ, which by restriction 2 takes the form ψ : xj ≤ m0 or ψ : xj ≥ m0, m0 ∈ N0, over the coordinate j ∈ [n] of the variables x. As before, let ¯ c be the modified parameter vector, identical to c for all coordinates other than j. The NCEN0 using the L1 norm is then

In our appointment scheduling example, we are given n patients (jobs) and mmedical resources. Let c ∈ Nn0 represent patient acuity (a higher value means higher acuity), p ∈ Nn0 represent job processing times, and x ∈ X ⊆ N n 0 represent job completion times, where X contains any constraints on the schedule (e.g., resource capacity, task precedence, etc.). The goal is to find a schedule that minimizes the weighted sum of completion times, min{c · x : x ∈ X}. The question "Why can't I be seen before time m0?" is exactly represented by the NCEN0 problem with ψ : xj ≤ m0.

5.1 Theoretical Results

We present theoretical results for the ψ : xj ≤ m0 case. The proof can be modified to show that Theorem 2 holds for the case of ψ : xj ≥ m0 as well.

The NCEN0 is more involved than NCE0-1 because we cannot rely on the fact that xj = 0 in the optimal factual solution. As a result, modifications to the cj parameter change the objective value of both the optimal counterfactual and factual solutions and we must reason about the change in their relative values as cj varies.

We aim to prove that there is a constant c∗j ∈ R0+ such that [c∗j ,∞) ∩ N0 is the set of all feasible solutions to the NCE, i.e. all values ¯ cj ∈ N0 result in feasible solutions iff ¯ cj ≥ c∗j . This result will allow the use of binary search over a number of instances of the forward optimization problem to solve the NCE. To this end, as above, we define an auxiliary function

To establish the observation above it is enough to prove the following.

Theorem 2. Let 〈X, c, ψ〉 be an NCE problem with ψ : xj ≤ m0. Then,

1. ∆Xψ (y) is a monotonically non-increasing function in yj .
2. There is a c0j ∈ R0+ such that ∆Xψ (c0 ) = 0 and c0 coincides with c on every entry other than j.

In what follows, we assume y and ¯ y are two vectors in Rn0+ that are identical over all coordinates except j where yj ≤ ¯ yj, and denote their positive difference by δy. Intuitively, we show that if yj increases by positive δy, both components of ∆Xψ (¯ y) will increase, but the negative component minx∈X ¯ y · x will increase faster, and the function will eventually vanish.

Let us start with an observation that uses the form of the foil constraint to provide bounds on how fast the components of ∆Xψ (¯ y) can increase w.r.t. ¯ yj. Intuitively, part 1 below uses the minimum value of zj to derive a lower bound on the increase of the optimal factual solution w.r.t. ¯ yj. Similarly, part 2 uses the maximum value of zj to give an upper bound on the increase of the optimal foil solution w.r.t. yj.

Lemma 1. Let Z be a finite feasible set.

1. If for each z ∈ Z it holds that k0 ≤ zj, we have δyk0 ≤ minz∈Z ¯ y · z -minz∈Z y · z.
2. If for each z ∈ Z it holds that zj ≤ K0, we have minz∈Z ¯ y · z -minz∈Z y · z ≤ δyK0.

Proof. Let z∗ ∈ Z be an optimal solution for the minimization problem 〈Z, y〉, and let ¯ z∗ ∈ Z be an optimal solution for the minimization problem 〈Z, ¯ y〉. Note also that by definition of ¯ y, for each vector x ∈ Rn we have

Statement (1): since z∗ is optimal given y, we have y ·z∗ ≤ y · ¯ z∗ . Thus, using (12) we deduce

Statement (2) is proved similarly. As ¯ z∗ is optimal for ¯ y,

Then, again using (12) we can write,

We can now proceed to the proof of Theorem 2.

Proof. Assume that Xcψ ̸= ∅, since otherwise both claims hold trivially. First, we aim at proving that ∆Xψ is monotonic non-increasing within the scope of one coordinate. Recall that y and ¯ y are two vectors in Rn0+ that are identical over all coordinates except j where yj ≤ ¯ yj, with their positive difference denoted δy. We shall prove that

Let us look at the three following cases:

1. The case ∆Xψ (¯ y) = 0 is trivial, since by definition ∆Xψ (y) ≥ 0 for every y ∈ Rn0+.
2. Let ∆Xψ (y) = 0. Let x∗,ψ ∈ Xψ be an optimal solution for the minimization problem 〈X, y〉. By definition of ψ, this means x∗,ψ j ≤m0. Let xc ∈ Xcψ be a solution in the complement of Xψ, meaning that, x∗,ψ j ≤m0 < xcj . In order for ∆Xψ (y) = 0, we must have

By this, we have that minx∈Xψ ¯ y · x ≤ minx∈Xcψ ¯ y · x. Which implies that ∆Xψ (¯ y) = 0.

For ∆Xψ to be monotonically non-increasing, the following difference of deltas must be non-positive:

We can observe that (13) will hold iff all foils are suboptimal, meaning that all optimal solutions lie in Xcψ . Using this condition and rearranging (14),

Next, we insert bounds on these terms from Lemma 1. Note that for each x ∈ Xψ it holds that xj ≤ m0. Thus, by Lemma 1 part 2 we have

Similarly, for each x ∈ Xcψ it holds that xj ≥ m0 + 1. Thus, by Lemma 1 part 1 we have

Applying these two inequalities to 14 we have

Next, we prove the second part of Theorem 2, that there is a c0j ∈ R0+ such that ∆Xψ (c0 ) = 0 and c0 coincides with the unmodified parameter vector c on every entry other than j. We must show thatmin

Let us define a vector xmin ∈ Nn0 , where every entry other than j is zero and xmin j = m0 + 1. For every x ∈ Xcψ , we observe that xmin i ≤ xi for each coordinate i. Thus, for every c′ ∈ Rn0+ it holds that c′ · xmin ≤ min{c′ · x : x ∈ Xcψ }. Therefore, (15) will hold if we can satisfy

To this end, we pick an arbitrary xψ ∈ Xψ and recall that xψj ≤ m0. We will satisfy (16) if we can find a c0j ∈ R0+

Note that selecting this value of c0j will also provide an upper bound for the binary search, as discussed next.

5.2 Solving NCEN0 Problems

We use the results of Theorem 2 to show that NCEN0 can be solved with binary search. Theorem 2 assures us that feasible solutions for NCEN0 〈X, c, ψ〉, with ψ : xj ≤ m0, are the integers that lie within the interval [c∗j ,∞) ⊆ R0+ (i.e. ∆Xψ vanishes for each integer in this interval). Since we are looking for the minimal solution, to solve the problem it is sufficient to find ⌈c∗j ⌉.

The last part of the proof of Theorem 2 provides us with an upper bound on the optimal solution, c0j ∈ R0+ such that c∗j ≤ c0j . To compute c0j , we must find a feasible foil, xψ ∈ Xψ. The smallest possible value of c0j will be given by xψ ∈ argmin{c·x-cjxj : x ∈ Xψ}. Alternatively, it may be more convenient to use the original forward objective function, so that xψ ∈ argmin{c · x : x ∈ Xψ}, though this may result in a higher value for c0j . The lower bound on ⌈c∗j ⌉ is cj + 1, because cj < ⌈c∗j ⌉ since all foils are suboptimal at cj (by restriction 2). Since ∆Xψ is a monotonically non-increasing function, it is enough to run binary search on the integer set {cj + 1, . . . , ⌈c0j ⌉} to solve the problem. This, together with the identity ⌈log2⌈x⌉⌉ = ⌈log2 x⌉ for each x ≥ 1, results in the following statement:

Proposition 1. Let 〈X, c, ψ〉 be an NCE problem. Given a vector c0 ∈ Nn , where c0j replaces the j'th entry in the vector c, such that ∆Xψ (c0 ) = 0, the 〈X, c, ψ〉 problem can be solved within at most ⌈log2(c0j -cj)⌉ solutions of the forward WSIV minimization problems of the form 〈¯ c, Xψ〉 and 〈¯ c, Xcψ 〉.

6 Discussion and Limitations

We demonstrated that we can generate counterfactual explanations for general optimization models with two common objective functions. The additional computational effort is solving either a single or logarithmic number of forward optimization problems, depending on the objective function. Our contributions were made within a restricted context.

Our first limitation (Section 3.1) restricted the scope for explanation to a single model parameter. In the context of the GDPR, the restriction to characteristics of the questioner is reasonable both for the need to protect private information and from the perspective of generating a meaningful explanation: a counterfactual that changes characteristics of other individuals has limited value. Lifting the restriction to address a set of parameters concerning the questioner would require general partial inverse optimization. While most inverse optimization literature deals with multiple parameters [Heuberger, 2004], especially in the case of discrete variables, such problems are still challenging. We see this extension as a prime area for near-term future research.

Our second and fourth restrictions require that a foil solution exists and is not optimal for the factual problem. Both restrictions were made because it is unclear what kind of counterfactual explanation is appropriate if they are lifted. If the foil solution does not exist, then the Nearest Counterfactual Explanation problem is infeasible and no possible modification can result in the questioner's counterfactual. If the foil solution is optimal for the original problem, then there is no reason why it was not chosen as the factual solution. In either case, there does not appear to be a meaningful explanation.

Finally, we required that none of the counterfactual parameters appear in the constraints. Without such a restriction, not all solutions x ∈ X would remain feasible as the parameters change, substantially complicating the mathematical structure used in our results. While there exists some work in inverse optimization under such assumptions (e.g., [Yang et al., 1997]), approaches to the problem are not well-developed and form another important research direction.

In addition to the above restrictions, our work relies on the assumption that the users know and understand their weight. For a medical scheduling example, we assume patients know or can access their acuity scores. For the example of solving a knapsack problem to select clients, we assume clients know how much they are ready to pay for a product.

In our framework, a user has several choices after an explanation: they can accept the decision, act to change it (e.g., get a second opinion of their acuity), or contest the decision on the grounds that it is unfair to use this weight in this way. In the latter case, they may ask why the system makes distinctions based on the weight, leading to ethical discussions which are important but beyond the scope of explaining the decision. Though, we note that our approach provides an explanation that can enable a user to pose such metaexplanation questions.

If our assumption does not hold and the user does not understand how their weight was assigned, then they no longer need an explanation of the optimization-based decision, but rather an explanation of how the inputs to the model are determined. This is again beyond our scope as it now demands an explanation from the automated or human system that assigned the weights. But again, by explaining that a change in weight would change the outcome, our approach allows the user to question another part of the decision making system.

7 RelatedWork

Much recent work has looked at counterfactual explanations for classifiers, with seminal work by Wachter et. al [2017b]. Most relevant is work that generates explanations with a binary search over a sequence of combinatorial models [Karimi et al., 2020; Russell, 2019]. To our knowledge, none of the work addresses decisions made by explicit optimization models nor makes the connection to inverse optimization.

Explainable constraint programming has mainly focused on explaining infeasibility [Freuder, 2017], often through the identification of a minimal set of unsatisfiable constraints [Junker, 2004]. A parallel literature exists in mathematical programming [Chinneck, 2008]. While such sets could be viewed as counterfactuals (i.e., one of these constraints must be different), this connection has not been clearly developed and the use of inverse optimization is absent.

Other research has looked at counterfactual explanations in AI Planning, highlighting the difference between specific factual and counterfactual plans [Fox et al., 2017] and describing properties of all counterfactual plans [Eiffer et al., 2020].

The only previous work that we are aware of that relates counterfactual explanations with inverse optimization is that of Brandao and Magazzeni [2020] which generates counterfactual explanations for path planning using an inverse shortest path formulation. While clearly making the connection with inverse optimization, the work focuses on the polynomially solvable inverse shortest path problem and has a substantially narrower scope than ours.

8 Conclusion

We have shown that counterfactual explanations for decisions made by an optimization model can be generated through a generalization of inverse combinatorial optimization, a problem that has been studied in mathematical programming. Within the context of legislation such as the General Data Protection Regulations that mandates the right to an explanation, our approach can produce user-centered explanations that allow an individual to contest and act to change the decision to which they were subject [Wachter et al., 2017b].

Our formulation allows an individual to inquire about any change to a decision that can be represented with a constraint set on the original formulation. With some restrictions, we show that counterfactual explanations for models with two common objective functions can be generated with limited additional computational effort beyond solving the original model. We believe this general approach to counterfactual explanations for optimization-based decisions is a fruitful yet nascent direction that deserves further development.

Acknowledgements

This research was supported by the Natural Sciences and Engineering Research Council of Canada.