On the Distortion of Multi-winner Election Using Single-Candidate Ballots

paper, we study the distortion bounds for voting mechanisms in multi-winner elections in general metric spaces. Our study pertains to the case in which each voter only reports her favorite candidate amongst m possible choices. Given that candidates’ locations are undisclosed to the mechanism, the mechanism has to form a w-winner committee based solely on the number of votes received by candidates. We establish distortion bounds for both truthful and non-truthful mechanisms. Our research highlights the significance of the σ parameter, which represents the ratio between maximum and minimum distances among all candidate pairs. We show that the distortion is linear in σ. First, we demonstrate that all mechanisms possess a distortion greater than 1+w-1w+1(σ-1). To give an upper bound, we study the Single Non-Transferable Vote (SNTV) mechanism, whose distortion is at most 1+2σ. Second, we retrieve the upper bounds for strategyproof mechanisms. In particular, we infer an upper bound by examining the Random Sequential Dictator mechanism that achieves a distortion less than 1+4σ when w=2.