Multi-objective Influence Diagrams

Radu Marinescu, Abdul Razak, Nic Wilson

Introduction

Influence Diagrams (IDs) are a cornerstone of graphical modeling for sequential decision-making under uncertainty. Traditionally, these models assume a single scalar utility function, requiring all outcomes to be reduced to a single numerical value (e.g., monetary cost). However, real-world decision-makers often face multiple, non-commensurate objectives—such as maximizing profit while minimizing environmental impact or health risks.

When these objectives cannot be perfectly weighed against one another, we must rely on partial orderings like Pareto dominance. The primary challenge is that Pareto-optimal sets tend to explode in size during computation, making standard exact algorithms intractable for complex problems. This research introduces novel pruning and approximation techniques to make Multi-objective Influence Diagrams (MOIDs) computationally feasible.

Methodology

The authors propose two primary enhancements to the baseline exact algorithm, ELIM-MOID, which adapts variable elimination to handle sets of utility vectors.

A Multi-objective Influence Diagram (MOID) example showing decision nodes and utility sets representing multiple objectives.

1. Approximation via $\epsilon$-coverings

To prevent the exponential blowup of incomparable policies, the ELIM-MOID$_\epsilon$ algorithm utilizes $\epsilon$-coverings. By mapping the utility space onto a logarithmic grid and keeping only one representative vector per grid cell, the algorithm ensures that every true optimal policy is "covered" (dominated by a factor of $1 + \epsilon$). This drastically shrinks the number of vectors the algorithm must track while providing a guaranteed bound on the approximation error.

2. Handling Imprecise Tradeoffs

In many scenarios, users can provide some guidance on preferences without committing to a strict mathematical weight. The ELIM-MOID-TOF framework translates these "imprecise tradeoffs" (e.g., "I am willing to sacrifice 1 unit of profit for 3 units of safety") into convex cones. By using linear programming to check if a utility vector falls into a dominated cone, the algorithm can prune the search space far more aggressively than standard Pareto dominance allows.

Key Results

The proposed methods were evaluated on randomly generated influence diagrams with up to 55 variables and 5 objectives.

The relationship between the approximation parameter $\epsilon$, the size of the resulting $\epsilon$-covering, and the percentage of problem instances successfully solved.

As shown in the experimental results, the approximation and tradeoff techniques provide massive performance gains:

  • Computational Efficiency: On a problem class with 25 chance variables and 2 objectives, the exact method took 17 seconds to generate ~3,600 optimal vectors. The $\epsilon$-covering method (with $\epsilon=0.3$) solved the same problem in just 0.17 seconds, reducing the output to only 24 vectors.
  • Pruning Effectiveness: Introducing even a single imprecise tradeoff reduced the size of the maximal expected utility set by a factor of 38 on the largest tested problem classes.
  • Scalability: These methods allowed the solver to handle large-scale networks that completely exhausted memory resources when using exact Pareto methods.

Conclusion

By integrating $\epsilon$-coverings and imprecise tradeoff modeling, this work demonstrates that multi-objective decision-making can scale to complex, real-world sized problems. These techniques bridge the gap between mathematically rigorous Pareto optimization and the practical constraints of computational resources and human preference elicitation. Future research will focus on applying these frameworks to specific domains like medical treatment planning and supply chain logistics.

Summary updated

BibTeX
@inproceedings{marinescu2012multi,
  author = {Radu Marinescu and Abdul Razak and Nic Wilson},
  title = {{Multi-objective Influence Diagrams}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
}
Figure