Proportional Representation in Metric Spaces and Low-Distortion Committee Selection

We propose and analyze a natural new definition for when a small set R of k points in a metric space is representative of a larger set. There is a set V of points to be represented (such as documents or voters), and a set C of candidates (also documents, or candidates for office) who could represent them. Our definition states (essentially) that for any set S ⊆ V of points comprising a θ fraction of V , the average distance of S to their respective best θk points in R should not be larger by more than a factor γ compared to their average distance to the best θk points among all of C. This definition is a strengthening of the notions of proportional fairness and core fairness, but -different from those notions -requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which -unless γ is polynomially large -no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/α, for α > 1. Furthermore, motivated by the application to elections, we mostly focus on the ordinal model, in which the algorithm does not learn the actual distances; instead, the algorithm learns only for each point v ∈ V and each pair of candidates c, c ′ which of c, c ′ is closer to v. Our main result is that the Expanding Approvals Rule of Aziz and Lee is (α, γ) representative in our sense with γ ≈ 1 + 6.71 • α α-1 . We also obtain three novel byproducts and corollaries from our analysis. First, we show that the Expanding Approvals Rule achieves constant proportional fairness in the ordinal model, giving the first positive result on metric proportional fairness with ordinal information. Second, we show that for the core fairness objective, the Expanding Approvals Rule achieves the same asymptotic tradeoff between resource augmentation and approximation as the recent results of Li et al., which used full knowledge of the metric. Finally, our results imply a very simple single-winner voting rule with metric distortion at most 44.