A Reduction of the Complexity of Inconsistencies Test in the MACBETH 2-Additive Methodology

Brice Mayag, Michel Grabisch, Christophe LabreucheADT 2011 · DOI

TL;DR

This paper tackles the computational burden of checking for inconsistencies in decision-making models that use 2-additive capacities. They propose a method to significantly reduce the number of comparisons needed by focusing only on "binary actions" directly related to the decision-maker's stated preferences, making complex decision analysis more tractable.

What Problem Does This Paper Address?

Multi-Criteria Decision Aid (MCDA) methods aim to help decision-makers (DMs) choose the best option from a set of alternatives, considering multiple, often conflicting, criteria. The MACBETH 2-additive methodology, a sophisticated MCDA approach, uses 2-additive capacities to model preferences, allowing for interactions between pairs of criteria. A crucial step in this methodology is ensuring the consistency of the DM's stated preferences. This consistency check, particularly the "MOPI property," can become computationally very expensive as the number of criteria grows, requiring comparisons across many combinations of criteria. The paper addresses the challenge of making this inconsistency test more efficient, especially when dealing with a large number of criteria, by reducing the complexity of the required checks.

Methods

The core of the paper's contribution lies in simplifying the inconsistency test for 2-additive capacities. Traditionally, checking the MOPI property involves examining all subsets of three criteria. The authors propose to limit this test to a specific, smaller set of "binary actions." These binary actions are fictitious alternatives representing specific scenarios: one where all criteria are neutral, others where a single criterion is satisfactory and the rest are neutral, and finally, those where two specific criteria are satisfactory and the rest are neutral.

The paper introduces a new relation, M', which extends the monotonicity relation on these binary actions. They then define a reduced set of binary actions, B', which includes all binary actions directly involved in the DM's stated preferences (strict preferences or indifference). The key result is Proposition 1, which states that an ordinal information is representable by a 2-additive Choquet integral if and only if two conditions are met:

  1. A specific combined relation (PUIUM') on B' contains no strict cycles.
  2. The MOPI conditions, when restricted to elements within B' and using paths within B', are satisfied.

This effectively shifts the burden of inconsistency checking from all possible combinations of criteria to a much smaller, relevant subset of binary actions.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and proposes a method that would be applied to real-world decision problems, but it does not present empirical evaluations on specific datasets.

Key Insights and Ideas

  • Focusing on Relevance: The most significant insight is that not all possible comparisons are equally important for detecting inconsistencies. By identifying "binary actions" that are directly linked to the DM's stated preferences, we can significantly prune the search space for inconsistencies.
  • The Power of Binary Actions: The paper demonstrates how carefully constructed "binary actions" can encapsulate the essential information needed to verify the 2-additive capacity model. These actions act as proxies for more complex preference structures.
  • Reduced Complexity, Same Guarantee: The proposed method achieves a substantial reduction in computational complexity while retaining the guarantee of detecting all inconsistencies, which is a critical balance for practical application.
  • Extending Monotonicity: The introduction of the M' relation is a clever way to extend the notion of monotonicity to the reduced set of binary actions, enabling the simplified inconsistency test.

Key Results

The paper's main result is Proposition 1, which provides a necessary and sufficient condition for the representability of an ordinal information by a 2-additive Choquet integral. This condition is based on the absence of strict cycles in a combined relation on a reduced set of binary actions (B') and the satisfaction of MOPI conditions restricted to B'. This proposition effectively offers a computationally less demanding way to test for inconsistencies in the DM's preferences within the MACBETH 2-additive framework. The paper also provides lemmas and proofs that support this proposition, showing how the extended monotonicity relation and the reduced set of binary actions are sufficient for the inconsistency test.

Limitations and Future Work

The paper acknowledges that the proposed method is applicable when the DM can provide preferential information on the set of binary actions. It doesn't explicitly discuss scenarios where this information is incomplete or difficult to obtain. The paper focuses on the theoretical reduction of complexity for the MOPI test. Future work could involve developing practical algorithms to implement this reduced test and evaluating its performance on real-world decision problems with a large number of criteria. Further research could also explore extending this complexity reduction to higher-order additive capacities.

Summary updated

BibTeX
@inproceedings{mayag2011reduction,
  author = {Brice Mayag and Michel Grabisch and Christophe Labreuche},
  title = {{A Reduction of the Complexity of Inconsistencies Test in the MACBETH 2-Additive Methodology}},
  booktitle = {ADT},
  year = {2011},
  doi = {10.1007/978-3-642-24873-3\_14},
}
Figure