Computational Democracy Research Seminar

Title: Title: Weighted Kemeny Rules for Aggregating Pairwise Preferences

Speaker: Patrick Lederer (University of Amsterdam)

Abstract: In rank aggregation, the goal is to compute a collective ranking over some alternatives based on the voters' preferences over these alternatives. While the literature commonly assumes that preferences take the form of full rankings, reported preferences are typically much sparser in modern applications such as crowdsourcing. Motivated by this observation, we study rank aggregation under pairwise preferences, where each voter reports only her preferences between pairs of alternatives of her choice. For this setting, we axiomatically characterize the class of weighted Kemeny rules, which generalize the well-known Kemeny rule by assigning weights to voters based on how many comparisons between alternatives they report. Our characterization of these rules relies on a population consistency notion called reinforcement and a novel axiom called balanced local Condorcet consistency. We also characterize two particularly natural weighted Kemeny rules: the standard Kemeny rule, which weights all voters equally, and the normalized Kemeny rule, where weights are inversely proportional to the number of reported comparisons. Finally, we conduct simulations to better understand the differences in the behavior of our rules.

This is joint work with Ulle Endriss