  Influence diagrams provide a compact graphical representation of decision
problems. Several algorithms for the quick computation of their associated
expected utilities are available in the literature. However, often they rely on
a full quantification of both probabilistic uncertainties and utility values.
For problems where all random variables and decision spaces are finite and
discrete, here we develop a symbolic way to calculate the expected utilities of
influence diagrams that does not require a full numerical representation.
Within this approach expected utilities correspond to families of polynomials.
After characterizing their polynomial structure, we develop an efficient
symbolic algorithm for the propagation of expected utilities through the
diagram and provide an implementation of this algorithm using a computer
algebra system. We then characterize many of the standard manipulations of
influence diagrams as transformations of polynomials. We also generalize the
decision analytic framework of these diagrams by defining asymmetries as
operations over the expected utility polynomials.
