Metric Distortion of Line-up Elections: The Right Person for the Right Job
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912243030949888 |
|---|---|
| author | Jerrett, Christopher Han, Yue Anshelevich, Elliot |
| author_facet | Jerrett, Christopher Han, Yue Anshelevich, Elliot |
| contents | We provide mechanisms and new metric distortion bounds for line-up elections. In such elections, a set of $n$ voters, $m$ candidates, and $\ell$ positions are all located in a metric space. The goal is to choose a set of candidates and assign them to different positions, so as to minimize the total cost of the voters. The cost of each voter consists of the distances from itself to the chosen candidates (measuring how much the voter likes the chosen candidates, or how similar it is to them), as well as the distances from the candidates to the positions they are assigned to (measuring the fitness of the candidates for their positions). Our mechanisms, however, do not know the exact distances, and instead produce good outcomes while only using a smaller amount of information, resulting in small distortion.
We consider several different types of information: ordinal voter preferences, ordinal position preferences, and knowing the exact locations of candidates and positions, but not those of voters. In each of these cases, we provide constant distortion bounds, thus showing that only a small amount of information is enough to form outcomes close to optimum in line-up elections. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04020 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Metric Distortion of Line-up Elections: The Right Person for the Right Job Jerrett, Christopher Han, Yue Anshelevich, Elliot Computer Science and Game Theory Data Structures and Algorithms We provide mechanisms and new metric distortion bounds for line-up elections. In such elections, a set of $n$ voters, $m$ candidates, and $\ell$ positions are all located in a metric space. The goal is to choose a set of candidates and assign them to different positions, so as to minimize the total cost of the voters. The cost of each voter consists of the distances from itself to the chosen candidates (measuring how much the voter likes the chosen candidates, or how similar it is to them), as well as the distances from the candidates to the positions they are assigned to (measuring the fitness of the candidates for their positions). Our mechanisms, however, do not know the exact distances, and instead produce good outcomes while only using a smaller amount of information, resulting in small distortion. We consider several different types of information: ordinal voter preferences, ordinal position preferences, and knowing the exact locations of candidates and positions, but not those of voters. In each of these cases, we provide constant distortion bounds, thus showing that only a small amount of information is enough to form outcomes close to optimum in line-up elections. |
| title | Metric Distortion of Line-up Elections: The Right Person for the Right Job |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.04020 |