On Weakly and Strongly Popular Rankings

Kraiczy, Sonja and Cseh, Ágnes and Manlove, David (2023) On Weakly and Strongly Popular Rankings. DISCRETE APPLIED MATHEMATICS : THE JOURNAL OF COMBINATORIAL ALGORITHMS, INFORMATICS AND COMPUTATIONAL SCIENCES, 340. pp. 134-152. ISSN 0166-218X (print); 1872-6771 (online)

Preview

Text dam.pdf Available under License Creative Commons Attribution. Download (646kB) | Preview

Abstract

Van Zuylen et al. (2014) introduced the notion of a popular ranking in a voting context, where each voter submits a strict ranking 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 pi to sigma, at least half 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 at least half of the voters who are not indifferent between pi and sigma to prefer pi. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results in Van Zuylen et al. (2014). We also point out connections to the famous open problem of finding a Kemeny consensus with three voters.

Actions (login required)

Edit Item