Spatial Voting with Incomplete Voter Information
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913472493649920 |
|---|---|
| author | Imber, Aviram Israel, Jonas Brill, Markus Shachnai, Hadas Kimelfeld, Benny |
| author_facet | Imber, Aviram Israel, Jonas Brill, Markus Shachnai, Hadas Kimelfeld, Benny |
| contents | We consider spatial voting where candidates are located in the Euclidean $d$-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_08929 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Spatial Voting with Incomplete Voter Information Imber, Aviram Israel, Jonas Brill, Markus Shachnai, Hadas Kimelfeld, Benny Computer Science and Game Theory Computational Complexity We consider spatial voting where candidates are located in the Euclidean $d$-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions. |
| title | Spatial Voting with Incomplete Voter Information |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2302.08929 |