Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
An impossibility result for strongly group-strategyproof multi-winner approval-based voting
arXiv.org
13 Feb 2024
Abstract
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.
Metrics
15 Record Views
Details
- Title
- An impossibility result for strongly group-strategyproof multi-winner approval-based voting
- Creators
- Ioannis CaragiannisRob LeGrandEvangelos MarkakisEmmanouil Pountourakis
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science
- Other Identifier
- 991021869109004721