CRCS Lunch Seminar (Monday, October 4, 2010)
Speaker: Craig Boutilier, University of Toronto
Title: Computational Social Choice: A Decision-Theoretic Perspective
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.
Joint work with Tyler Lu
Bio: Craig Boutilier is a Professor of Computer Science at the University of Toronto. He received his Ph.D from of Toronto in 1992, and joined the faculty of University of British Columbia in 1991 (where he remains an Adjunct Professor). He returned to Toronto in 1999, and served as Chair of the Department of Computer Science from 2004-2010. Boutilier was a consulting professor at Stanford University from 1998-2000, a visiting professor at Brown University in 1998, and a visiting professor at Carnegie Mellon University in 2008-09. He served on the Technical Advisory Board of CombineNet, Inc. from 2001 to 2010.
Boutilier’s has published over 170 refereed articles covering topics ranging from knowledge representation, belief revision, default reasoning, and philosophical logic, to probabilistic reasoning, decision making under uncertainty, multiagent systems, and machine learning. His current research efforts focus on various aspects of decision making under uncertainty: preference elicitation, mechanism design, game theory and multiagent decision processes, economic models, social choice, computational advertising, Markov decision processes and reinforcement
Boutilier served as Program Chair for both the 16th Conference on Uncertainty in Artificial Intelligence (UAI-2000) and the 21st International Joint Conference on Artificial Intelligence (IJCAI-09). He will begin a two-year term as Associate Editor-in-Chief of the Journal of Artificial Intelligence Research (JAIR) in 2011 and serve as Editor-in-Chief for a two-year term beginning in 2013. Boutilier is a Fellow of the American Association of Artificial Intelligence (AAAI). He has been awarded the Isaac Walton Killam Research Fellowship and an IBM Faculty Award. He also received the Killam Teaching Award from the University of British Columbia in 1997.
(Source: YouTube | Harvard’s CRCS)