TL;DR
This paper introduces a novel method for eliciting user preferences in complex decision-making scenarios modeled by Generalized Additive Independence (GAI) utility functions. By leveraging the structure of GAI models and focusing on "local" queries about small subsets of attributes, the authors significantly reduce the cognitive burden on users and enable efficient elicitation even in very large domains.
What Problem Does This Paper Address?
Automated decision support systems often rely on understanding a user's preferences, typically modeled by utility functions. For complex problems with many attributes, specifying these utility functions directly is infeasible due to the exponential growth of possible outcomes. While structural assumptions like additive independence simplify this, Generalized Additive Independence (GAI) models offer more flexibility by allowing dependencies between subsets of attributes. However, existing methods for eliciting parameters of GAI models often still require users to make difficult judgments about full outcomes, negating some of the benefits of GAI's structure. This paper addresses the challenge of developing practical and efficient elicitation procedures for GAI models that minimize user effort.
Methods
The core contribution is a two-pronged approach to GAI utility elicitation:
- Local Elicitation: Instead of asking users to compare entire outcomes, the method focuses on "local" queries. These queries involve comparing suboutcomes (partial outcomes restricted to a subset of attributes) against local gambles (lotteries over these suboutcomes). This is made possible by Theorem 3, which shows that under GAI, preferences over local outcomes are independent of other attributes when conditioning attributes are fixed at their default levels. This allows for eliciting local value functions for each GAI factor independently.
- Global Scaling: After local elicitation, a procedure for "global scaling" is used to combine these local preferences into a coherent global utility function. This involves a limited number of queries about anchor outcomes (specific combinations of attribute levels) to calibrate the overall utility. The authors also propose a graphical representation of GAI models (GAI graphs) to systematically identify the necessary local suboutcomes for elicitation.
- Elicitation Under Uncertainty: The paper extends this by considering scenarios where utility parameters are not precisely known but are described by prior probability distributions. They propose a myopic Expected Value of Information (EVOI) strategy to select the most informative queries. This involves optimizing over both the choice of query and the query point itself, aiming to maximize the expected reduction in uncertainty about the optimal decision.
Datasets
The paper evaluates its approach on a "realistic car-rental problem" with 26 variables and over 61 billion possible configurations. This problem is modeled using a GAI structure with 13 local factors. The authors do not introduce a new benchmark dataset but use an existing problem to demonstrate their method's scalability and effectiveness.
Key Insights and Ideas
- "Local" is the Key: The most significant insight is that GAI models' structure allows for breaking down complex preference elicitation into manageable, "local" queries. This drastically reduces the cognitive load on the user compared to methods requiring judgments on full outcomes.
- GAI Graphs Simplify Structure: Representing GAI models as graphs provides a systematic way to understand attribute dependencies and identify the specific suboutcomes relevant for elicitation, simplifying the process.
- EVOI for Intelligent Queries: When utility parameters are uncertain, a myopic EVOI strategy intelligently guides the elicitation process by selecting queries that are most likely to reduce uncertainty about the optimal decision. This is more efficient than random querying.
- Scalability is Achieved: The proposed methods are shown to be computationally efficient enough to support interactive elicitation, even for very large and complex problems.
Key Results
- The proposed local elicitation method significantly reduces the number of queries and the complexity of judgments required from the user.
- The EVOI strategy, when applied to GAI models, demonstrates superior performance compared to random query strategies in reducing utility error. For instance, with Gaussian priors, the EVOI strategy reduces error by over 80% after 50 queries, whereas random strategies achieve at best 20% reduction.
- The method is computationally efficient, with EVOI computations for the car-rental problem taking around 1 second, enabling interactive use.
Limitations and Future Work
- GAI Structure Assumption: The method relies on the assumption that the user's preferences can be accurately represented by a GAI model. Determining the appropriate GAI structure itself is a separate, important research direction.
- Noise and Inconsistency: The current method assumes consistent user responses. Future work could explore methods for dealing with noisy or inconsistent user input.
- Non-Myopic EVOI: The paper uses a myopic EVOI strategy. Developing computationally tractable approximations for non-myopic EVOI could lead to even more optimal elicitation policies.
- Other Decision Criteria: Exploring decision criteria beyond maximizing expected utility, such as minimax regret, is suggested for future work.
- More Realistic Queries: While focusing on local gambles, the paper mentions considering "more realistic local comparison queries" as a future step.
Summary updated