An impossibility result for strongly group-strategyproof multi-winner approval-based voting
<|reference_start|>An impossibility result for strongly group-strategyproof multi-winner approval-based voting: Multi-winner approval-based voting has received considerable attention recently. 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 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 a 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, ..., 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.<|reference_end|>
@article{caragiannis2024an,
    title={An impossibility result for strongly group-strategyproof multi-winner
  approval-based voting},
    author={Ioannis Caragiannis and Rob LeGrand and Evangelos Markakis and
  Emmanouil Pountourakis},
    journal={arXiv preprint arXiv:2402.08746},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.08746},
    primaryClass={cs.GT}
}