[Intelligence Seminar] December 7, 3:30pm: Presentation by Graig Boutilier

[Noah A Smith]

INTELLIGENCE SEMINAR
December 7 at 3:30pm, in GHC 4303

SPEAKER: CRAIG BOUTILIER (University of Toronto)
Host: Tuomas Sandholm
For meetings, contact Charlotte Yano (yano at cs.cmu.edu)

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 in 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.

BIO

Craig Boutilier is a Professor of Computer Science at the University of
Toronto.  He received his Ph.D from the University of Toronto in 1992, and
joined the faculty of the 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-2009. He served on the Technical
Advisory Board of CombineNet, Inc. from 2001 to 2010.  Boutilier 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
learning. 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-2009).
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 Association for the Advancement 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.srv.cs.cmu.edu/pipermail/intelligence-seminar-announce/attachments/20101201/133219f5/attachment-0001.html