An Impossibility Result for Strongly Group-Strategyproof Multi-winner Approval-Based Voting
摘要
Multi-winner approval-based voting has received considerable attention recently, as an election format. A voting rule in this setting takes as input ballots in which each agent approves a subset of the available alternatives and outputs a committee of alternatives of a given size k. We consider the scenario when a coalition of agents can act strategically and alter their ballots so that the new outcome is strictly better for some coalition member and at least as good for anyone else in the coalition. Voting rules that are robust against this strategic behaviour are called strongly group-strategyproof. We prove that, for \(k\in \{1,2, \ldots , m-2\}\) , strongly group-strategyproof multi-winner approval-based voting rules which furthermore satisfy the minimum efficiency requirement of unanimity do not exist, where m is the number of available alternatives. Our proof builds a connection to single-winner voting with ranking-based ballots and exploits the infamous Gibbard-Satterthwaite theorem to reach the desired impossibility result. Our result has implications for paradigmatic problems from the area of approximate mechanism design without money and indicates that strongly group-strategyproof mechanisms for minimax approval voting, variants of facility location, and classification can only have an unbounded approximation ratio.