A note about redundancy in influence diagrams

✍ Scribed by Enrico Fagiuoli; Marco Zaffalon

• Book ID: 104347967
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 645 KB
• Volume: 19
• Category: Article
• ISSN: 0888-613X
• DOI: 10.1016/s0888-613x(98)10015-4

✦ Synopsis

Influence Diagrams (IDs) are formal tools for modelling decision processes and for computing optimal strategies under risk. Like Bayesian networks, influence diagrams exploit the sparsity of the dependency relationships among the random variables in order to reduce computational complexity. In this note, we initially observe that an influence diagram can have some arcs that are not necessary for a complete description of the model. We show that while it may not be easy to detect such arcs, it is important, since a redundant graphical structure can exponentially increase the computational time of a solution procedure. Then we define a graphical criterion that is shown to allow the identification and removal of the redundant parts of an ID. This technical result is significant because it precisely defines what is relevant to know at the time of a decision. Furthermore, it allows a redundant influence diagram to be transformed into another ID, that can be used to compute the optimal policy in an equivalent but more efficient way.