Introduction
In the field of Multi-Criteria Decision Making (MCDM), additive utility models are the standard for ranking options based on multiple attributes. By assigning weights to features—such as price, quality, or distance—and summing their values, these models provide a powerful way to determine preference. However, these models often function as "black boxes." When an AI system recommends one option over another, it typically justifies the decision with a numerical score. This quantitative output lacks the qualitative, logical structure that humans use to reason through complex choices.
This paper addresses the gap between numerical decision models and human-readable explanations. Drawing inspiration from Benjamin Franklin’s "Moral Algebra"—a method of decision-making involving the cancellation of pros and cons of equal weight—the authors formalize a symbolic reasoning framework. They introduce "Cancellative Argument Schemes" that provide a rigorous, step-by-step logical justification for preferences, ensuring these justifications align perfectly with established decision theory.
Methodology: Cancellative Argument Schemes
The researchers propose a formal method to infer new preferences from a set of existing ones using a "cancellation" principle. If a specific attribute value appears on the "better" side of one preference statement and the "worse" side of another, they can be canceled out. This allows for the aggregation of multiple statements to reach a new conclusion.
The paper defines two primary types of schemes:
- Syntactic Schemes: These include every logical step in the reasoning process, providing a complete trace of the inference.
- Elliptic Schemes: These streamline the argument by omitting "dominance" facts—logical certainties such as "a 4-star hotel is better than a 2-star hotel"—to make the explanation more concise for the reader.
To determine if a preference can be inferred from a given set of statements, the authors utilize Linear Programming (LP). They demonstrate that checking the validity of a preference is a matter of solving a specific linear program, which makes the basic inference task computationally efficient (polynomial time).
Key Insights and Theoretical Equivalence
The most significant contribution of this work is the Equivalence Theorem. The authors prove that their symbolic cancellation method is mathematically identical to the "necessary preference relation" found in additive utility models. Specifically, if a preference holds for every possible set of weights within a linear model, there is a guaranteed cancellation-based argument to prove it. This bridges the gap between robust decision theory and symbolic logic, allowing AI to explain "necessary" preferences in a human-readable format.
However, the research also reveals a fundamental tension in Explainable AI (XAI): Inference is easy, but explaining is hard. While an AI can quickly determine if a preference exists using LP, finding the shortest or most elegant explanation is NP-complete. This suggests that as decisions become more complex, finding a concise argument that a human can easily digest becomes a significant computational challenge.
Furthermore, the authors note that "repetition matters" in symbolic logic. Some valid inferences can only be explained if the conclusion is repeated multiple times within the logic (e.g., demonstrating that two instances of Statement A combined with Statement B imply two instances of the Conclusion).
Results and Complexity Analysis
- Theorem 1 (Equivalence): Establishes that the set of preferences reachable via cancellation is identical to the robust preferences of additive value models.
- Polytime Inference: Confirms that determining the validity of a preference statement can be achieved in polynomial time through conical decomposition and LP.
- Theorem 4 (Complexity): Establishes that finding a minimal-length explanation (the fewest number of premises) is NP-complete, using a reduction from the "Vertex Cover" problem.
Limitations and Future Directions
While this framework provides a robust foundation for explainable MCDM, it currently operates under the additivity assumption, meaning it assumes attributes are independent. It does not yet account for interactions between features—for instance, a traveler might only value a hotel pool if the destination has a hot climate. Future work will explore "Generalized Additive Models" (GAI) to address these dependencies.
Additionally, the study focuses on the formal logic of explanations rather than their psychological impact. Future user studies are required to determine if humans find these cancellation tables more intuitive than other formats. Finally, the current model assumes that the initial preferences provided by a user are consistent; extending the framework to handle contradictory or inconsistent input remains an open area for research.
Summary updated