Metric Distortion in Peer Selection
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911211478581248 |
|---|---|
| author | Cembrano, Javier Shahkarami, Golnoosh |
| author_facet | Cembrano, Javier Shahkarami, Golnoosh |
| contents | In the metric distortion problem, a set of voters and candidates lie in a common metric space, and a committee of $k$ candidates must be elected. The objective is to minimize a social cost, defined as a function of the distances between voters and their chosen representatives, while the voting rule only has access to ordinal preferences. The distortion of a rule is the worst-case ratio between the social cost of its outcome and that of the optimal committee, taken over all consistent preferences and metrics.
We initiate the study of metric distortion in peer selection, where voters and candidates coincide. We consider four objectives, obtained by combining two aggregation rules with two types of social cost. Under additive aggregation, an individual's cost is the sum of their distances to all committee members; under $q$-cost, it is their distance to the $q$th closest member. The overall social cost is either utilitarian, given by the sum of all individual costs, or egalitarian, given by the maximum individual cost. Surprisingly, we find that even on the line metric, peer selection retains much of the hardness of the general case: Lower bounds remain strictly larger than one for all objectives, and cases where bounded distortion is impossible in general remain so here as well. On a positive note, cases with bounded distortion in the general setting achieve better constants in peer selection. For utilitarian cost, selecting the $k$ middle agents achieves a distortion between $1$ and $2$ under additive aggregation. Under $q$-cost, we show positive results for $q=k=2$, but impossibility results largely carry over. For egalitarian cost, selecting the extremes yields an optimal distortion of $2$ under additive aggregation and for $q$-cost with $q>k/3$. Thus, while peer selection on the line metric allows better constants, fundamental hardness barriers persist. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_21084 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Metric Distortion in Peer Selection Cembrano, Javier Shahkarami, Golnoosh Computer Science and Game Theory In the metric distortion problem, a set of voters and candidates lie in a common metric space, and a committee of $k$ candidates must be elected. The objective is to minimize a social cost, defined as a function of the distances between voters and their chosen representatives, while the voting rule only has access to ordinal preferences. The distortion of a rule is the worst-case ratio between the social cost of its outcome and that of the optimal committee, taken over all consistent preferences and metrics. We initiate the study of metric distortion in peer selection, where voters and candidates coincide. We consider four objectives, obtained by combining two aggregation rules with two types of social cost. Under additive aggregation, an individual's cost is the sum of their distances to all committee members; under $q$-cost, it is their distance to the $q$th closest member. The overall social cost is either utilitarian, given by the sum of all individual costs, or egalitarian, given by the maximum individual cost. Surprisingly, we find that even on the line metric, peer selection retains much of the hardness of the general case: Lower bounds remain strictly larger than one for all objectives, and cases where bounded distortion is impossible in general remain so here as well. On a positive note, cases with bounded distortion in the general setting achieve better constants in peer selection. For utilitarian cost, selecting the $k$ middle agents achieves a distortion between $1$ and $2$ under additive aggregation. Under $q$-cost, we show positive results for $q=k=2$, but impossibility results largely carry over. For egalitarian cost, selecting the extremes yields an optimal distortion of $2$ under additive aggregation and for $q$-cost with $q>k/3$. Thus, while peer selection on the line metric allows better constants, fundamental hardness barriers persist. |
| title | Metric Distortion in Peer Selection |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.21084 |