(Joint work with Farzad Farnoud and Behrouz Touri)

Vote aggregation has a long history, dating back as early to the first democratic elections held in the polis of Athens under the government of Solon and Cleisthenis. In the early voting processes, one usually had two candidates to choose from, so that the problem of determining the winner reduced to simple majority (plurality) vote counting. In more recent political history, it was recognized that plurality methods for multiple candidate voting systems are plagued by a number of issues. These issues were most succinctly identified by de Borda and de Condorcet, and pertain to the fact that votes may be non-transitive and that "strong candidates" may loose out to "weak candidates" due to their close mutual competition.

The above described issues with aggregating multiple votes lead to a line of work centered around the use of distance measures between votes and an underlying axiomatic approach.  The idea behind the approach is that the aggregation problem is equivalent to evaluating the median of a set of points (permutations) in a given metric space. Well known metrics include Kendall's tau and Spearman's Footrule.

One of the drawbacks of aforementioned distance-based aggregation methods is that the distance functions do not cater to the need of certain applications, were similar items are to be treated similarly in the aggregation process, and where the top and the bottom of the list carry different relevance to the ranking procedure. One example for the first scenario may be in ranking candidates for a number of positions requiring that some diversity criteria be met, while an example for the second scenario may be in ranking candidates where only a small fraction at the top is considered for a position.

We describe a novel family of distance measures that addresses the issue of costs of rankings, and propose a number of rank aggregation algorithms based on this distance measure. The algorithms either have a constant approximation guarantee for the cost of the aggregate, or they represent heuristic methods based on Markov chain modeling that offer similar simulation-based performance. We conclude the talk by describing a number of interesting problems arising in distributed vote aggregation over networks.