Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2502.01380 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909544586674176 |
|---|---|
| author | Goel, Ashish Goyal, Mohak Munagala, Kamesh |
| author_facet | Goel, Ashish Goyal, Mohak Munagala, Kamesh |
| contents | We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most $k$, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models in the metric distortion framework, where the voters and alternatives are embedded in a latent metric space, with closer alternative being more desirable for a voter. We posit that the outcome of a small-group interaction optimally uses the voters' collective knowledge of the metric, either deterministically or probabilistically.
We characterize the distortion of our deliberation models for small $k$, showing that groups of size $k=3$ suffice to drive the distortion bound below the deterministic metric distortion lower bound of $3$, and groups of size $4$ suffice to break the randomized lower bound of $2.11$. We also show nearly tight asymptotic distortion bounds in the group size, showing that for any constant $ε> 0$, achieving a distortion of $1+ε$ needs group size that only depends on $1/ε$, and not the number of alternatives. We obtain these results via formulating a basic optimization problem in small deviations of the sum of $i.i.d.$ random variables, which we solve to global optimality via non-convex optimization. The resulting bounds may be of independent interest in probability theory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01380 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Metric Distortion of Small-group Deliberation Goel, Ashish Goyal, Mohak Munagala, Kamesh Computer Science and Game Theory We consider models for social choice where voters rank a set of choices (or alternatives) by deliberating in small groups of size at most $k$, and these outcomes are aggregated by a social choice rule to find the winning alternative. We ground these models in the metric distortion framework, where the voters and alternatives are embedded in a latent metric space, with closer alternative being more desirable for a voter. We posit that the outcome of a small-group interaction optimally uses the voters' collective knowledge of the metric, either deterministically or probabilistically. We characterize the distortion of our deliberation models for small $k$, showing that groups of size $k=3$ suffice to drive the distortion bound below the deterministic metric distortion lower bound of $3$, and groups of size $4$ suffice to break the randomized lower bound of $2.11$. We also show nearly tight asymptotic distortion bounds in the group size, showing that for any constant $ε> 0$, achieving a distortion of $1+ε$ needs group size that only depends on $1/ε$, and not the number of alternatives. We obtain these results via formulating a basic optimization problem in small deviations of the sum of $i.i.d.$ random variables, which we solve to global optimality via non-convex optimization. The resulting bounds may be of independent interest in probability theory. |
| title | Metric Distortion of Small-group Deliberation |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.01380 |