Event
Special Seminar: Olgica Milenkovic, "A Constrained-Distance Based Approach to Social Choice Theory"
Wednesday, October 17, 2012
5:00 p.m.
2460 A.V. Williams Building
Prakash Narayan
301 405 3661
prakash@umd.edu
Control, Communications and Signal Processing Seminar
A Constrained-Distance Based Approach to Social Choice Theory
Olgica Milenkovic
Department of Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Hosts: Prakash Narayan and Alexander Barg
Abstract
We consider a classical problem in social choice theory vote aggregation using a novel analytical framework based on distance measures between rankings. The distance measures are derived through an axiomatic approach, taking into account various issues arising in voting with side constraints such as non-uniform relevance between the top and the bottom of rankings (or equivalently, eliminating negative outlier votes). The proposed distance functions may be seen as weighted versions of Kendalls τ distance measure. In addition to proposing the distance measures and providing the theoretical underpinnings for their applications, we also consider algorithmic aspects associated with the distance-based aggregation processes. We focus on a method based on approximating weighted distance measures by a generalized version of Spearmans footrule distance, with provable constant approximation guarantees, and a method based on the PageRank algorithm.
This is a joint work with Farzad Farnoud and Behrouz Touri.