Constant-Factor Distortion Mechanisms for k-Committee Election

I think there is a credible, though qualified, continuous mirror. My lead anchor is Theorem 3.10, proved in this paper. It gives Mechanism 3 with per-agent query complexity \(\widetilde O\!\left(k\log(1/\delta)\log(\min\{\ell,n/\ell\})\right)\) and \(O(1)\) distortion for the \(\ell\)-centrum problem.

The natural high-multiplicity setting is a large electorate choosing a committee of \(k\) candidates or policy platforms. Let \(A\) be the finite candidate set. A type \(t\) consists of a complete ranking \(\succ_t\) together with its distances \(d(t,a)\) to all \(a\in A\), induced by a common metric on voter locations and candidates. The society is a rational distribution \(\mu\) over a finite type set \(T\), with \(|T|=\tau\). Thus millions of voters may occupy only a few dozen or hundred ideological, demographic, or geographic types.

For \(\lambda\in(0,1]\), define the cost of a committee \(S\subseteq A\), \(|S|\le k\), by

\[ \Phi_{\lambda}(\mu,d,S) = \max_{\substack{0\le z_t\le \mu_t\\ \sum_t z_t=\lambda}} \sum_{t\in T} z_t\,d(t,S), \qquad d(t,S)=\min_{a\in S}d(t,a). \]

This is the total cost of the worst \(\lambda\)-fraction of the population. Equivalently,

\[ \Phi_{\lambda}(\mu,d,S) = \min_{\rho\ge 0} \left\{ \lambda\rho+ \sum_{t\in T}\mu_t(d(t,S)-\rho)_+ \right\}. \]

If a discrete electorate has \(N\) voters, \(\mu_t=n_t/N\), and \(\lambda=\ell/N\), then \(\Phi_\lambda\) is exactly \(N^{-1}\operatorname{Top}_{\ell}\). This is therefore a genuine high-multiplicity relaxation, not merely an analogy.

I would name the lead problem \(\textsf{HM-Top}_{\lambda}\textsf{-Committee with Type Queries}\). Its input is \(A,k,\lambda,T,\mu\), the rankings \(\succ_t\), and oracle access to the hidden metric through queries returning \(d(t,a)\). A solution is a committee \(S\) with \(|S|\le k\) such that, with probability at least \(1-\delta\),

\[ \Phi_{\lambda}(\mu,d,S) \le \alpha\min_{|S'|\le k}\Phi_{\lambda}(\mu,d,S') \]

for a universal constant \(\alpha\). The query budget is charged per distinct type, not per voter. The natural target is a polynomial, preferably polylogarithmic-in-population, number of type queries; one representative query can reveal a distance shared by an entire cohort.

I expect this problem to be tractable for constant-factor approximation, hence Class A in the approximation sense. The paper’s central device survives exactly: the Top-\(\ell\) objective becomes the separable weighted expression above. Adaptive sampling becomes sampling types proportionally to their mass and proxy cost, and the sparsification step becomes aggregation of voters around \(O(k)\) weighted representatives. The exact optimization problem should still be hard: at \(\lambda=1\), it contains weighted metric \(k\)-median. Thus the honest claim is not that continuization makes exact committee selection easy, but that it creates a clean weighted approximation and limited-information problem.

The authors should recognise this as their problem. The committee, metric consistency, rankings, cardinal value queries, and worst-\(\lambda\)-fraction objective are unchanged. Only the electorate is represented by masses. It also fits their Section 4 setting \(A\ne C\), which is the appropriate version for many voters and a fixed candidate set.

A useful secondary anchor is Theorem 3.1, whose direct proof is included in the paper’s full version, although the paper notes that the result also follows from Caragiannis, Shah, and Voudouris (2022). It states that for \(k\)-median with \(k\ge3\), ordinal information alone permits unbounded distortion. Its continuous counterpart is the precise question \(\textsf{HM-Ordinal-Top}_1(k)\): given only \((A,k,T,\mu,\succ)\), can a rule choose \(S\) whose cost is within a universal constant of the optimum for every compatible metric? The expected answer is no. A discrete lower-bound instance can be duplicated many times without changing its normalized distortion, producing \(N\gg\tau\). This shows that the continuous mirror preserves the paper’s information-theoretic boundary as well as its positive query-based result.

The weakest point is that Theorem 3.10 is stated primarily for \(A=C\), while the high-multiplicity scenario naturally has \(A\ne C\); the paper only sketches that extension in the supplied version. More importantly, replacing per-agent queries by per-type queries is a new information model whose guarantees are not proved here. The continuous mirror is therefore strongest as a precisely posed weighted \(\ell\)-centrum approximation problem, with the type-query analogue as a well-motivated research question rather than an established theorem.

It generates several concrete follow-ups: whether the adaptive-sampling proof extends to arbitrary rational masses, how query complexity depends on \(\lambda\), whether exact weighted versions are fixed-parameter tractable in \(k+\tau\), and which parts of the ordinal lower bound survive when the support has very few types.