An Algebraic Graphical Model for Decision with Uncertainties,
  Feasibilities, and Utilities
  Numerous formalisms and dedicated algorithms have been designed in the last
decades to model and solve decision making problems. Some formalisms, such as
constraint networks, can express "simple" decision problems, while others are
designed to take into account uncertainties, unfeasible decisions, and
utilities. Even in a single formalism, several variants are often proposed to
model different types of uncertainty (probability, possibility...) or utility
(additive or not). In this article, we introduce an algebraic graphical model
that encompasses a large number of such formalisms: (1) we first adapt previous
structures from Friedman, Chu and Halpern for representing uncertainty,
utility, and expected utility in order to deal with generic forms of sequential
decision making; (2) on these structures, we then introduce composite graphical
models that express information via variables linked by "local" functions,
thanks to conditional independence; (3) on these graphical models, we finally
define a simple class of queries which can represent various scenarios in terms
of observabilities and controllabilities. A natural decision-tree semantics for
such queries is completed by an equivalent operational semantics, which induces
generic algorithms. The proposed framework, called the
Plausibility-Feasibility-Utility (PFU) framework, not only provides a better
understanding of the links between existing formalisms, but it also covers yet
unpublished frameworks (such as possibilistic influence diagrams) and unifies
formalisms such as quantified boolean formulas and influence diagrams. Our
backtrack and variable elimination generic algorithms are a first step towards
unified algorithms.
