Metric Distortion of Small-Group Deliberation

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.

Authors

• Ashish Goel
• Mohak Goyal
• Kamesh Munagala

Keywords

• Copeland rule
• Deliberation
• Metric distortion
• Social choice