November 18, 2010: Distinguished Lecturer Seminar Series - Craig Boutilier: "Computational Social Choice: A Decision-theoretic Perspective"
The University of Illinois at Chicago
Department of Computer Science
2010-2011 Distinguished Lecturer Seminar Series
Computational Social Choice: A Decision-theoretic Perspective
University of Toronto
Thursday, November 18, 2010
11:00 a.m., Room 1000 SEO
Social choice, an important topic of study for centuries, has recently been the subject of intense investigation and application within computer science. One reason for this is the increasing ease with which preference data from user populations can be derived, assessed, or estimated, and the variety of settings in which preference data can be aggregated for consensus recommendations. However, much work in computational social choice adopts existing social choice schemes rather uncritically. We adopt an explicit decision-theoretic perspective on computational social choice in which an explicit objective function is articulated for the task at hand. With this is place, one can develop new social choice rules suited to that objective; or one can analyze the performance of existing social choice rules relative to that criterion.
We illustrate the approach with two different models. The first is the "unavailable candidate model." In this model, a consensus choice must be selected from a set of candidates, but candidates may become unavailable after agents express their preferences. An aggregate ranking is used as a decision policy in the face of uncertain candidate availability. We define a principled aggregation method that minimizes expected voter dissatisfaction, provide exact and approximation algorithms for optimal rankings, and show experimentally that a simple greedy scheme can be extremely effective. We also describe strong connections to the plurality rule and the Kemeny consensus, showing specifically that Kemeny produces optimal rankings under certain conditions.
The second model is the "budgeted social choice" model. In this framework, a limited number of alternatives can be selected for a population of agents. This limit is determined by some form of budget. Our model is general, spanning the continuum from pure consensus decisions (i.e., standard social choice) to fully personalized recommendation. We show that standard rank aggregation rules are not appropriate for such tasks and that good solutions typically involve picking diverse alternatives tailored to different agent types. In this way, it bears a strong connection to both segmentation problems and multi-winner election schemes. The corresponding optimization problems are shown to be NP-complete, but we develop fast greedy algorithms with theoretical guarantees. Experimental results on real-world datasets demonstrate the effectiveness of our greedy algorithms.
Craig Boutilier is a Professor in the Department of Computer Science at the University of Toronto. He received his Ph.D. in Computer Science from the University of Toronto in 1992. He served as Chair of the Department of Computer Science at Toronto from 2004-2010. He is also an Adjunct Professor at the University of British Columbia. Current research efforts focus on various aspects of decision making under uncertainty: preference elicitation, mechanism design, game theory and multi-agent decision processes, economic models, social choice, computational advertising, Markov decision processes, reinforcement learning and probabilistic inference. In a past research life, he spent quite a bit of time working in the areas of knowledge representation, belief revision, default reasoning, and philosophical logic.
Host: Piotr Gmytrasiewicz