Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Robustness Radius for Chamberlin-Courant on Restricted Domains
verfasst von : Neeldhara Misra, Chinmay Sonar
Erschienen in: SOFSEM 2019: Theory and Practice of Computer Science
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 notion of robustness in the context of committee elections was introduced by Bredereck et al. [SAGT 2018] [2] to capture the impact of small changes in the input preference orders, depending on the voting rules used. They show that for certain voting rules, such as Chamberlin-Courant, checking if an election instance is robust, even to the extent of a small constant, is computationally hard. More specifically, it is NP-hard to determine if one swap in any of the votes can change the set of winning committees with respect to the Chamberlin-Courant voting rule. Further, the problem is also \(\mathsf {W[1]}\)-hard when parameterized by the size of the committee, k. We complement this result by suggesting an algorithm that is in \(\mathsf {XP}\) with respect to k. We also show that on nearly-structured profiles, the problem of robustness remains NP-hard. We also address the case of approval ballots, where we show a hardness result analogous to the one established in [2] about rankings and again demonstrate an \(\mathsf {XP}\) algorithm.