On the Complexity of General Solution DAGs

The General Solution DAGs (GS-DAGs) are a method used to solve the Unconstrained Influence Diagrams (UIDs). In the first part of this paper, we determine the strict upper bound on the size of the GS-DAG with respect to the size of the UID being solved. In the second part, we introduce a new type of GS-DAG multinode, which reduces the number of edges of the GS-DAGs significantly. This has a huge impact on the evaluation of the GS-DAGs, because the number of edges heavily influences the number of computed and stored potential tables. The results presented in this article are also of a great importance from the point of view of approximation methods, which appeared recently and try to outperform the GS-DAG approach with an unknown complexity (until now).