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

[Walker, Lashauna]

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.



Thank You.

LaShauna Walker
Executive Assistant to Dean Carla Brodley
College of Computer and Information Science
Northeastern University
617-373-5204
Facebook<https://www.facebook.com/ccisatnu?ref=hl> | Instagram<https://instagram.com/ccisatnu/> | LinkedIn<https://www.linkedin.com/groups/Northeastern-University-College-Computer-Information-1943637?gid=1943637&mostPopular=&trk=tyah&trkInfo=idx%3A1-1-1%2CtarId%3A1426606862845%2Ctas%3ANortheastern+University+College+of+Com> | Twitter<https://twitter.com/CCISatNU>