Tutte seminar - Craig Boutilier

Friday, June 7, 2013 3:30 pm - 4:30 pm EDT (GMT -04:00)

Preference Elicitation for Social Choice: A Study in Voting and Stable Matching

Speaker: Craig Boutilier
Affiliation: University of Toronto
Room: Mathematics and Computer Building (MC) 5158

Abstract:

While the methods of social choice provide firm foundations for many decision problems involving groups of individuals, their practical realization requires some means of eliciting, assessing, or learning the underlying preferences of participants. This can impose a tremendous cognitive burden on participants, who may be required provide precise rankings or utilities for dozens, hundreds, or thousands of alternatives, only to discover that much of this information has no impact on the ultimate decision.

In this talk, I will describe methods for robust optimization in social choice problems given only partial user preference information, using the concept of minimax regret. I will also describe techniques for effectively eliciting user preferences, driven by the robust solutions of the partial preference problems, that allow the computation of optimal decisions with relatively little preference information. I will focus on the application of these techniques to both voting and stable matching problems, emphasizing their use in distribution-free models, but also discussing how to exploit probabilistic preference models to further reduce the elicitation burden. Time permitting, I'll also briefly discuss the value of a more data-driven, empirical perspective on social choice, and its impact on learning and the analysis of manipulation.