**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