Extending the scope of graphical models

The influence diagram framework serves as a powerful modeling language for decision problems with a single decision maker. However, efficient use of the influence diagram framework imposes some rather severe structural constraints on the decision problem being modeled. For instance, a linear temporal ordering of the decisions is required in order to ensure that the decision problem is well-defined, and the decision problem should furthermore be symmetric (e.g., future decision options may not depend on past decisions and observations). The focus of this project is the development of graphical models and algorithms for extending the class of decision problems that can be modeled and solved efficiently. For instance, Nielsen and Jensen (1999) relax the requirement of a linear ordering of the decisions by giving a set of necessary and sufficient structural constraints ensuring that an influence diagram, with only a partial ordering of the decisions, is well-defined. Alternative, Jensen and Vomlelova (2002) suggest that one might take outset in a partial specification of the influence diagram (well-defined or not), and then determine a good sequence for the decisions during the solution phase. Along similar lines, graphical specification languages for representing so-called asymmetric decision problems are proposed in (Nielsen and Jensen, 2004; Jensen, Nielsen and Shenoy, 2005). The specification languages are much more compact than decision trees, and the solution algorithms are substantially faster than the algorithm for solving decision trees. Also, Madsen, Olesen and Dittmer (2001) presents an adjusted representation of influence diagrams to exploit deterministic relations.