Decision Modeling and Analysis Using Influence Diagrams

Eng Hak Boon

Abstract

The influence diagram was developed to substitute conventional decision trees in modeling and solving real world decision problems. It offers comparative advantages of compact and intuitive formulation, easy numerical assessment and most importantly, effective representation of independencies between variables over trees. These factors contributed to the wide spread use of influence diagrams as a tool for representing and analyzing complex decision problems in recent years.

However, algorithms proposed for finding optimal decision policies based on influence diagrams have been found to be highly sensitive to the topological structure of the diagram being manipulated, and demand excessive computational and storage resources. This restricted the application of influence diagrams to relatively small problems.

In this project, an algorithm for evaluating influence diagrams without resorting to tree conversion was studied and improved upon by incorporating a heuristic-based preprocessing scheme before solution. This scheme facilitates the reduction of large diagrams to manageable size in polynomial time. Further research effort to improve the efficiency with information storage revealed certain weaknesses at the semantic level with the current definition of a regular influence diagram. This project concludes that certain technical constrains need to be relaxed to minimize information redundancy and facilitate multiple-decision-maker problem formulation.