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 Kendall’s τ 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 Spearman’s 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.

Audience: Graduate  Undergraduate  Faculty  Post-Docs  Alumni