Robustness Radius for Chamberlin-Courant on Restricted Domains

摘要

The notion of robustness in the context of committee elections was introduced by Bredereck et al. [SAGT 2018] 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 W-hard when parameterized by the size of the committee, k. We complement this result by suggesting an algorithm that is in 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 about rankings and again demonstrate an XP algorithm.