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
We propose new methods of preference elicitation for
constraint-based optimization problems based on the use
of minimax regret. Specifically, we assume a constraintbased
optimization problem (e.g., product configuration)
in which the objective function (e.g., consumer preferences)
are unknown or imprecisely specified. Assuming
a graphical utility model, we describe several elicitation
strategies that require the user to answer only binary
(bound) queries on the utility model parameters. While a
theoretically motivated algorithm can provably reduce regret
quickly (in terms of number of queries), we demonstrate
that, in practice, heuristic strategies perform much
better, and are able to find optimal (or near-optimal) con-
figurations with far fewer queries.
To appear, IJCAI 2005
Return to List of Papers