On Weakly and Strongly Popular Rankings

Van Zuylen et al. [26] 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 π of the candidates is at least as good as any other ranking σ in the following sense: if we compare π to σ , at least half of all voters will always weakly prefer π. 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 choiceis stricter, because it requires at least half of the voters who are not indifferent between π and σ to prefer π. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results in [26]. We also point out connections to the famous open problem of finding a Kemeny consensus with 3 voters.