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 \(\sigma \) parameter, which represents the ratio between maximum and minimum distances among all candidate pairs. We show that the distortion is linear in \(\sigma \) . First, we demonstrate that all mechanisms possess a distortion greater than \(1+\frac{w-1}{w+1}(\sigma -1)\) . To give an upper bound, we study the Single Non-Transferable Vote (SNTV) mechanism, whose distortion is at most \(1+2\sigma \) . 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\sigma \) when \(w=2\) .