Constraint-Based Optimization and Utility Elicitation Using the Minimax Decision Criterion
In many situations, a set of hard constraints encodes the feasible con gurations of
some system or product over which multiple users have distinct preferences. However,
making suitable decisions requires that the preferences of a speci c user for
di erent con gurations 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 speci ed; 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 di erent procedures, all relying
on mixed integer linear programs, that can be used to compute minimax regret
and regret-optimizing solutions e ectively. 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 re ne 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.
Citation
C. Boutilier,
R. Patrascu,
P. Poupart,
D. Schuurmans.
"Constraint-Based Optimization and Utility Elicitation Using the Minimax Decision Criterion".
Artificial Intelligence (AIJ), 170(8-9), pp 686-713, January 2006.
| Keywords: |
decision theory, constraint satisfaction, optimization, preference, machine learning |
| Category: |
In Journal |
BibTeX
@article{Boutilier+al:AIJ06,
author = {Craig Boutilier and Relu Patrascu and Pascal Poupart and Dale
Schuurmans},
title = {Constraint-Based Optimization and Utility Elicitation Using the
Minimax Decision Criterion},
Volume = "170",
Number = "8-9",
Pages = {686-713},
journal = {Artificial Intelligence (AIJ)},
year = 2006,
}Last Updated: April 24, 2007
Submitted by AICML Admin Assistant 
