[Colloq] Talk on Tuesday, Dec 8: Elliot Anshelevich (RPI), Approximating Optimal Social Choice under Metric Preferences

[Rajmohan Rajaraman]

CCIS Colloquium and Theory Seminar
----------------------------------

TITLE: Approximating Optimal Social Choice under Metric Preferences
SPEAKER: Elliot Anshelevich (RPI)
DATE: Tuesday, Dec 8, 2015
TIME: 12:30 PM
LOCATION: 366 WVH

ABSTRACT:

We examine the quality of social choice mechanisms using a utilitarian
view, in which all of the agents have costs for each of the possible
alternatives. While these underlying costs determine what the optimal
alternative is, they may be unknown to the social choice mechanism;
instead the mechanism must decide on a good alternative based only on
the ordinal preferences of the agents which are induced by the
underlying costs. Due to its limited information, such a social choice
mechanism cannot simply select the alternative that minimizes the total
social cost (or minimizes some other objective function). Thus, we seek
to bound the distortion: the worst-case ratio between the social cost of
the alternative selected and the optimal alternative. Distortion
measures how good a mechanism is at approximating the alternative with
minimum social cost, while using only ordinal preference information.
The underlying costs can be arbitrary, implicit, and unknown; our only
assumption is that the agent costs form a metric space, which is a
natural assumption in many settings. We quantify the distortion of many
well-known social choice mechanisms. We show that for both total social
cost and median agent cost, many positional scoring rules have large
distortion, while on the other hand Copeland and similar mechanisms
perform optimally or near-optimally, always obtaining a distortion of at
most 5. We also give lower bounds on the distortion that could be
obtained by *any* deterministic social choice mechanism, and extend our
results on median agent cost to more general objective functions.

BIO:

Elliot Anshelevich is an Associate Professor in Computer Science at Rensselaer Polytechnic Institute. He received his Ph.D. from Cornell University in 2005, working under the direction of Jon Kleinberg and Eva Tardos. After receiving the NSF Postdoctoral Fellowship in Mathematics, he spent a year at Princeton University working with Moses Charikar. His research interests focus on algorithmic game theory, and more generally algorithms for large decentralised networks. Particular interests include: network design problems with self-interested agents, local and decentralized routing algorithms, approximation algorithms, networked markets, and information propagation in both social and computer networks.