Proportional Representation in Metric Spaces and Low-Distortion Committee

There is a credible continuous mirror here, strongest for the paper’s population-level proportional-representation guarantee. I would not claim that the paper supplies a complexity classification in the usual NP-hard/P sense: its named computational results are approximation guarantees and algorithms. But those results continuize naturally.

The right regime is a large electorate or population choosing a small committee of representatives or facilities. Let \(C\) be the finite candidate set and \(k\) the committee size. A voter type is a repeated location or cost profile: agents of type \(t\) have the same candidate distances and hence the same ranking \(\succ_t\). The society is a rational distribution \(\mu\) over the finite type set \(T\). For example, millions of residents may occupy a few hundred neighbourhood or ideological cells, all facing the same small slate of candidate facilities. Thus \(n\gg \tau\), while \(m,k,\tau\) remain moderate.

The continuous action is still a discrete committee \(R\subseteq C\), \(|R|=k\). Only the population is continuized. In the ordinal version, the algorithm sees \((T,\mu,\succ)\), not the distances. A latent pseudometric \(d\) on \(T\cup C\) is required to be consistent with the rankings, and the guarantee is required for every such \(d\). In the cardinal version, \(d\) is simply supplied as part of the type information.

My lead anchor is Theorem 4.1, proved in this paper:

The EXPANDING APPROVALS RULE outputs a committee that is \((\alpha,\gamma(\alpha))\)-proportionally representative for every \(\alpha>1\), where
\[ > \gamma(\alpha) > = > 1+\frac{7+\sqrt{41}}{2}\frac{\alpha}{\alpha-1}. > \]

The corresponding continuous problem is:

Continuum Proportional Representation (\(\mathrm{CPR}_\infty\)). An instance consists of \(C,k,\alpha\), a finite type set \(T\), a rational distribution \(\mu\), and rankings \(\succ_t\). Find a committee \(R\subseteq C\), \(|R|=k\), such that, for every compatible metric \(d\), every integer \(j\) with \(j\alpha/k\le1\), and every coalition subdistribution \(\sigma\) satisfying \(0\le\sigma_t\le\mu_t\) and \(\sum_t\sigma_t\ge j\alpha/k\),

\[ \sum_{t\in T}\sigma_t \min_{\substack{R'\subseteq R\\|R'|=j}} \sum_{r\in R'}d(t,r) \le \gamma(\alpha) \min_{\substack{C'\subseteq C\\|C'|=j}} \sum_{t\in T}\sigma_t\sum_{c\in C'}d(t,c). \]

A solution is one committee satisfying all these coalition and \(j\)-level constraints. Equivalently, one can ask for the committee minimizing the worst representation factor.

This is very close to the paper’s exact question. The paper’s \(|S|\ge j\alpha p\) becomes coalition mass at least \(j\alpha/k\); sums over voters become integrals or weighted sums; and the “best \(j\) representatives” condition is unchanged. Resource augmentation also survives honestly: \(\alpha>1\) means the guarantee is demanded only from coalitions larger than their nominal proportional share.

The continuous Expanding Approvals Rule maintains uncovered mass by type and candidate approval-pool mass. When a candidate’s pool reaches \(1/k\), it is selected and that mass is removed from the remaining pools. It never needs to expand the population into \(n\) named voters. For rational \(\mu\), choose \(n\) divisible by \(k\), create \(n\mu_t\) identical copies of each type, and apply the paper’s finite algorithm. The continuous formulation is therefore an exact high-multiplicity version, not merely an analogy. The aggregated implementation should be polynomial in \(m,\tau\), and the encoding length of \(\mu\).

I expect \(\mathrm{CPR}_\infty\) to be Class A for the guarantee version: the paper’s structural argument and the mass version of Expanding Approvals provide a direct algorithm. The exact optimum representation factor remains a worthwhile continuous-optimization question. In particular, one could ask for an efficient separation method for the worst coalition, improve the constant \(\gamma(\alpha)\), or determine whether the resource augmentation can approach \(\alpha=1\). Propositions 2.4 and 2.5, although not separate anchors here, suggest that the need for approximation and resource augmentation is not a finite-population artefact: rational bad instances can be replicated proportionally.

A second, cleaner anchor is Corollary 4.5, proved in this paper, though its majority-distortion step invokes Lemma 6 of Anshelevich et al. (2018). It states that a simple rule has metric distortion at most \(44\).

The corresponding problem is:

Continuum Ordinal Low-Distortion Winner (\(\mathrm{COLDW}_\infty\)). Given \(C,T,\mu\), and rankings \(\succ_t\), run the continuous Expanding Approvals Rule with \(k=2\) and quota \(1/2\), obtaining candidates \(a,b\). Return whichever of \(a,b\) is preferred by at least half the population, breaking ties deterministically. The required guarantee is that for every compatible metric \(d\),

\[ \sum_t\mu_t d(t,w) \le 44\min_{c\in C}\sum_t\mu_t d(t,c). \]

This is precisely the paper’s single-winner corollary with voter counts replaced by population mass. The majority argument and all metric-cost inequalities extend from sums to weighted sums. I expect this problem also to be Class A, with a constant-factor ordinal algorithm. The exact optimal distortion for a given distribution, and the best possible rule under the continuous model, are further questions.

I would not use Corollary 4.3 as a separate anchor. Its definition says that a coalition contains at least one suitably represented voter; under a continuum, “one voter” can have zero mass and becomes a poor population-level requirement. The integral coalition guarantees in Theorem 4.1 and Corollary 4.4 are much safer mirrors. Similarly, Theorem 4.2’s \(O(n/k)\) bound has no useful scale-free limit when \(n\) disappears, so I would not present it as a successful continuous result.

The main weakness is that the paper itself does not formulate the mass version, and its ordinal model hides the metric. A sceptic could argue that requiring one shared metric witness over voter types creates a new robust problem. The answer is that the construction can instead use repeated co-located metric types, making the high-multiplicity interpretation exact; and for rational distributions the finite theorem transfers by literal replication. The mirror therefore preserves the paper’s candidates, rankings, metric objective, coalitions, committees, and resource-augmentation tradeoff. It only replaces irrelevant voter identities by mass.

So the strongest positive case is narrow but solid: Theorem 4.1 yields a genuine continuous-population committee problem with a natural Class A algorithmic guarantee, and Corollary 4.5 yields a particularly transparent distributional voting mirror.