Abstract When using graphical models for decision making, the presence of unobserved variables may hinder our ability to reach the correct decision. A fundamental question here is whether or not one is ready to make a decision (stopping criteria), and if not, what additional observations should be made in order to better prepare for a decision (selection criteria). A recently introduced notion, the SameDecision Probability (SDP), has been shown to be useful as both a stopping and a selection criteria. This query has been shown to be highly intractable, being PPPP –complete, and is exemplary of a class of queries which correspond to the computation of certain expectations. We propose the first exact algorithm for computing the SDP in this paper, and demonstrate its effectiveness on several real and synthetic networks. We also present a new complexity result for computing the SDP on models with a Naive Bayes structure.