Parameterized Intractability for Multi-Winner Election under the Chamberlin-Courant Rule and the Monroe Rule
Answering an open question by Betzler et al. [Betzler et al., JAIR'13], we resolve the parameterized complexity of the multi-winner determination problem under two famous representation voting rules: the Chamberlin-Courant (in short CC) rule [Chamberlin and Courant, APSR'83] and the Monroe rule [Monroe, APSR'95]. We show that under both rules, the problem is W[1]-hard with respect to the sum $\beta$ of misrepresentations, thereby precluding the existence of any $f(\beta) \cdot |I|^{O(1)}$ -time algorithm, where $|I|$ denotes the size of the input instance.
Code (0)
등록된 구현이 없습니다.
Tasks
Open-Ended Question AnsweringSimilar Papers 제목 키워드 기반
Complexity of Shift Bribery in Committee Elections
Given an election, a preferred candidate p, and a budget, the SHIFT BRIBERY problem asks whether p can win the election after shifting p higher in some voters' preference orders. Of course, shifting comes at a price (dep…
DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections
The study of fairness in multiwinner elections focuses on settings where candidates have attributes. However, voters may also be divided into predefined populations under one or more attributes (e.g., "California" and "I…
AttributeDiversityFairnessElections with Few Voters: Candidate Control Can Be Easy
We study the computational complexity of candidate control in elections with few voters, that is, we consider the parameterized complexity of candidate control in elections with respect to the number of voters as a param…
Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules
We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) and the bribery actions are limited to: adding an approval to a vote, …
Sampling-Based Winner Prediction in District-Based Elections
In a district-based election, we apply a voting rule $r$ to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-base…
Prediction