Literature by the same author
plus at Google Scholar

Bibliografische Daten exportieren
 

On weakly and strongly popular rankings

Title data

Kraiczy, Sonja ; Cseh, Ágnes ; Manlove, David:
On weakly and strongly popular rankings.
In: Discrete Applied Mathematics. Vol. 340 (2023) . - pp. 134-152.
ISSN 1872-6771
DOI: https://doi.org/10.1016/j.dam.2023.06.041

Official URL: Volltext

Abstract in another language

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 π 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 choice—is 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 Van Zuylen et al. (2014). We also point out connections to the famous open problem of finding a Kemeny consensus with three voters.

Further data

Item Type: Article in a journal
Refereed: Yes
Keywords: Majority rule; Kemeny consensus; Complexity; Preference aggregation; Popular matching
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics > Chair Mathematical Economics - Univ.-Prof. Dr. Jörg Rambau
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data > Chair Dynamical Systems and Data - Univ.-Prof. Dr. Peter Koltai
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Dynamical Systems and Data
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Date Deposited: 24 Jul 2023 06:17
Last Modified: 08 Aug 2023 12:55
URI: https://eref.uni-bayreuth.de/id/eprint/86274