On the Distortion of Multi-winner Election Using Single-Candidate Ballots
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908382120640512 |
|---|---|
| author | Auricchio, Gennaro Ren, Zeyu Wang, Zihe Zhang, Jie |
| author_facet | Auricchio, Gennaro Ren, Zeyu Wang, Zihe Zhang, Jie |
| contents | In this 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+\frac{w-1}{w+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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_09386 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Distortion of Multi-winner Election Using Single-Candidate Ballots Auricchio, Gennaro Ren, Zeyu Wang, Zihe Zhang, Jie Computer Science and Game Theory In this 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+\frac{w-1}{w+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$. |
| title | On the Distortion of Multi-winner Election Using Single-Candidate Ballots |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2205.09386 |