Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
On the Complexity of Chamberlin-Courant on Almost Structured Profiles
verfasst von : Neeldhara Misra, Chinmay Sonar, P. R. Vaidyanathan
Erschienen in: Algorithmic Decision Theory
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The Chamberlin-Courant voting rule is an important multiwinner voting rule. Although \(\mathsf {NP}\)-hard to compute on general profiles, it is known to be polynomially solvable on single-crossing and single-peaked electorates by exploiting the structures of these domains. We consider the problem of generalizing the domain on which the voting rule admits efficient algorithms.
On the one hand, we show efficient algorithms on profiles that are
candidates or
voters away from the single-peaked and single-crossing domains. In particular, for profiles that are
candidates away from being single-peaked or single-crossing, we show algorithms whose running time is \(\mathsf {FPT}\) in
. For profiles that are
voters away from being single-peaked or single-crossing, our algorithms are \(\mathsf {XP}\) in
. These algorithms are obtained by a careful extension of known algorithms on structured profiles [2, 12]. This provides a natural application for the work by Elkind and Lackner in [9], who study the problem of finding deletion sets to single-peaked and single-crossing profiles.
candidates or
voters away from the single-peaked and single-crossing domains. In particular, for profiles that are
candidates away from being single-peaked or single-crossing, we show algorithms whose running time is \(\mathsf {FPT}\) in
. For profiles that are
voters away from being single-peaked or single-crossing, our algorithms are \(\mathsf {XP}\) in
. These algorithms are obtained by a careful extension of known algorithms on structured profiles [2, 12]. This provides a natural application for the work by Elkind and Lackner in [9], who study the problem of finding deletion sets to single-peaked and single-crossing profiles.In contrast to these results, for a different, but equally natural way of generalizing these domain, we show severe intractability results. In particular, we show that the problem is \(\mathsf {NP}\)-hard on profiles that can be “decomposed” into a constant number of single-peaked profiles. Also, if the number of crossings per pair of candidates in a profile is permitted to be at most three (instead of one), the problem continues be \(\mathsf {NP}\)-hard. This stands in contrast with other attempts at generalizing these domains (such as single-peaked or single-crossing width), as it rules out the possibility of fixed-parameter (or even \(\mathsf {XP}\)) algorithms when parameterized by the number of peaks, or the maximum number of crossings per candidate pair.
