###
Constraint-based Optimization and Utility Elicitation using the Minimax Decision Criterion

**Craig Boutilier **

Department of Computer Science

University of Toronto

Toronto, ON M5S 3H5

*email:* `cebly@cs.toronto.edu`

**Relu Patrascu **

Department of Computer Science

University of Toronto

Toronto, ON M5S 3H5

*email:* `relu@cs.toronto.edu`

**Pascal Poupart **

Department of Computer Science

University of Toronto

Toronto, ON M5S 3H5

*email:* `ppoupart@cs.toronto.edu`

**Dale Schuurmans **

Department of Computing Science

University of Alberta

Edmonton, AB, T6G 2E8

*email:* `dale@cs.ualberta.ca`

**Abstract**

In many situations, a set of hard
constraints encodes the feasible configurations of some system or product over
which multiple users have distinct preferences. However, making suitable
decisions requires that the preferences of a specific user for different
configurations be articulated or elicited, something
generally acknowledged to
be onerous.We address two problems associated with preference elicitation:
computing a best feasible solution when the user s utilities are imprecisely
specified; and developing useful elicitation procedures that reduce utility
uncertainty, with minimal user interaction, to a point where (approximately)
optimal decisions can be made. Our main contributions are threefold. First, we
propose the use of minimax regret as a suitable decision criterion for decision
making in the presence of such utility function uncertainty. Second, we devise
several different procedures, all relying on mixed integer linear programs,
that can be used to compute minimax regret and regret-optimizing solutions
effectively. In particular, our methods exploit generalized additive structure
in a user s utility function to ensure tractable computation. Third, we propose
various elicitation methods that can be used to refine utility uncertainty in
such a way as to quickly (i.e., with as few questions as possible) reduce
minimax regret. Empirical study suggests that several of these methods are
quite successful in minimizing the number of user queries, while remaining
computationally practical so as to admit real-time user interaction.

* To appear, Artificial Intelligence, 2006*

Return to
List of Papers