  We describe multi-objective influence diagrams, based on a set of p
objectives, where utility values are vectors in Rp, and are typically only
partially ordered. These can still be solved by a variable elimination
algorithm, leading to a set of maximal values of expected utility. If the
Pareto ordering is used this set can often be prohibitively large. We consider
approximate representations of the Pareto set based on e-coverings, allowing
much larger problems to be solved. In addition, we define a method for
incorporating user tradeoffs, which also greatly improves the efficiency.
