An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities

Abstract

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.

References in corpus (18)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements
• Context-Specific Independence in Bayesian Networks
• Graphical Models for Preference and Utility
• Stochastic Constraint Programming
• Plausibility Measures: A User's Guide
• An Order of Magnitude Calculus
• Unconstrained Influence Diagrams
• A Qualitative Linear Utility Theory for Spohn's Theory of Epistemic Beliefs
• A Possibilistic Model for Qualitative Sequential Decision Problems under Uncertainty in Partially Observable Environments
• Hybrid Processing of Beliefs and Constraints
• Qualitative Models for Decision Under Uncertainty without the Commensurability Assumption
• Conditional Plausibility Measures and Bayesian Networks
• Valuation-Based Systems for Discrete Optimization
• Great Expectations. Part I: On the Customizability of Generalized Expected Utility
• Great Expectations. Part II: Generalized Expected Utility as a Universal Decision Rule
• From influence diagrams to multi-operator cluster DAGs
• General Belief Measures

Cited by in corpus (2)

• Exact and approximate inference in graphical models: variable elimination and beyond
• Revisiting Algebra and Complexity of Inference in Graphical Models