Regret-based Methods for Preference Elicitation and Mechanism Design

Preference elicitation is generally required when making or recommending decisions on behalf of users whose utility function is not known with certainty. Although one can engage in elicitation until a utility function is perfectly known, in practice, this is infeasible. In this talk, I explore the use of minimax regret as (a) a distribution-free means for making decisions with imprecise utility information; and (b) a means for guiding elicitation in a way that focuses only on relevant aspects of a user's preferences. The talk will develop efficient integer programming approaches to this problem and heuristic techniques for elicitation.

Preference elicitation is, of course, an important component of (economic) mechanism design as well. Classical approaches to mechanism design require participants to fully reveal their utility functions. Time permitting, I will sketch some recent results on the use of minimax regret in the automated design of partial revelation mechanisms, that is, mechanisms in which participants declare only parts of their utility functions. We provide bounds on both incentives (i.e., the value of misreporting preferences) and outcome quality by generalizing classic Vickrey-Clarke Groves (VCG) payments to regret-based partial revelation mechanisms.

(This talk describes joint work with various collaborators.)

Craig Boutilier received his Ph.D. in Computer Science (1992) from the University of Toronto, Canada. He is Professor and Chair of the Department of Computer Science at the University of Toronto. He was previously an Associate Professor at the University of British Columbia, a consulting professor at Stanford University, and has served on the Technical Advisory Board of CombineNet, Inc. since 2001.

Dr. Boutilier's research interests span a wide range of topics, with a focus on decision making under uncertainty, including preference elicitation, mechanism design, game theory, Markov decision processes, and reinforcement learning. He is a Fellow of the American Association of Artificial Intelligence (AAAI) and the recipient of the Isaac Walton Killam Research Fellowship, an IBM Faculty Award and the Killam Teaching Award. He has also served in a variety of conference organization and editorial positions, and is Program Chair of the upcoming Twenty-first International Joint Conference on Artificial Intelligence (IJCAI-09).