An impossibility result for strongly group-strategyproof multi-winner approval-based voting
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914677843296256 |
|---|---|
| author | Caragiannis, Ioannis LeGrand, Rob Markakis, Evangelos Pountourakis, Emmanouil |
| author_facet | Caragiannis, Ioannis LeGrand, Rob Markakis, Evangelos Pountourakis, Emmanouil |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08746 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An impossibility result for strongly group-strategyproof multi-winner approval-based voting Caragiannis, Ioannis LeGrand, Rob Markakis, Evangelos Pountourakis, Emmanouil Computer Science and Game Theory 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. |
| title | An impossibility result for strongly group-strategyproof multi-winner approval-based voting |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.08746 |