On the Complexity of Decision Making in Possibilistic Decision Trees

Hélène Fargier, Nahla Ben Amor, Wided GuezguezUAI 2011

TL;DR

This paper investigates the computational complexity of finding optimal strategies in possibilistic decision trees. It establishes that while many possibilistic decision criteria allow for efficient, polynomial-time solutions using dynamic programming, others, like possibilistic Choquet integrals, lead to NP-hard problems. This work clarifies which possibilistic decision-making frameworks are computationally feasible for complex sequential decisions.

What Problem Does This Paper Address?

Decision-making under uncertainty is a fundamental problem in artificial intelligence. When uncertainty can be precisely quantified using probabilities, the expected utility (EU) framework and dynamic programming provide efficient ways to find optimal strategies in sequential decision problems, often represented as decision trees. However, in many real-world scenarios, precise probabilistic quantification is difficult or impossible. Possibility theory offers an alternative for representing uncertainty, but it requires new decision criteria beyond the standard EU model. This paper addresses the crucial question of computational complexity: for various possibilistic decision criteria, can we efficiently find optimal strategies in sequential decision trees, or are these problems computationally intractable?

Methods

The paper extends the concept of decision trees and strategies from probabilistic settings to possibilistic ones. A key technique is the "reduction" of compound lotteries (representing complex strategies) into equivalent simple lotteries. This reduction, using min and max operations, is polynomial in the size of the strategy. The core of the analysis lies in examining whether different possibilistic decision criteria satisfy a "weak monotonicity property." This property is crucial because it allows for the application of dynamic programming, a powerful algorithmic technique that works backward from the end of the decision tree to find an optimal strategy in polynomial time. The authors formally define this property and then analyze several possibilistic decision criteria:

  • Possibilistic Qualitative Utilities (Upes, Uopt, PU): These criteria are shown to satisfy weak monotonicity, making them amenable to polytime dynamic programming.
  • Possibilistic Likely Dominance (LN, LI): These criteria also satisfy weak monotonicity, leading to polytime solutions.
  • Possibilistic Choquet Integrals (ChN, ChΠ): These criteria are demonstrated not to satisfy weak monotonicity. Through counterexamples and theoretical analysis, the paper proves that optimizing strategies under these criteria is NP-hard.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Monotonicity is Key: The paper highlights that the "weak monotonicity property" is the critical factor determining whether dynamic programming can be efficiently applied to find optimal strategies in possibilistic decision trees.
  • Qualitative vs. Quantitative Trade-offs: While qualitative possibilistic criteria (like Upes, Uopt) and some comparative ones (like likely dominance) are computationally tractable, more quantitative, compensatory criteria (Choquet integrals) introduce significant computational complexity.
  • NP-Hardness of Choquet Integrals: A significant finding is that optimizing decisions using possibilistic Choquet integrals is NP-hard, implying that for large decision trees, finding an exact optimal strategy might be computationally infeasible.
  • Extension to Order of Magnitude: The paper successfully extends the analysis to Order of Magnitude Expected Utility (OMEU), showing it also satisfies weak monotonicity and thus can be solved efficiently.

Key Results

  • Polynomial-time solvability: Strategies for possibilistic decision trees using qualitative utilities (Upes, Uopt, PU) and likely dominance (LN, LI) can be found in polynomial time with respect to the tree size.
  • NP-Hardness: The problem of finding an optimal strategy for possibilistic decision trees using possibilistic Choquet integrals (ChN, ChΠ) is NP-complete.
  • Algorithm 1: A general dynamic programming algorithm is presented that works for any criterion satisfying the weak monotonicity property.

Limitations and Future Work

  • Choquet Integral Complexity: While the paper proves NP-hardness for possibilistic Choquet integrals, it notes that the computation of the Choquet value itself is polynomial. However, for more complex scenarios (e.g., multi-prior expected utility), the problem might become even harder.
  • Extension to Influence Diagrams: The authors suggest that their findings for decision trees can be extended to possibilistic influence diagrams, particularly for the Choquet integral case, which would likely involve developing direct evaluation algorithms.
  • Practical Implications: The paper lays the groundwork for understanding the computational feasibility of different possibilistic decision-making approaches, guiding practitioners on which methods are scalable for real-world problems.

Summary updated

BibTeX
@inproceedings{fargier2011complexity,
  author = {Hélène Fargier and Nahla Ben Amor and Wided Guezguez},
  title = {{On the Complexity of Decision Making in Possibilistic Decision Trees}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure