  We introduce a novel definition for a small set R of k points being
"representative" of a larger set in a metric space. Given a set V (e.g.,
documents or voters) to represent, and a set C of possible representatives, our
criterion requires that for any subset S comprising a theta fraction of V, the
average distance of S to their best theta*k points in R should not be more than
a factor gamma compared to their average distance to the best theta*k points
among all of C. This definition is a strengthening 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 gamma 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/alpha, for alpha > 1. Furthermore, motivated by the application to
elections, we mostly focus on the "ordinal" model, where the algorithm does not
learn the actual distances; instead, it learns only for each point v in V and
each candidate pairs c, c' which of c, c' is closer to v. Our main result is
that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma)
representative with gamma <= 1 + 6.71 * (alpha)/(alpha-1).
  Our results lead to three notable byproducts. First, we show that the EAR
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 EAR 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.
