Logo image
Back
An Impossibility Result for Strongly Group-Strategyproof Multi-winner Approval-Based Voting
Book chapter

An Impossibility Result for Strongly Group-Strategyproof Multi-winner Approval-Based Voting

Ioannis Caragiannis, Rob LeGrand, Evangelos Markakis and Emmanouil Pountourakis
Web and Internet Economics, pp 457-475
2026
DOI: https://doi.org/10.1007/978-3-032-08560-3_26

Abstract

approval voting computational social choice mechanism design
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∈1,2,…,m-2 $$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.

Metrics

5 Record Views

Details

Logo image