Minimax regret based elicitation of generalized additive utilities

Darius Braziunas, Craig BoutilierUAI 2007 · OpenReview

TL;DR

This paper introduces a novel approach to eliciting user preferences for complex, multi-attribute decisions using the minimax regret criterion. By developing new query types and efficient computational methods, it enables decision support systems to make robust recommendations even with incomplete information about user utilities, paving the way for more practical and effective AI-driven decision aids.

What Problem Does This Paper Address?

In many real-world applications, decision support systems need to understand and represent user preferences across multiple attributes (e.g., choosing a car, a rental property, or a complex product configuration). The challenge is that the number of possible outcomes grows exponentially with the number of attributes, making it computationally infeasible to ask users about every single possibility. Traditional methods often rely on simplified utility models (like additive independence) which can be too restrictive. More flexible models, such as Generalized Additive Independence (GAI), exist but are harder to elicit preferences for because their parameters lack clear semantic interpretations. Furthermore, users' preferences are often not perfectly known; there's inherent uncertainty. How can we design systems that elicit preferences efficiently and make good decisions despite this uncertainty?

Methods

The core of this paper lies in combining the Generalized Additive Independence (GAI) utility model with the minimax regret decision criterion.

  • GAI Model: This model allows for more flexible preference structures than simple additive models by decomposing utility over overlapping subsets of attributes. The authors leverage a canonical representation of GAI utilities that separates parameters into "local" (value functions for attribute subsets) and "global" (scaling constants) components, giving them semantic meaning.
  • Minimax Regret: This criterion is used to make decisions under uncertainty. Instead of assuming a specific utility function, it considers a set of possible utility functions (defined by user responses to queries) and chooses the action that minimizes the worst-case loss (regret) across all these possibilities. This is particularly useful when distributional information about preferences is unavailable.
  • Novel Query Types: The authors introduce four new query types designed for GAI models:
  • Local Bound (LB) Queries: These bound the value of local utility functions by asking users to compare a partial outcome to a lottery.
  • Local Comparison (LC) Queries: These ask users to compare two partial outcomes, helping to refine local utility function parameters.
  • Anchor Bound (AB) Queries: These bound the global scaling constants by asking about preferences between anchor outcomes and lotteries.
  • Anchor Comparison (AC) Queries: These compare anchor outcomes from different factors, providing relative information about global scaling.
  • Efficient Computation: A key contribution is the development of linear mixed integer programming (MIP) formulations for computing minimax regret. This allows the system to efficiently find the optimal decision and identify the most informative query to ask next, even with the added complexity of GAI models. They also propose strategies for handling large product databases by iteratively generating candidate solutions.

Datasets

The authors evaluated their approach on two real-world problems:

  • Car Rental Configuration Problem: A complex problem with 26 attributes, over 6.1 x 10^10 possible configurations, and a GAI model with 378 utility parameters.
  • Apartment Rental Database: A smaller problem with 186 apartments described by 8 attributes, using a GAI model with 156 utility parameters.

No new benchmarks were introduced; existing problems were used to demonstrate the effectiveness of their GAI-based minimax regret approach.

Key Insights and Ideas

  • Semantically Sound GAI Elicitation: By carefully structuring the GAI model and defining new query types, the authors provide a way to elicit parameters that have clear meaning to the user, making the process more intuitive and robust.
  • Local Queries are Powerful: While global queries are sometimes necessary for full calibration, the paper demonstrates that a significant portion of the "heavy lifting" in elicitation can be achieved using local queries that focus on smaller subsets of attributes, aligning with human cognitive limitations.
  • Minimax Regret as a Practical Decision Criterion: For situations with significant uncertainty about user preferences, minimax regret offers a principled way to make decisions that are guaranteed to be "good enough" in the worst case, avoiding potentially disastrous choices.
  • MIPs for Scalability: The translation of minimax regret computation into linear MIPs is crucial for making this approach computationally feasible for realistic problems.

Key Results

The experimental results on both the car rental and apartment rental problems were highly encouraging:

  • Significant Regret Reduction: All tested query strategies, even those using only local queries, achieved a sharp reduction in minimax regret within the first 10-20 interactions.
  • Real-time Interaction: The system could compute the regret-minimizing solution and determine the next query in about 1 second, enabling real-time interaction with users.
  • Effectiveness of Local Queries: Strategies relying solely on local queries (like LC and LB) performed very well, often approaching the performance of strategies that also used global queries.
  • Global Queries for Optimal Guarantees: Strategies incorporating global anchor queries (AB+LC+LB, AB+LB) were able to reduce regret to zero, providing the strongest guarantees.

Limitations and Future Work

  • GAI Structure Assumption: The current work assumes the GAI structure of the utility function is known. Future work aims to explore techniques for eliciting this structure itself.
  • Probabilistic Knowledge: The authors plan to investigate incorporating probabilistic knowledge about utility parameters to guide elicitation more effectively, especially when making final decisions.
  • Query Costs: While heuristic scores are used to rank queries, explicitly incorporating query costs (e.g., time, user effort) into elicitation strategies is a direction for future research.
  • Human Factors: Future experiments with human decision-makers are planned to understand the impact of psychological factors like framing and ordering effects on the normative model of elicitation.

Summary updated

Abstract

We describe the semantic foundations for elicitation of generalized additively independent (GAI) utilities using the minimax regret criterion, and propose several new query types and strategies for this purpose. Computational feasibility is obtained by exploiting the local GAI structure in the model. Our results provide a practical approach for implementing preference-based constrained configuration optimization as well as effective search in multiattribute product databases.
BibTeX
@inproceedings{braziunas2007minimax,
  author = {Darius Braziunas and Craig Boutilier},
  title = {{Minimax regret based elicitation of generalized additive utilities}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=DCk6XjojLL},
}
Figure