Weakly and Strongly Popular Rankings

Van Zuylen et al. introduced the notion of a popular ranking in a voting context, where each voter submits a strictly ordered list of all candidates. A popular ranking pi of the candidates is better than any other ranking sigma in the following sense: if we compare pi to sigma, a majority of all voters will always weakly prefer pi. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity---as applied to popular matchings, a well-established topic in computational social choice---is stricter, because it requires a majority of voters who are not indifferent between pi and sigma to prefer pi. In this talk, I will present structural and algorithmic results in both settings, also improving upon the results of van Zuylen et al. I will also point out strong connections to the famous open problem of finding a Kemeny consensus with 3 voters.

Joint work with Sonja Kraiczy and David Manlove.

To view the seminar recording, click here