Decomposed Utility Functions and Graphical Models for Reasoning about Preferences

Ronen I. Brafman, Yagil EngelAAAI 2010 · DOI

Introduction

In the field of Artificial Intelligence, modeling user preferences is as critical as modeling uncertainty. While probability theory has long benefited from the efficiency and clarity of graphical models—such as Bayesian Networks—utility functions have historically lacked a similarly robust, axiomatic framework. The primary challenge lies in the nature of utility: while probability distributions are naturally multiplicative and easily marginalized, utility functions are typically additive. This difference has made it difficult to define a "marginal utility" for a single attribute without considering the state of all other variables.

This paper addresses this gap by introducing Marginal Utility Networks, a formal framework that bridges the mathematical divide between probability and preference modeling. By establishing a fixed reference point, the authors demonstrate that utility independence satisfies the same fundamental axioms as probabilistic independence, enabling the use of powerful inference tools like d-separation and Belief Propagation for preference reasoning.

The Reference Utility Framework

The core innovation of this research is the introduction of a Reference Assignment ($u_r$). To resolve the marginalization problem, the authors propose fixing a baseline state for all variables in a system. This allows for two critical definitions:

  1. Marginal Utility: The utility of a subset of attributes is defined as their utility when all other attributes are held at the reference level.
  2. Conditional Utility: Defined as $u_r(\gamma_1 | \gamma_2) = u_r(\gamma_1 \gamma_2) - u_r(\gamma_2)$. This serves as the additive analog to the multiplicative definition of conditional probability ($P(A|B) = P(A,B)/P(B)$).

By framing utility in terms of deviations from a reference point, the authors transform a complex additive problem into a structured graphical one. This "reference point" approach provides the necessary mathematical grounding to treat utility with the same rigor as probability.

Axiomatic Foundations and d-Separation

The theoretical weight of the paper rests on the proof that Conditional Utility Independence ($CDI_r$) satisfies the semi-graphoid axioms. These axioms—including symmetry, decomposition, and weak union—are the essential rules that allow independence relationships to be represented via Directed Acyclic Graphs (DAGs).

Because $CDI_r$ adheres to these axioms, the authors prove that d-separation—the standard criterion for determining independence in Bayesian Networks—is fully applicable to utility networks. This equivalence means that researchers can use the same structural logic to determine if one set of preferences is independent of another, given a third set of attributes.

Marginal Utility Networks

The authors formally define Marginal Utility Networks as a new class of graphical models that serve as minimal I-maps of $CDI_r$. Effectively, these are "Bayesian Networks for preferences." Key properties of these networks include:

  • Chain and Bayes' Rules: The paper establishes additive versions of the Chain Rule and Bayes' Rule, providing a calculus for decomposing complex utility functions into local components.
  • Linear Retrieval: Calculating the total utility of any specific outcome from a Marginal Utility Network is linear relative to the number of attributes, ensuring high efficiency even in large-scale systems.
  • Constraint Handling: The framework naturally incorporates hard constraints (e.g., incompatible product features) by utilizing dummy nodes with $-\infty$ utility, mirroring the way evidence is handled in probabilistic models.

Algorithmic Portability: Belief Propagation

One of the most practical outcomes of this research is the adaptation of the Belief Propagation (BP) algorithm for utility maximization. Because the underlying logic of Marginal Utility Networks mirrors that of Bayesian Networks, existing algorithms can be ported with minimal modification. By swapping multiplications for additions and sums for maximizations, the authors derive a version of BP that can find the most preferred outcome in trees and polytrees with formal guarantees of correctness.

Limitations and Future Directions

While the framework is mathematically sound, it introduces new considerations for preference elicitation. The model's structure depends on the choice of a reference assignment; while any assignment is mathematically valid, the choice may impact how intuitively a human user can provide the necessary "Conditional Utility Tables" (CUTs).

Furthermore, while the adapted Belief Propagation works perfectly on trees, its performance on loopy graphs remains an area for empirical study, likely serving as a strong approximation. Future work may also explore how these networks can be learned directly from user behavior data, rather than being manually constructed through elicitation.

Conclusion

By proving the mathematical equivalence between utility independence and probabilistic independence, this paper provides a unifying language for reasoning about what an agent believes and what an agent wants. Marginal Utility Networks offer a scalable, efficient, and theoretically grounded approach to preference modeling, opening the door for more sophisticated decision-support systems and autonomous agents.

Summary updated

BibTeX
@inproceedings{brafman2010decomposed,
  author = {Ronen I. Brafman and Yagil Engel},
  title = {{Decomposed Utility Functions and Graphical Models for Reasoning about Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7582},
}
Figure