Problem-Focused Incremental Elicitation of Multi-Attribute Utility Models

Vu A. Ha, Peter HaddawyUAI 1997

TL;DR

This paper tackles the challenge of efficiently eliciting user preferences (utility models) for decision-making systems. Instead of demanding complete upfront information, it proposes an incremental approach that prioritizes eliciting the most impactful preference information first, significantly reducing user burden and speeding up decision-making, especially in time-critical scenarios.

What Problem Does This Paper Address?

Decision theory provides a powerful framework for AI agents to make optimal decisions by considering probabilities of world states and user preferences (utility). While significant effort has gone into eliciting probabilistic models, eliciting utility models has been a bottleneck. This is because utility models are often specific to each decision instance and can be tedious to elicit fully. Traditional approaches require all utility information upfront, which is impractical for interactive systems or time-constrained situations. This paper addresses the need for a more flexible and efficient way to elicit utility information, focusing on how to infer optimal decisions even with incomplete utility models and how to intelligently ask for more information when needed.

Methods

The core of the paper's contribution lies in its "problem-focused incremental elicitation" approach. Key methods include:

  • Reasoning with Partial Utility Models: The paper explores how to infer overall dominance (which plan is better) from local dominances (which plan is better on a subset of attributes) even when the complete utility function is unknown. This is achieved by leveraging concepts from multi-attribute utility theory, particularly preferential and utility independence.
  • Additive Utility Assumption: For much of the analysis, the authors assume an additive utility function, which simplifies the problem and allows for direct inference of overall dominance from local dominances if attributes are probabilistically independent.
  • Rank Correlation Coefficient (RCC) for Intelligent Elicitation: To decide what preference information to ask for next, the paper proposes using the Rank Correlation Coefficient. This statistical measure helps identify pairs of attributes whose rankings of potential plans are most dissimilar. Eliciting tradeoff information (e.g., "how much of attribute A am I willing to sacrifice for one unit of attribute B?") between these conflicting attributes is hypothesized to reveal the most suboptimal plans, thus most efficiently narrowing down the set of candidate solutions.
  • Incremental Elicitation Loop: The system iteratively performs two main steps:
  • Eliminate Suboptimal Plans: Using the current (partial) utility information, identify and remove plans that are provably worse than others.
  • Elicit Tradeoff Information: If the set of remaining candidate plans is still too large, use the RCC heuristic to select the next most informative tradeoff question to ask the user. This process repeats until the user is satisfied with the remaining options.

Datasets

Not discussed in the paper. The authors use a medical decision problem (management of deep venous thrombosis) as a case study for demonstrating their approach, but this is presented as an example rather than a formal dataset evaluation.

Key Insights and Ideas

  • Utility Elicitation is a Bottleneck: The paper highlights that for many AI systems, eliciting utility is far more time-consuming than reasoning with it, making efficient elicitation crucial.
  • Partial Information is Often Sufficient: Users don't always need to specify every single preference. Often, partial information can significantly prune the decision space, leading to a satisfactory choice or making the remaining options clearly distinguishable.
  • Intelligent Questioning is Key: Simply asking random questions about preferences is inefficient. The paper's core insight is that by understanding the relationships between attributes (via RCC), we can ask questions that yield the most "bang for the buck" in terms of eliminating suboptimal plans.
  • Tradeoffs Reveal Suboptimality: The most informative questions often involve tradeoffs between attributes that conflict in their ranking of potential solutions. Understanding these tradeoffs helps reveal which plans are truly inferior.
  • "Lazy" Elicitation: The proposed approach is "lazy" because it only elicits information when it's needed to make progress in narrowing down the options, rather than demanding everything upfront.

Key Results

  • Experimental Validation: The paper presents experimental results comparing their RCC-based approach to a random attribute selection method (RAND) and an omniscient optimal approach (OPT).
  • Improved Performance: The RCC-based algorithm consistently outperformed the random approach in eliminating suboptimal plans, achieving a competitive ratio of 0.89 compared to RAND's 0.65.
  • Efficiency Gains: In a case study on deep venous thrombosis management, the system, using RCC, was able to reduce a set of 91 candidate plans to just 4 plans after only a few elicitation steps, without needing to fully specify the utility function (specifically, the cost attribute).
  • Anytime Performance: Figure 1 shows that the RCC approach generally leads to a smaller efficient frontier (fewer remaining candidate plans) for a given number of questions asked, demonstrating better "anytime" performance.

Limitations and Future Work

  • Additive Utility Assumption: The paper heavily relies on the assumption of an additive utility function for much of its theoretical development and for the direct application of RCC. While this is a common simplification, it limits applicability to problems where this assumption doesn't hold.
  • Heuristic Nature of RCC: The authors acknowledge that RCC is a heuristic. While it performed well experimentally, it doesn't guarantee identifying the absolute best attribute pair for elicitation in all cases. Other pairings might reveal more suboptimal plans.
  • Future Work: The authors suggest extending the RCC method to more general utility function forms, such as conditionally additive independence (CAI), and exploring how to incorporate user feedback on attribute ranges (e.g., identifying attributes with negligible variation) to further simplify the elicitation process. They also propose investigating the use of extreme solutions as a way to guide elicitation.

Summary updated

BibTeX
@inproceedings{ha1997problem,
  author = {Vu A. Ha and Peter Haddawy},
  title = {{Problem-Focused Incremental Elicitation of Multi-Attribute Utility Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1997},
}
Figure