The Power of Two: Optimal Metric Distortion via Dyadic Deliberation

Abstract

We study what happens when preference information is compressed twice in metric social choice: first from hidden cardinal costs to full ordinal rankings, and then from full rankings to pairwise comparisons. The first compression already limits what a rule can know; the second makes elicitation scalable, but it discards additional relational structure and weakens deterministic distortion guarantees. We ask whether pairwise data can be enriched just enough to recover the well-known distortion-$3$ guarantee available from full rankings, while keeping the tournament-style format that makes pairwise methods attractive.We introduce Deliberation via Matching, a protocol that, for each pair of candidates, matches voters who disagree on that pair, lets each matched dyad choose the candidate with lower total cost to the two voters, and combines these dyadic outcomes with the original votes into a weighted tournament. Applying a weighted uncovered-set rule to this enriched tournament achieves distortion $3$ for an appropriate choice of parameters. In this sense, minimal dyadic deliberation lets tournament aggregation recover the deterministic full-ranking guarantee, while breaking past the lower-bound barrier known for deterministic tournament rules without deliberation.Our analysis rewrites the worst-case distortion problem as a bilinear optimization and then uses structural reductions to collapse extremal instances to a finite-dimensional program. We also give a sampling-based implementation that achieves distortion $3 + \epsilon$ with high probability while keeping per-voter participation very low in large electorates. Finally, we prove complementary lower bounds showing both the optimality of the distortion-$3$ guarantee for our protocol and broader limitations of dyadic deliberation.