Multi-Objective Influence Diagrams with Possibly Optimal Policies

Radu Marinescu, Abdul Razak, Nic Wilson

Abstract

Multi-objective decision-making often suffers from a "solution explosion" where the number of Pareto-optimal policies becomes unmanageable for decision-makers. This paper introduces the concept of possibly optimal policies—those that are optimal under at least one scenario consistent with a user's imprecise tradeoffs. We propose MOVE (Multi-Objective Variable Elimination), an algorithm that leverages these tradeoffs to prune the search space more aggressively. Our evaluation on random influence diagrams shows that MOVE significantly reduces the number of candidate solutions and enhances computational scalability compared to traditional Pareto-based methods.

Introduction: The Challenge of Multi-Objective Decisions

In complex decision-making environments, agents must often balance multiple competing objectives, such as efficacy, risk, and cost. Influence Diagrams (IDs) are a standard graphical tool for modeling such decisions under uncertainty. When extended to multiple objectives (MOIDs), the standard approach is to identify "Pareto optimal" solutions—policies that are not strictly dominated by any other.

An example of a Multi-Objective Influence Diagram (MOID) for oil drilling, featuring multiple utility vectors.

However, as the number of objectives increases, the number of Pareto optimal solutions grows exponentially. A decision-maker might be presented with thousands of "optimal" policies, rendering the model ineffective for practical guidance. This research addresses this challenge by incorporating imprecise tradeoffs (e.g., "Objective A is at least twice as important as Objective B") to filter solutions down to a manageable set of "possibly optimal" candidates.

Methodology: The MOVE Algorithm

The authors propose a framework centered on Possibly Optimal (PO) solutions. A policy is considered possibly optimal if there exists at least one specific weighting of objectives, consistent with the user's known tradeoffs, that makes it the best choice.

The core contribution is the MOVE (Multi-Objective Variable Elimination) algorithm. Key components include:

  • Axiomatic Foundation: The authors define formal properties (e.g., Union and Additive Decomposition) required for an optimality operator to be used safely within a variable elimination framework.
  • Variable Elimination with Pruning: Similar to standard Bayesian network inference, MOVE eliminates variables sequentially. At each step, it applies a pruning operator (like PO) to discard utility vectors that cannot be part of an optimal global policy.
  • Convex Hull Pruning: For linear weights, the set of possibly optimal points corresponds to the vertices of the utility set's convex hull, allowing for efficient geometric pruning.
  • Tradeoff Integration: The model accepts linear constraints representing user preferences, defining the "consistent scenarios" used to determine optimality.

Experimental Evaluation

The algorithm was evaluated using randomly generated MOIDs with up to 55 chance variables and 10 decision variables, across 2, 3, and 5 objectives. To simulate user input, random consistent linear tradeoffs (denoted by $K$) were generated.

Key Results

  • Massive Set Reduction: In 5-objective problems, the set of Possibly Optimal solutions was often more than 10 times smaller than those found using standard dominance checks.
  • Enhanced Scalability: MOVE(PO) solved significantly more problem instances within a 20-minute limit than MOVE(PARETO). While Pareto-based approaches often failed on high-complexity cases, MOVE(PO) frequently finished in seconds.
  • Tradeoff Sensitivity: Performance improves drastically as the number of user-provided tradeoffs ($K$) increases, as shown in the figure below. More information leads to more aggressive pruning and faster computation.
Performance of MOVE algorithms as a function of the number of user-provided tradeoffs (K).

Discussion and Future Work

The research demonstrates that while checking for "possible optimality" is computationally more intensive than simple Pareto checks (requiring linear programming), the resulting reduction in the search space leads to a net gain in overall execution speed and scalability. This approach aligns better with human decision-making by focusing on solutions that could actually be "the winner" under plausible preference scenarios.

Limitations

  • Linearity: The current framework assumes preferences can be modeled as a weighted sum. It does not yet account for non-linear preferences.
  • Induced Width: Like all variable elimination algorithms, MOVE is limited by the graph's connectivity (induced width). Extremely dense models remain computationally challenging.

Future work may explore integrating this framework into an iterative elicitation process, where the algorithm queries the user for specific tradeoffs only when necessary to further prune the search space.

Summary updated

Abstract

The formalism of multi-objective influence diagrams has recently been developed for modeling and solving sequential decision problems under uncertainty and multiple objectives. Since utility values representing the decision maker's preferences are only partially ordered (e.g., by the Pareto order) we no longer have a unique maximal value of expected utility, but a set of them. Computing the set of maximal values of expected utility and the corresponding policies can be computationally very challenging. In this paper, we consider alternative notions of optimality, one of the most important one being the notion of possibly optimal, namely optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop a variable elimination algorithm for computing the set of possibly optimal expected utility values, prove formally its correctness, and compare variants of the algorithm experimentally.
BibTeX
@inproceedings{marinescu2017multi,
  author = {Radu Marinescu and Abdul Razak and Nic Wilson},
  title = {{Multi-Objective Influence Diagrams with Possibly Optimal Policies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11053},
}
Figure