Explaining Multi-Criteria Decision Aiding Models with an Extended Shapley Value

Christophe Labreuche, Simon Fossier

Introduction

In high-stakes domains such as maritime surveillance or medical diagnostics, Multi-Criteria Decision Aiding (MCDA) models are essential for synthesizing complex, often conflicting data into actionable insights. However, as these models grow in complexity, they frequently become "black boxes," making it difficult for human operators to understand the rationale behind specific automated decisions. This lack of transparency can hinder trust and effective human-machine collaboration.

This paper, originally presented at IJCAI-18, addresses this challenge by introducing a mathematically rigorous framework for explaining decisions in hierarchical MCDA models. The authors propose the Extended Owen (EOw) value, a novel influence index that quantifies the contribution of individual criteria within a nested decision structure.

The Challenge of Hierarchical Decision Logic

Real-world decision-making is rarely flat. Instead, it follows a hierarchical structure where high-level concepts are derived from lower-level technical data. For instance, in a maritime patrol scenario, a ship's "Priority Level" might be determined by its "Suspicion Level" and "Kinematics." These, in turn, are calculated from sub-criteria like sensor inconsistencies or current speed.

Hierarchical structure of a decision model where nodes represent aggregated criteria and leaves represent base inputs.

Existing explanation methods, such as the standard Shapley value, often struggle with these structures because they assume a flat list of independent factors. Furthermore, many existing methods are unstable—small fluctuations in input data can lead to drastically different explanations—and fail to account for redundancies or complementarities between criteria.

Methodology: The Extended Owen (EOw) Value

The authors adopt an axiomatic approach to define an ideal influence index. They identify six essential properties, including Additivity (ensuring the influence of a sum of utilities equals the sum of their individual influences) and Efficiency (ensuring the total influence sums to the total score difference). They prove that the EOw value is the unique index satisfying all these axioms.

Technical Innovations

To adapt game-theoretic concepts to tree structures, the researchers introduced two key innovations:

  1. Admissible Orderings: Unlike the standard Shapley value, which considers all permutations of players, the EOw value only considers permutations that respect the tree's hierarchy, ensuring that "sibling" nodes are grouped together.
  2. Tree Reduction: To overcome the exponential complexity typical of Shapley-style calculations, the authors developed a "pruning" technique. This allows the algorithm to collapse irrelevant branches into single nodes when calculating the influence of a specific leaf, significantly reducing the computational burden.

Evaluation and Results

The method was evaluated using a synthetic maritime patrol scenario and a large-scale performance test involving 25,000 randomly generated decision trees.

Computational Efficiency

A major contribution of this work is demonstrating that rigorous explanations can be generated in real-time. Despite the theoretical NP-hardness of such calculations, the tree-reduction optimization proved highly effective.

Quantiles of computation time (in seconds) for the EOw value across varying numbers of criteria (n).

As shown in the performance data, for models with 31-40 criteria, the median computation time was approximately 35 milliseconds. Even for complex models with 100 criteria, the calculation took roughly 1.2 seconds, making it suitable for interactive user interfaces.

Qualitative Accuracy and Stability

In the maritime example, the EOw index demonstrated superior qualitative performance compared to older methods. It correctly identified redundant sensors—assigning them zero influence when they provided no new information—and maintained continuity, ensuring that explanations remain stable even as input data changes slightly.

Conclusion

The Extended Owen value provides a unique, stable, and efficient solution for explaining hierarchical decision models. By bridging the gap between complex mathematical aggregation and human-understandable explanations, this work paves the way for more transparent and trustworthy automated decision systems. Future research may focus on further optimizing these calculations for specific aggregation functions and conducting user studies to measure the impact on human decision-making performance.

Summary updated

Abstract

The capability to explain the result of aggregation models to decision makers is key to reinforcing user trust. In practice, Multi-Criteria Decision Aiding models are often organized in a hierarchical way, based on a tree of criteria. We present an explanation approach usable with any hierarchical multi-criteria model, based on an influence index of each attribute on the decision. A set of desirable axioms are defined. We show that there is a unique index fulfilling these axioms. This new index is an extension of the Shapley value on trees. An efficient rewriting of this index, drastically reducing the computation time, is obtained. Finally, the use of the new index is illustrated on an example.
BibTeX
@inproceedings{labreuche2018explaining,
  author = {Christophe Labreuche and Simon Fossier},
  title = {{Explaining Multi-Criteria Decision Aiding Models with an Extended Shapley Value}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/46},
}
Figure