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.