Bi-Criteria Metric Distortion
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913611540070400 |
|---|---|
| author | Banihashem, Kiarash Chakraborty, Diptarka Jahan, Shayan Chashm Gholami, Iman Hajiaghayi, MohammadTaghi Mahdavi, Mohammad Springer, Max |
| author_facet | Banihashem, Kiarash Chakraborty, Diptarka Jahan, Shayan Chashm Gholami, Iman Hajiaghayi, MohammadTaghi Mahdavi, Mohammad Springer, Max |
| contents | Selecting representatives based on voters' preferences is a fundamental problem in social choice theory. While cardinal utility functions offer a detailed representation of preferences, ordinal rankings are often the only available information due to their simplicity and practical constraints. The metric distortion framework addresses this issue by modeling voters and candidates as points in a metric space, with distortion quantifying the efficiency loss from relying solely on ordinal rankings. Existing works define the cost of a voter with respect to a candidate as their distance and set the overall cost as either the sum (utilitarian) or maximum (egalitarian) of these costs across all voters. They show that deterministic algorithms achieve a best-possible distortion of 3 for any metric when considering a single candidate.
This paper explores whether one can obtain a better approximation compared to an optimal candidate by relying on a committee of $k$ candidates ($k \ge 1$), where the cost of a voter is defined as its distance to the closest candidate in the committee. We answer this affirmatively in the case of line metrics, demonstrating that with $O(1)$ candidates, it is possible to achieve optimal cost. Our results extend to both utilitarian and egalitarian objectives, providing new upper bounds for the problem. We complement our results with lower bounds for both the line and 2-D Euclidean metrics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10671 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Bi-Criteria Metric Distortion Banihashem, Kiarash Chakraborty, Diptarka Jahan, Shayan Chashm Gholami, Iman Hajiaghayi, MohammadTaghi Mahdavi, Mohammad Springer, Max Computer Science and Game Theory Data Structures and Algorithms Selecting representatives based on voters' preferences is a fundamental problem in social choice theory. While cardinal utility functions offer a detailed representation of preferences, ordinal rankings are often the only available information due to their simplicity and practical constraints. The metric distortion framework addresses this issue by modeling voters and candidates as points in a metric space, with distortion quantifying the efficiency loss from relying solely on ordinal rankings. Existing works define the cost of a voter with respect to a candidate as their distance and set the overall cost as either the sum (utilitarian) or maximum (egalitarian) of these costs across all voters. They show that deterministic algorithms achieve a best-possible distortion of 3 for any metric when considering a single candidate. This paper explores whether one can obtain a better approximation compared to an optimal candidate by relying on a committee of $k$ candidates ($k \ge 1$), where the cost of a voter is defined as its distance to the closest candidate in the committee. We answer this affirmatively in the case of line metrics, demonstrating that with $O(1)$ candidates, it is possible to achieve optimal cost. Our results extend to both utilitarian and egalitarian objectives, providing new upper bounds for the problem. We complement our results with lower bounds for both the line and 2-D Euclidean metrics. |
| title | Bi-Criteria Metric Distortion |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.10671 |