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.
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.
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