Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams

• We show a polynomial-time reduction from MAP to MEU that preserves the boundedness of treewidth.
• We show a polynomial-time reduction from MEU to MAP that also preserves the boundedness of treewidth.
• We use the reduction from MAP to MEU to characterize the complexity of MEU in credal influence diagrams.
• Experiments show that reducing MEU to MAP can be an effective alternative for solving MEU problems.

Two important tasks in probabilistic reasoning are the computation of the maximum posterior probability of a given subset of the variables in a Bayesian network (MAP), and the computation of the maximum expected utility of a strategy in an influence diagram (MEU). Both problems are NPPP-hard to solve, and NP-hard to approximate when the treewidth of the underlying graph is bounded. Despite the similarities, researches on both problems have largely been conducted independently, with algorithmic solutions and insights designed for one problem not (trivially) transferable to the other one. In this work, we show constructively that these two problems are equivalent in the sense that any algorithm designed for one problem can be used to solve the other with small overhead. Moreover, the reductions preserve the boundedness of treewidth. Building on the known complexity of MAP on networks whose parameters are imprecisely specified, we show how to use the reductions to characterize the complexity of MEU when the parameters are set-valued. These equivalences extend the toolbox of either problem, and shall foster new insights into their solution.