Advertisement
Published in:
2019 | OriginalPaper | Chapter
Robustness Radius for Chamberlin-Courant on Restricted Domains
Authors : Neeldhara Misra, Chinmay Sonar
Published in: SOFSEM 2019: Theory and Practice of Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.