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.