Contrastive Explanations of Centralized Multi-agent Optimization Solutions

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 16:07:14

Abstract: In many real-world scenarios, agents are involved in optimization problems. Since most of these scenarios are over-constrained, optimal solutions do not always satisfy all agents. Some agents might be unhappy and ask questions of the form “Why does solution S not satisfy property P ?”. We propose CMAOE, a domain-independent approach to obtain contrastive explanations by: (i) generating a new solution S′ where property P is enforced, while also minimizing the differences between S and S′; and (ii) highlighting the differences between the two solutions, with respect to the features of the objective function of the multi-agent system. Such explanations aim to help agents understanding why the initial solution is better in the context of the multi-agent system than what they expected. We have carried out a computational evaluation that shows that CMAOE can generate contrastive explanations for large multi-agent optimization problems. We
have also performed an extensive user study in four different domains that shows that: (i) after being presented with these explanations, humans’ satisfaction with the original solution increases; and (ii) the constrastive explanations generated by CMAOE are preferred or equally preferred by humans over the ones generated by state of the art approaches.

Main paper: 
 introduction: 
 In many real-world scenarios, centralized AI systems generate solutions for optimization problems involving multiple agents with conflicting preferences. Due to these conflicts and the over-constrained nature of the problems, satisfying all agents' preferences is often impossible, and AI decisions might lead to some agents being unhappy (Kraus et al. 2020 ). In such situations, it is natural that some agents question the decisions made by the AI system, since there is a mismatch between the proposed solution and the user's mental model (Chakraborti et al. 2017) .Generating explanations for such questions may improve the AI system's transparency, facilitate human-computer collaboration, and increase human satisfaction (Bradley and Sparks 2009) . Studies in different areas ranging from Explainable AI (Krarup et al. 2021) to social sciences (Lim, Dey, and Avrahami 2009; Miller 2019) or marketing (Tomaino et al. 2022) show that users typically formulate "why?" questions when they are not happy with a given solution. These questions usually take the form of "Why does solution S not satisfy property P ?". There exist two main approaches to answering these questions in the literature: counterfactual and contrastive explanations.Counterfactual explanations (Wachter, Mittelstadt, and Russell 2017; Korikov, Shleyfman, and Beck 2021) try to provide explanations by constructing a hypothetical situation where the agent would have received its desired solution if its inputs were different. These explanations take the form 50 of "solution S would have satisfied property P if your input to the system had been Y ′ rather than Y ′′ ". This type of explanations are not always valid, as the suggested recourses might not be actionable in practice. Another alternative to answering "why?" questions focuses on contrastive expla-55 nations (Lipton 1990; Miller 2021) . In this case, the focus is purely on understanding why the solution returned by the AI system was a better choice than the one the human agent who requested the explanation had in mind. Unlike counterfactuals, contrastive explanations do not prescribe actions, 60 so they can be safely generated across a wider range of domains.Inspired by (Krarup et al. 2021) , in this paper we present CMAOE, a domain-independent approach to generate local contrastive explanations for multi-agent optimization prob-65 lems where decision making is centralized. Figure 1 depicts CMAOE. First, the solver generates a solution S for the original Centralized Multi-Agent Optimization Problem (CMAOP) and presents it to the user. Then, the user formulates a question asking why solution S does not satisfy 70 property P . This is passed to CMAOE, which generates a new hypothetical CMAOP (HCMAOP) that forces property P to be satisfied. The hypothetical problem suggested by the user might lead to a new solution that is very different from the original one. This is often not desirable, since (i) the new solution should be plausible in the real world, i.e., it should be similar to the one generated by the solver; and (ii) a large number of changes between the original and new solutions would entail longer explanations that could frustrate users. Therefore, HCMAOP not only encapsulates property P , but also modifies the original problem to minimize the number of changes between the original solution S and the new solution S ′ . The Solver sends these two solutions to CMAOE, which finally generates an explanation by computing their differences. This process is iterative, as the user can ask further questions until the explanation is satisfactory, also gaining a better understanding of the decision-making process followed by the Solver at each iteration.The main contributions of this paper are: (i) the definition of hypothetical CMAOP; (ii) the automated generation and solving of HCMAOP that yields contrastive explanations; (iii) a computer-based evaluation of several CMAOP tasks; and (iv) an extensive user-study in four domains with more than 240 users that shows the value and user acceptance of those explanations, as well as their preference of contrastive over counterfactual explanations.The rest of the paper is organized as follows. We first formalize CMAOPs and introduce a novel approach to generate contrastive explanations of solutions to these problems. We evaluate CMAOE on four well-known CMAOPs, showing how it generates explanations in a similar time as the one needed to solve the original problem. Later, we present the results of an extensive user study in four well-known CMAOPs with more than 240 users. After being presented with these explanations, humans' satisfaction with the original solution increases and their desire to complain decreases. Furthermore, the explanations generated by CMAOE are preferred or equally preferred by humans over the ones generated by state of the art approaches. Finally, we draw our main conclusions and outline future work.Centralized Multi-Agent Optimization Problems (CMAOPs) are solved by finding an optimal solution that minimizes (or maximizes) a given objective function from a set of alternatives, taking into account a set of constraints referring to a set of agents. We focus on CMAOPs where the decision-making is centralized, i.e., a central entity solves the optimization problem by considering the agents' preferences and constraints. Many real-world scenarios lie under this framework, such as nurse shift scheduling, task or resource allocation, or logistics planning. CMAOPs are formally defined as follows:Definition 1 A Centralized Multi-Agent Optimization Problem (CMAOP) is a tuple CMAOP = ⟨A, X, C, f, m⟩where A is a set of agents, X is a domain of feasible points subject to set of constraints C, f is the objective function, and m is the goal function which is either min or max.The Mixed Integer Programming (MIP) formulation of CMAOPs is based on an algebraic specification of a set of 130 feasible alternatives, as well as the objective criterion for comparing alternatives. This is achieved by: (i) introducing discrete and/or continuous decision variables; (ii) expressing the criterion as a function of variables; and (iii) representing the set of feasible alternatives as the solutions to a con-135 junction of constraints described as equations and inequalities over the variables. Therefore, MIP provides a general framework for modeling a large variety of CMAOPs such as scheduling, planning, task assignment, network design, etc. A general MIP formulation of a CMAOP is defined below:140 min f (x) s.t. g i (x) ≥ 0 i = 1, ..., q h j (x) = 0 j = 1, ..., pwhere x ∈ X ⊆ R n represents an n-variable decision vector subject to a feasible set X. Let a(x) ⊆ x refer to the subset of decision variables involving agent a ∈ A. One decision variable x could involve multiple agents. The objective function f (x) is composed of two sub-terms: f A (x), a func-145 tion over the subset of decision variables involving agents' inputs; and f G (x), a function over the subset of decision variables not involving any agents' input.The feasible set X is given by the set of constraints in C. These constraints are represented as inequalities (g i ) or 150 equalities (h j ) of functions over the decision vector x.Finally, a maximization problem can be modelled as a minimization problem by multiplying the objective function by (-1). We denote the quality of a solution to a CMAOP as q f (x) . An optimal solution is represented as x * . In the 155 rest of the paper, we will always refer to optimal solutions when we talk about solutions of CMAOPs.Running Example: the Knapsack Problem Let us introduce a Knapsack Problem (KP) as the running example throughout the paper. In KP, each agent from a set of agents 160 owns a few items. Each item occupies a different space, and each agent assigns a different utility value to each item, i.e., how much they appreciate their items. The agents share a common depot with a limited capacity where items can be included. The problem is determining the items to be in-165 cluded in the depot so that the total utility is maximized, while satisfying the depot's capacity and considering some fairness issues. A formal MIP formulation of a KP is shown below. The objective function to optimize is:max a∈A,i∈I xa,i × UTILITY(a, i) + minItems (1)subject to the following constraints:EQUATION(5)There is one binary decision variable x a,i for each agent a ∈ A and item i ∈ I. These variables will take a value of 1 if item i from agent a is included in the depot. Integer decision variable minItems keeps track of the number of items belonging to the agent with the least number of items included in the depot (Constraint 3). The objective function maximizes the utility of the included items, and the number of items belonging to the agent with the least number of items included in the depot. Constraint 2 ensures that the maximum capacity of the depot is not exceeded.In this case, the first term of the objective function corresponds to f A (x), i.e., variables explicitly associated with agents' inputs, while the second term corresponds to f G (x), i.e., other variables not involving agents' inputs.Given that most CMAOPs are over-constrained, optimal solutions do not always satisfy all agents, who might be unhappy and ask questions about the solution. In this paper, we focus on generating local contrastive explanations for questions that take the form of "Why does solution S not satisfy property P ?". The next sections describe how CMAOE works: (i) it builds a hypothetical CMAOP; and (ii) it generates explanations from the comparison of the solutions returned by the original and the hypothetical CMAOP.To generate these explanations, we build a hypothetical optimization problem where property P is forced to be satisfied. This hypothetical problem might generate a solution that is very different from the original one. To prevent this, we further modify the original problem to minimize the number of changes between the original and new solution, S and S ′ .We first define how to compute the differences between two solutions. In many scenarios, the set of decision variables x used to model CMAOPs includes some auxiliary variables that are used to help the modeling process or improve the efficiency when solving the problem. We refer to the subset of decision variables in a CMAOP that actually represent a solution as S ⊆ x. These are the variables considered when computing the differences between two solutions. Going back to our KP running example, while x a,i and minItems are the decision variables of the problem (x), only x a,i variables would be in S, since they are the only ones representing a solution.We formally define a Hypothetical Multi-Agent Optimization Problem (HCMAOP) as an extension of the original CMAOP as follows:Definition 2 A Hypothetical Multi-Agent Optimiza- tion Problem (HCMAOP) is a tuple HCMAOP = ⟨A, X ′ , C ′ , f, m, S, P ⟩, where A is a set of agents, X ′is an updated domain of feasible points subject to the new set of constraints C ′ , f and m remain as in the original OP, S is a solution to the original CMAOP, and P is the hypothetical property to be enforced.We extend the original set of constraints C with a new set of constraints that enforce that the hypothetical property P is satisfied. From now on, we assume HCMAOP is solvable, i.e., enforcing the hypothetical property P might affect quality but not solvability. We also extend the original decision vector x with a new set of decision variables z(S) that will 230 compute the differences between the solution to the original CMAOP (S) and a solution to the new HCMAOP (S ′ ). The value of these new variables is ensured by a set of constraints Z, i.e., C ′ = C ∪ P ∪ Z. Finally, we also modify the original objective function to reason at the same time about 235 the quality of the solution, f (x), and the number of changes between the original and the hypothetical solution, z(S).A general MIP formulation of a HCMAOP is defined as:min αf (x ′ ) + βz(S) s.t. C ′where x ′ ∈ X ′ represents the new decision vector subject to the feasible set X ′ . We introduce two parameters (weights) 240 in HCMAOP's objective function, α and β. By modifying these parameters, we will generate solutions that prioritize either maximizing the quality of the hypothetical CMAOP solution or minimizing the number of changes between the original (S ⊆ x) and the hypothetical (S ′ ⊆ x ′ ) CMAOP 245 solutions. In scenarios where we maximize quality, the solution to the HCMAOP problem might be arbitrarily different from the original solution, thus yielding very long explanations. However, minimizing the number of changes between the original (S ⊆ x) and the hypothetical (S ′ ⊆ x ′ ) CMAOP 250 solutions leads to shorter and more concise explanations. KP running example. Now, agent "Alice" asks why item "bed" has not been included in the optimal CMAOP's solution x * . We build the associated HCMAOP as follows. First, we enforce the agent's property by adding the following con-255 straint, which ensures that the bed is included in the depot. Then we generate a new set of z(S) variables by duplicating the decision variables used to represent the original solution.In this case, we add one z a,i variable for each original x a,i variable. We also add the following constraints to ensure that 260 the z variables capture the changes of the new solution with respect to the original one:x ′ a,i -x a,i ≤ z a,i , x a,i -x ′ a,i ≤ z a,i , z a,i ≥ 0 Finally, we update the objective function:max α a∈A,i∈I x a,i ×UTILITY(a, i)+minItems -β a∈A,i∈I z a,iIn the following, we focus on two main variations of CMAOE: Q-CMAOE, which prioritizes quality by making 265 α ≫ β; and C-CMAOE, which prioritizes the number of changes by making β ≫ α. Both variations still reason about both terms.The complexity of the new HCMAOP compared to that of the original CMAOP relates to how many new con-270 straints and variables need to be added. The number of constraints and variables to add depends on (i) the number of decision variables used to represent a solution in the original CMAOP; and (ii) the hypothetical property P to be enforced. HCMAOP's objective function is more com-275 plex since it also reasons about z(S) variables. However, as we will see later, the hypothetical property P tends to constrain the solution space so that HCMAOPs can be efficiently solved in practice.the level of abstraction we want. Abstract Explanation. The explanation only refers to the difference in the quality of both solutions.Quality Diff = q f (x) -q f (x ′ ) (6) Full Explanation. The explanation refers to the specific changes between S and S ′ , grouping them by agents. Algorithm 1 outlines how this computation is performed. The Algorithm 1: Full Explanation GenerationRequire: HCMAOP = ⟨A, X ′ , C ′ , f, m, S, P ⟩, S ′ Ensure: E 1: EI ← ∅ , ED ← ∅ 2: I = COMPUTEINCREASES(S, S ′ ) 3: D = COMPUTEDECREASES(S, S ′ ) 4: for a ∈ A do 5: Ia = a(I), Da = a(D) 6: EI ← EI ∪ {⟨i, q f (i) ⟩ | i ∈ Ia} 7: ED ← ED ∪ {⟨d, q f (d) ⟩ | d ∈ Da} 8: end for 9: E ← EI ∪ ED 10: return Ealgorithm receives as input the HCMAOP and the solution to the new problem (HCMAOP already contains the solution to the original problem). First, the algorithm computes the subset of decision variables representing a solution whose value 295 has either increased or decreased between the original and the hypothetical solution. This is done by the COMPUTEIN-CREASES and COMPUTEDECREASES functions, which return the set of increase (I) or decrease (D) changes, respectively. Then, the algorithm iterates over the set of agents, computing the subset of increases and decreases where agent a was involved (line 5). After that, it computes the contribution of these changes to the objective function and updates the sets of increases and decreases (lines 6 and 7). Finally, the algorithm returns the explanation E, which is the union of all the decision variables in the solution that either increased or decreased their value in the new solution S ′ with respect to the original solution S.KP running example. Let us assume that the only change between solutions S and S ′ is Bob removing his bed (with a utility of 4) in favour of Alice's bed (with a utility of 2) increasing The Abstract Explanation would be that doing so would mean a loss of 2 utility units. The Full Explanation would be:E I = {⟨x Alice,bed , 2⟩} ∪ E D = {⟨x Bob,bed , 4⟩}.Although our formalization is general to any CMAOP described as a MIP, we run experiments using Mixed Integer Linear Programs (MILP) for which optimal solutions are easier to compute. We evaluate our approach by providing explanations in simulated scenarios in four well-known CMAOPs that can be formulated as MILPs. Below, we provide a brief description of each domain. A formal definition of their associated MILPs can be found in Appendix A.• Knapsack Problem (KP). A variation of our KP running example where the objective function only optimizes the total utility of the items included in the depot. • Task Allocation Problem (TAP). A set of tasks needs to be allocated to a set of agents. Each agent has a maximum workload. Each agent assigns a different utility value to each task. The goal is to assign all the tasks, while maximizing the total utility of the assignment and respecting agents' workload. • Wedding Seating Problem (WSP). A set of agents need to be seated at a set of tables with different capacities. Each pair of agents has an associated affinity value, i.e., how much they would like to be seated at the same table.The AI system's problem is determining the allocation of agents to tables so that the total affinity is maximized while satisfying the tables' capacities. • Capacitated Vehicle Routing Problem (CVRP). A set of agents (vehicles) with heterogeneous capacities have to visit a set of points distributed on a map. The number of points a vehicle can visit is given by its capacity. All agents start and end in a depot. Each pair of points has an associated distance. The AI system needs to determine the route of vehicles so that the total traveled distance is minimized while satisfying the vehicles' capacities.We have generated problems in the four domains by fixing some inputs and general constraints of the problem: the depot's capacity in KP, the tables' capacity in WSP, the number of points and vehicles' capacity in CVRP, and the number of agents in TAP. For each configuration, we have generated 10 CMAOPs with random utilities/affinities/distances depending on the domain. We optimally solved each problem and automatically computed all of the unsatisfied variables, i.e., those decision variables representing the solution with a value of zero. Then, we randomly picked 10 of these unsatisfied variables in order to generate 10 hypothetical properties, i.e., agents' questions about the original solution. For example, in KP we get all of the items that were not included in the depot and generate 10 questions of the form "why was item x not included in the depot?". This yielded 100 HCMAOPs to solve. We can solve each problem with either of the two variations of our approach: Q-CMAOE or C-CMAOE. For each problem, we report (i) the time needed to compute the solution for the CMAOP and the HCMAOP;(ii) the quality of the CMAOP and the HCMAOP; and (iii) the length of the explanation, i.e., the number of changes between the CMAOP and HCMAOP solutions.MILP problems were modeled using the PuLP Python library (Mitchell, OSullivan, and Dunning 2011) and solved using the CBC solver (Forrest and Lougee-Heimer 2005) . Experiments were run in Intel(R) Xeon(R) CPU E3-1585L v5 @ 3.00GHz machines with 64GB RAM and a 60s timeout (including the solving and model-building times). ity of the problem. In KP, we increase the complexity of the problem by increasing the number of agents and setting the depot's capacity to be a function of this number. In TAP, we fix the number of agents and increase the number of tasks to be assigned. In WSP, we also increase the number of agents, fixing the number of tables but varying their size to be able to accommodate all agents. Finally, in CVRP, we increase the number of points, fixing the number of vehicles but varying their capacity to be able to visit all points. All of these problems are solved using Q-CMAOE. Execution times are similar for C-CMAOE.The results of this experiment are shown in Figure 2 . As expected, increasing the complexity of the problems leads to longer solving times and explanation generation times in all domains. However, while generating explanations is notably faster than solving the problem in WSP and CVRP, the opposite occurs in KP and TAP. This is because these problems only have one type of decision variable and only a few types of constraints, while the other domains involve more constraints and interrelated decision variables.We conclude that the time needed to generate an explanation compared to the time needed to generate a solution will vary depending on the problem to be solved and its formulation. However, this time difference does not usually exceed an order of magnitude and remains constant as problems be-405 come more complex. Therefore, our approach will generate explanations for any MILP for which a solution can be generated within reasonable time and memory bounds.We analyze the trade-off between quality and explanation 410 length by comparing our two approaches and measuring: (i) Explanation Length -the number of changes between the original and hypothetical solutions, |E|; and (ii) Suboptimality Ratio -the quality of the original vs. the hypothetical solution, q f (S) /q f (S ′ ) . The results of this experiment are shown in Figure 3 for the smaller problems in all domains, i.e., 10 agents in KP, 10 tasks in TAP, 8 agents in WSP and 8 points in CVRP. Conclusions drawn from bigger problems are the same, and their results are shown in Appendix B.As expected, optimizing the quality of solution S ′ first (Q-CMAOE) yields solutions closer to the optimal one S (lower Suboptimality Ratios) at the expense of generating a new solution S ′ with more changes (higher Explanation Length). On the other hand, minimizing the number of changes between S and S ′ first (C-CMAOE), generates shorter explanations at the expense of having slightly worse solutions in terms of quality. Despite this trend, we often get the same Suboptimality Ratio and Explanation Length regardless of the approach used. From 100 problems generated for each domain, we obtain the same values in 67 problems in KP, 30 in TAP, 39 in WSP, and 9 in CVRP. When focusing on problems for which we obtain similar rather than exact values, there are 77 problems in KP, 30 in TAP, 49 in WSP, and 33 in CVRP for which the Suboptimality Ratio and Explanation Length values differ by less than 30%. These results show that, in most cases, there are no big differences in the solutions produced by both approaches.We designed and implemented a between-subjects user study to validate CMAOE. In the following subsections, we detail the setup, results and analysis.We generated abstract and full explanations using Q-CMAOE. We chose this variation given the similar results both approaches got in the previous section, while Q-CMAOE generates solutions with slightly higher quality. We compared these explanations against a baseline explanation. The objective of the baseline is to demonstrate that our explanation was the determining factor in the users' behavior, rather than simply providing any explanation. This is necessary based on the findings in (Kosch et al. 2023 ) that demonstrated the placebo effect in AI experiments. In particular, in this user study, we used "Sorry, this is what the algorithm generated" as a baseline explanation. We wanted to validate the following hypotheses: Hp1: CMAOE's explanations improve humans' satisfaction with the decisions of the AI system. Hp2: CMAOE's explanations reduce humans' desire to complain about the decisions of the AI system.Hp3: Humans prefer more detailed explanations.This experimental setting just focuses on assessing whether our contrastive explanations improve humans' satisfaction and decrease their desire to complain or not.The evaluation of CMAOE against other state of the art approaches is discussed in detail in User Study 2.By considering the four domains discussed in previous section and the three types of explanation, we generated twelve scenarios. We force the original solution to be very unfavourable for the participants so they have a reason to complain. In each scenario, participants were asked (i) their user satisfaction for the solution generated by AI, and (ii) their desire to make a complaint regarding that solution. The answers to both questions were measured on a 5-point Likert scale, where 1 represents the lowest and 5 is the highest. Then, in each scenario, regardless of the level of satisfaction or their desire to complain, the participants were presented with one of the three different types of explanations.Afterward, the same set of questions was repeated in order to compare the participants' satisfaction and desire to complain before and after receiving the explanation. Each user was asked to rate their satisfaction with the explanation on a Likert scale. Finally, we asked a domain-related question to verify the users' comprehension of the domain; e.g. in KP, asking what the goal of the AI algorithm was.We recruited 207 computer science students, 75 females and 132 males. The average age was 24.75 (std=3.54). Each participant was shown 2 or 3 scenarios randomly, ensuring that no domain or explanation type was repeated. We discarded 34 scenarios where users answered the verification question incorrectly, leading to 100, 85, 76 and 84 scenarios examined for the KP, WSR, CVRP and TAP domains, respectively. We used repeated measures ANOVA (General Linear Model) for each domain separately.In the first part of the user study, we evaluate Hp 1 and Hp 2 .Table 1 shows the number of users (N ) who participated in each scenario (distinct pairs of domain and explanation type). Further, it presents the mean and standard deviation of user satisfaction with the solution and their desire to complain. Based on the table, in all domains, the initial satisfaction of the users with the solution was similar among all users with different explanations (p > 0.05). This is a good indication of our randomized distribution of the users between all sessions since, at the initial stage, no explanation 505 was presented to the users. From a post-hoc analysis with correction for multiple measurements in all domains, the level of satisfaction after receiving the explanation is still low. This is because the original solution was very unfavourable for the participants, and CMAOE just tries to explain the outcome rather than changing it. Despite the general low satisfaction level, we can observe that the increase in user's satisfaction level was significantly greater following the abstract and full explanations compared to the baseline explanation. For more details 515 about the main and interaction effects, an ANOVA analysis is described in Appendix D.The results presented in this table confirm Hp1, i.e. the explanations generated by CMAOE improve humans' satisfaction regarding decisions made by the AI system.Finally, from a post-hoc analysis with correction for multiple measurements in all domains, the decrease in desire to complain was significantly greater following the abstract and full explanations compared to the baseline explanation.Similarly, an ANOVA analysis of the results is shown in Appendix D. The results presented in this table confirm Hp2, that the generated explanations by CMAOE decrease humans' desire to complain regarding decisions made by AI.In this part of the study, we validate our third hypothesis, Hp 3 . The results in Table 2 present a between-subjects analysis comparing the satisfaction between the users in each of the explanation types, using Univariate Analysis of Variance. In all domains, we found an effect for the type of explanations on user satisfaction. The F-score and p-value were; KP(F (2) = 19.52, p ≪ 0.01), WSP (F (2) = 14.62, p ≪ 0.01), CVRP (F (2) = 10.64, p ≪ 0.01) and TAP (F (2) = 6.9, p < 0.01). In general, in all domains, users reported higher satisfaction with the abstract and full explanations rather than the baseline explanation. In CVRP and WSP, users were significantly more satisfied with the full explanation in comparison to the abstract explanation. However, their satisfaction with the abstract and full explanations was much closer in the KP and TAP domains. We hypothesize this is because KP and TAP are much simpler domains in comparison to CVRP and WSP. The results of Table 2 confirm Hp3 -users prefer a more detailed expla- nation. These results are aligned with previous works on social sciences and marketing (Ramon et al. 2021) .User Study 2: Contrastive vs Counterfactual 550In this user study, we compare the contrastive explanation generated by CMAOE with the counterfactual explanation generated by (Korikov and Beck 2021) (will be referred to as KORIKOV21). To the best of our knowledge, this is the closest state-of-the-art approach that can address OPs.For this comparison, full explanations by Q-CMAOE is compared against the KORIKOV21 explanations for KP and WAP domains. As discussed in Related Work, the KO-RIKOV21 can generate counterfactual explanations highlighting a set of hypothetical facts that would have satisfied user's desired chracteristics. Such hypothetical facts are a set of changes that the user could have done in order to get their desired chracteristics. The KORIKOV21 is restricted to specific optimization formulation where the preferences of each user can only be reflected in the objective function and not in the constraints. TAP does not fit this formulation, thus KO-RIKOV21 cannot generate explanations for this domain. In the case of CVRP, the counterfactual explanations would include suggestions to change the distance between the points on the map. From a practical point of view such suggestions are not actionable and realistic and this has been the reason that we did not include this domain in the user study.For KP and WAP domains, we have generated four sceanrios were at each scenario the initial part of User Study 1 was repeated. At each sceario, each particpant was asked to rate on a 5-point Likert scale, their satisfaction and desire to complain regarding the unfavourable solution for each domain. Regardless of the level of satisfaction or their desire to complain, the partcipants were presented with one of the explanations generated by either CMAOE or KORIKOV21. Afterward, the same set of questions was repeated. At the end of each scneario, participants were asked to rate on a 5-point Likert scale the statements presented in Appendix D regarding explanations. These are metrics adapted from standard ones (Hoffman et al. 2018) . Below are the hypotheses that we wanted to test in this user study.Hp1: CMAOE's explanations improve humans' satisfaction more than KORIKOV21's explanations.Hp2: CMAOE's explanations reduce humans' desire to complain more than KORIKOV21's explanations.Hp3: CMAOE's explanations lead to higher scores on explanation goodness metrics than KORIKOV21's explanations.For this user study, we recruited 40 computer science students or graduates, 10 females and 30 males, average age 27.9 (std=7.27).THe first part of the user study evaluates Hp1 and Hp2. Table 3 presents the number of users (N ) and the mean and standard deviation of user satisfaction with the solution and their desire to complain. From a post-hoc analysis with correction for multiple measurements, the decrease in the desire to complain in the KP domain was significantly greater following explanations generated by CMAOE compared to the ones generated by the KORIKOV21 (p < 0.05). However, this decrease was not significant for the WAP domain. A detail ANOVA analysis of these results is presented in Appendix E.These results confirm Hp1, however Hp2 is partially satisfied as humans prefer or equally prefer the explanations generated by CMAOE in comparison to the ones generated by KORIKOV21.Using a Univariate Analysis of Variance, we analysed the results of the user study comparing the users' satisfaction with the two types of explanations, using a set of statements adopted from (Hoffman et al. 2018) . The set of statements and the results are presented in detail in Appendix F. The statistical test was performed with a significance level of 0.05. Based on this, for the Knapsack domain, we found a significant effect for the type of explanation in each of the statements we asked (p ≪ 0.05). On the other hand, in the WAP domain, despite CMAOE explanations got higher value scores than the KORIKOV21, their difference were not statistically significant. These results confirm Hp3, where we assumed the participants prefer CMAOE's explanations to KORIKOV21's ones.Most works on generating explanations for optimization models focus on explaining infeasibility, often through identifying a minimal (Parker and Ryan 1996; Chinneck 2007) or user preferred (Junker 2004 ) set of constraints that should be relaxed to get a solution. More recent works also cover optimality in their explanations using different approaches. (Korikov, Shleyfman, and Beck 2021; Korikov and Beck 2021) propose to use counterfactual explanations for OPs. Given a set of facts and a solution that does not satisfy some desired features, they solve an inverse optimization problem to generate explanations in the form of a hypothetical set of facts that would have satisfied the users' characteristics. Their setting is similar to ours, allowing an individual to inquire about any change to a decision that can be represented with a constraint set on the original formulation. However, while their explanations involve hypothetical features or facts that would yield the user desired output, our explanations highlight the losses incurred in satisfying users' characteristics. Another difference is that their explanation focuses only on the individual asking the question, while our explanation focuses on the rest of the agents involved in the optimization problem. On the experimental side, they limit their evaluation to simulations in two well-known domains, but do not test the validity and usefulness of their explanations with user studies as we do here.Other literature focuses on contrastive explanations. Cyras et al.(2019) explain schedules using argumentation frameworks. In order to provide the explanations, they manually generate the attack graphs, i.e., the relationship between the preferences and the assignments, while we do not need any external input other than the original model and the user's request. A key difference between these works and ours is that they are restricted to makespan scheduling problems with a limited number of preferences, while our approach can provide explanations for any CMAOP. On the evaluation side, they do not report any experiments. Pozanco et al. (Pozanco et al. 2022) proposed the EXPRES framework, which also focuses on explaining why the original solution is better than one where the user inquiry is satisfied. However, they: (i) are restricted to linear programs 670 where a totally ordered set of preferences is defined; (ii) need external inputs as in (Cyras et al. 2019) ; and (iii) only conducted experiments in a workforce scheduling domain, where they measured whether humans preferred explanations generated by other humans or those generated by EX-675 PRES. In this paper, we have conducted experiments in many different CMAOPs, showing how humans' satisfaction with the original solution increased after receiving the explanations generated by CMAOE.More recently, (Vasileiou, Xu, and Yeoh 2023) proposed 680 QUERIES, a logic-based explanation generation framework that produces both reason-seeking (contrastive) and modification-seeking (counterfactual) explanations that optimize for privacy. In their evaluation, the authors prove that individuals prefer explanations containing only public infor-685 mation, i.e., constraints and preferences known by all agents, over explanations including private information. However, they do not compare, as we do in this paper, whether individuals prefer contrastive or counterfactual explanations.We have introduced CMAOE, a domain-independent approach to generating contrastive explanations of multi-agent optimization solutions. We generate explanations by building a hypothetical optimization problem that (i) forces the user's requested property to be satisfied; and (ii) minimizes 695 the number of changes between the original and the hypothetical solution. Experimental results through a computational evaluation show how CMAOE can scale in generating contrastive explanations for CMAOPs. Finally, an extensive user study in different CMAOPs shows that expla-700 nations generated by CMAOE (i) increase humans' satisfaction with the original solution and decrease their desire to complain; and (ii) humans prefer the contrastive explanations generated by CMAOE over the counterfactual explanations generated by state of the art approaches.Currently, we are only providing one explanation. However, HCMAOPs often have a few optimal solutions. In future work, we would like to characterize each of these solutions to present a set of diverse explanations from which users could choose. Also, we would like to extend CMAOE 710 to consider agents' privacy or fairness. 
 
 Appendix:  


Decision: This paper introduces a technique for generating contrastive explanations of centralized multiagent optimization problems. It draws inspiration form earlier work in generating similar explanations for planning problems, and given an optimal solution, generates explanations of the form: “Why does solution S not satisfy property P? The approach is formulated in terms of an Integer Linear Program (ILP) solver and is evaluated over 4 traditional ILP problems. A computational study to analyze objective performance and multiple user studies to evaluate subjective effects are performed and reported. Major results show that humans’ satisfaction with the original solution increases after being presented with explanations and that explanations generated by the proposed approach are preferred by humans over other state of the art approaches.

Strengths: The paper adapts the idea of generating counterfactual explanations for planning problems to a different class of larger, multiagent optimization problems and establishes its broader applicability. The utility of the proposed technique is validated through extensive user studies. User studies are also used to validate how explanation length affects how the user perceives the explanation. Finally, the paper is well-written and mostly easy to follow.

Weaknesses: First, the paper does not clearly define what is meant by the term “centralized multiagent optimization problems”. The 4 problems considered in the experimental analysis are classical combinatorial optimization problems, but in what sense are they multiagent problems? From comments in the discussion, you seem to be referring to scheduling and allocation problems that involve assignment of resources (agents) to tasks over time. But this problem class is never explicitly defined, and this adds unnecessary confusion to the paper’s focus. More importantly, the paper does not do a good job of characterizing the unique challenges associated with applying contrastive explanations to this different class of problems. Why are these problems different and/or more difficult to explain than planning problems? The paper needs to better motivate the significance of the work and its contribution. Second, some of material needed to fully understand the paper is contained only in the appendices that were provide as supplementary materials and this detracts considerably from the paper’s comprehensibility in different spots. The author(s) responses to reviewer questions indicate their intention to move information essential to the paper’s claims and arguments into the paper itself, as well as provide a running example that shows what types of explanations are generated and considered in the user studies. Such revisions are seen as necessary for the paper to be accepted. Finally, the paper is missing any comparison with other contemporary explanation techniques that have carried out user studies. Minimally these should be mentioned when discussing related work.

Reviews: review: strength_weakness: strength_weakness: - experiments are done only with synthetic problems
questions: questions: 1 -  In the following paragraph it seems that is missing the formal constraint.

"First, we enforce the agent’s property by adding the following constraint, which ensures that the bed is included in the depot."

2 - I missed in the paper the concrete explanation given to the user. Only by checking in the Supplemtary Material I could find such a information. 
For example, abstract information will always be: 'Total utility would decrease'?

Also, it would be good to have the concrete explanation given my the Korikov21 method.

3 - In the objective function after line 260, it seems that x_{a,i} should be x'_{a,i}.

4 - In some parts of the paper, WSP is misspelled WAP.
strength_weakness: strength_weakness: I have two questions/issues with the paper --

(1) The paper is motivated towards multi-agent scenarios, which should mean that there is parallelism and concurrency between various agents in the scenario. The explanations should be oriented towards the multi-agent scenarios (or multi-agent oriented properties). However, in the current case the evaluation of scalability, quality and the user study is about whether some property changes and the explanation is provided. The properties are about specific parts of the solution and has no relevance to multi-agents. The problem solution is centralized, the explanation and to some extent the domains have no relation to the multi-agent scenarios either. It also follows the template of contrastive explanation which is one solution compared with another solution generated after constraining based on the property queried by the user. Thus, I am not sure what is the use of multi-agent optimization problems.
(2) Currently, the work needs more detail for the user study, most importantly the procedure followed to conduct the user study. It's unclear what was shown to the user, what properties they could question, how was the interface, etc. These details are necessary in the main paper in order to understand what was the real user study. Does it really gives the results for user satisfaction or not.

Other suggestions --
(2) The paper is missing comparison with other explanation related user studies that have been conducted. You do cite the Krarup's paper [1], but have no comparison as to why your contrast based explanation are different. In the current state I believe your work is just another way of implementation of the template for contrastive explanation. You also need to compare whether there technique can work for you, and if so then how does your solution strategy differ, and what novelty it brings to the table. You also miss the user study in [2]. I would love to see your work in compared and contrasted to user study specific papers as well. They should also be discussed in related work.

References --
[1] Krarup, B., Krivic, S., Magazzeni, D., Long, D., Cashmore, M. and Smith, D.E., 2021. Contrastive explanations of plans through model restrictions. Journal of Artificial Intelligence Research, 72, pp.533-612.
[2] Chakraborti, T., Sreedharan, S., Grover, S. and Kambhampati, S., 2019, March. Plan explanations as model reconciliation--an empirical study. In 2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI) (pp. 258-266). Ieee.
questions: questions: (1) Are there any limitations what kind of explanation properties the user can query about. Can all the property be easily converted to representable constraint set?
(2) The domains look a lot more combinatorial problems, instead of planning problems. Was that intentional? If so, compared to [1] (in Weakness section) is your solution approach more generic or more specialized. What is the difference in application of your approach to the paper that inspired the approach.
strength_weakness: strength_weakness: Below are some of the questions and comments I had about the paper (I will also repeat them in the question section)

Evaluation - While I applaud the authors' decisions to run user studies to evaluate the method. Seeing that the evaluation was just focused on a subjective metric is a bit of a missed opportunity. It is usually better to evaluate both subjective aspects regarding the method (acceptance, preference, etc..), along with the objective measures like how well the explanation may help the user better understand the task or help improve their ability to complete the task or make better decisions. I would highly encourage the authors to look at [1] for more guidelines on evaluating explanation generation methods.

Explanations themselves - It seems the explanations provided here actually compare the values taken by decision variables. This somehow implies the agents have access to and can understand the MIP encoding being used here. This doesn’t seem very realistic. While it works in these simpler problem settings, I would imagine more complex problems may require more involved compilations with multiple non-obvious decision variables. How well would an agent who is not an expert in MIP compilations be able to make sense of such explanations?

Distance measures and properties - Finally, it seems the paper currently focuses on a rather simple distance measure, namely the difference in values. I would imagine there are cases where similarity or dissimilarity of solutions could involve more complex notions (for example, there may be some qualitative notions of similarity, like how certain agents are favored over others, which might be hard to capture through just the difference in the value of individual variables). Also, I am assuming the fact that properties need to be encoded into MIP also constrains the kind of questions the user can ask.

On a smaller note/question, how important is the fact that this is a multi-agent optimization problem? Would any algorithmic mechanism change if it were a traditional optimization problem?

[1] Hoffman, Robert R., et al. "Metrics for explainable AI: Challenges and prospects." arXiv preprint arXiv:1812.04608 (2018).
questions: questions: Please respond to my assertions about

1. Whether an agent receives the explanation needs to understand the compilation
2. The limits on the kinds of similarity supported by the method
3. The limits on the kind of properties and, by extension, the questions that can be asked by the user.

I would also appreciate a response on the question regarding the need for multiple agents, but it is not a requirement