| paper | Proportional Representation in Metric Spaces and Low-Distortion Committee Selection |
| authors | Y. Kalayci, David Kempe, Vikram Kher |
| venue | AAAI 2024 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 5.1
Given candidates \(C\), \(k<m\), finite voter types \( \Theta \), rational masses \( \mu\in\Delta(\Theta) \), and a known rational pseudo-metric \(d\) on \( \Theta\cup C \), output an integral committee \(R\subseteq C\) with \( |R|=k \) such that, for every \( \alpha>1 \), \(1\le t\le k\), and submass \(0\le\lambda\le\mu\) with \( \sum_{\theta}\lambda_\theta\ge t\alpha/k \), \( \sum_{\theta}\lambda_\theta\min_{\substack{Q\subseteq R\|Q|=t}}\sum_{r\in Q}d(\theta,r)\le\gamma(\alpha)\min_{\substack{Q'\subseteq C\|Q'|=t}}\sum_{\theta}\lambda_\theta\sum_{c\in Q'}d(\theta,c) \), where \( \gamma(\alpha)=1+(2+\sqrt{2})\frac{\alpha}{\alpha-1} \).
A finite-type known-metric population: each type \( \theta\in\Theta \) carries mass \( \mu_\theta \), the decision variable is an integral \(k\)-committee \(R\), and the objective is a constructive worst-coalition representation guarantee over all submasses \( \lambda \).
The mass algorithm may be only a compressed implementation of the finite algorithm, and the exact optimum \( \Gamma(\mu) \) is not anchored by Theorem 5.1; this bounds novelty but does not defeat the stated guarantee problem.
fatal: False
Mirrors the known-metric Truncated Greedy Capture guarantee in Theorem 5.1, using the stability idea of Lemma 5.2; it leaves the ordinal Expanding Approvals results, the \( \alpha=1 \) \(O(n/k)\) theorem, metric-distortion corollaries, lower bounds, and exact optimization of \( \Gamma(\mu) \) separate.
The strongest honest positive case is a high-multiplicity version of the paper’s known-metric committee-selection problem. There is one important qualification: the paper contains no named NP-hardness, \(P\), FPT, or W[1]-hardness result. Its anchors are algorithmic approximation theorems, so this is a weaker ChoCo case than a paper whose discrete hardness might dissolve.
My lead anchor is Theorem 5.1, proved in the paper. It says that, given a finite voter set \(V\), candidates \(C\), committee size \(k\), and a known metric \(d\) on \(V\cup C\), Truncated Greedy Capture outputs a committee \(R\) of size \(k\) that is simultaneously \((\alpha,\gamma(\alpha))\)-proportionally representative for every \(\alpha>1\), where \( \gamma(\alpha)=1+(2+\sqrt{2})\frac{\alpha}{\alpha-1}\approx1+3.42\frac{\alpha}{\alpha-1} \). Concretely, every coalition \(S\) of size at least \(t\alpha\lceil n/k\rceil\) must have aggregate distance to its best \(t\) representatives in \(R\) at most \(\gamma(\alpha)\) times its aggregate distance to the best \(t\) candidates in \(C\). The theorem is proved in the paper, not merely cited. [The full paper states Theorem 5.1 and its algorithm here.](https://arxiv.org/html/2312.10369v2)
The continuous mirror I would propose is Continuous Metric Proportional Committee Selection\(_\infty\).
An instance consists of a finite candidate set \(C\), \(|C|=m\), an integer \(k<m\), a finite set of voter types \(\Theta=\{\theta_1,\ldots,\theta_\tau\}\), rational masses \(\mu_\theta\ge0\) summing to \(1\), and a rational pseudo-metric \(d\) on \(\Theta\cup C\). A type is a complete metric position: all agents of type \(\theta\) have the same distances \(d(\theta,c)\) to every candidate and are therefore indistinguishable for the problem. The decision variable is an ordinary committee \(R\subseteq C\) with \(|R|=k\); representatives are not fractional.
A coalition is a submass vector \(\lambda\) with \(0\le\lambda_\theta\le\mu_\theta\). Its mass is \(M(\lambda)=\sum_\theta\lambda_\theta\). For \(1\le t\le k\), define the committee cost
\(L_R(\lambda,t)=\sum_{\theta\in\Theta}\lambda_\theta\min_{\substack{Q\subseteq R\\|Q|=t}}\sum_{r\in Q}d(\theta,r)\),
and its best available alternative cost
\(O(\lambda,t)=\min_{\substack{Q\subseteq C\\|Q|=t}}\sum_{\theta\in\Theta}\lambda_\theta\sum_{c\in Q}d(\theta,c)\).
For a resource-augmentation parameter \(\alpha\ge1\), the question is to find \(R\) minimizing the smallest \(\gamma\) such that
\(L_R(\lambda,t)\le\gamma O(\lambda,t)\)
for every \(t\) and every coalition submass \(\lambda\) with \(M(\lambda)\ge t\alpha/k\). Equivalently, one may ask for a committee satisfying a supplied target \(\gamma\).
This is exactly the paper’s problem with population counts replaced by mass: \(\sum_{v\in S}\) becomes a weighted sum over types, and the finite Hare quota \(\lceil n/k\rceil\) becomes the per-capita quota \(1/k\). The committee, candidate set, metric objective, coalition deviations, and resource augmentation are unchanged. Thus this is continuization of the population, not of the outcome space.
The natural continuous algorithm is the mass version of Truncated Greedy Capture. Increase a radius \(\delta\); for each unselected candidate, accumulate currently uncovered mass in its \(\delta\)-ball. When a candidate reaches mass \(1/k\), select it and remove exactly that quota of mass. If a type lies on the boundary, split its mass fractionally. The only event radii are the \(\tau m\) values \(d(\theta,c)\), so the process can be implemented in polynomial time in \(\tau\), \(m\), and the input encoding length.
I would therefore expect this mirror to be Class A for the stated approximation-feasibility problem. The proof of Theorem 5.1 uses quota-sized disjoint neighborhoods, triangle inequalities, and sums of distances; all of these survive when voter counts become measures. The supporting Lemma 5.2 is especially suggestive: its finite statement says that every coalition of size at least \(\lceil n/k\rceil\) contains a voter whose assigned representative is within a factor \(1+\sqrt2\) of every excluded candidate. In the mirror, the same statement becomes a positive-mass-type stability property for every coalition of mass at least \(1/k\).
The regime is plausible in public-facility selection: millions of residents may fall into a few hundred or thousand location or commuting types, each with the same distances to a finite set of possible facilities. It is also plausible for large elections with repeated metric preference profiles. Here \(n\gg\tau\), and \(\mu_\theta\) records the fraction of the population in each repeated type. The authors should recognize this as their problem: the paper itself treats voters, documents, and facility locations uniformly, and its known-distance setting is already naturally compatible with repeated population locations.
The main weakness is that the paper’s finite algorithm already runs in essentially linear time in the explicit voter count, and the theorem is not a discrete hardness result. Consequently, the continuous version may look like a clean weighted implementation and a natural theorem extension rather than a discovery that discrete computational hardness disappears. The exact optimization problem—computing the minimum possible worst-coalition factor \(\gamma\)—is also not solved by Theorem 5.1; the theorem supplies a constructive upper bound.
That leaves worthwhile follow-up questions: compute or approximate the optimal \(\gamma\) as a function of \((m,\tau,k)\); determine the sharp \(\alpha=1\) bound; study the ordinal-only mirror over masses of ranking types; and establish a formal finite-to-continuous transfer theorem quantifying the effect of replacing \(\lceil n/k\rceil/n\) by \(1/k\).
The strongest negative case is not that the proposed population model is incoherent. It is coherent, and the public-facility interpretation gives a credible high-multiplicity regime. The problem is that the paper supplies no qualifying computational anchor for ChoCo.
Theorem 5.1 is an approximation guarantee for a particular greedy committee, not a complexity result about an optimization or decision problem. The paper’s only computational analysis is that Truncated Greedy Capture can be implemented in essentially \(\widetilde O(nm)\) time by sorting the \(nm\) voter–candidate distances. Its proof explicitly says that it uses only disjointness of neighborhoods, quota-sized neighborhoods, and Lemma 5.2. Replacing voter sets by masses and the quota \(p=\lceil n/k\rceil\) by \(1/k\) therefore gives a line-by-line measure version of the same proof, not a new computational theorem. [The paper states both the theorem and this running-time analysis.](https://arxiv.org/html/2312.10369v2)
Indeed, with rational masses one can choose a common denominator \(N\), replace type \(\theta\) by \(N\mu_\theta\) identical voters, and recover the finite algorithm exactly up to the normalized quota \(\lceil N/k\rceil/N\). In the limit, the weighted implementation merely replaces repeated set operations by mass counters. That is a legitimate compressed implementation, but it does not expose the kind of population-multiplicity phenomenon ChoCo is meant to study: there is no discrete computational obstacle being removed, no exponential-variable optimization problem, and no separation or pricing question.
The obvious stronger proposal is to define the optimal robustness value
\[
\Gamma(\mu)=
\min_{|R|=k}\;
\max_{t,\lambda}
\frac{L_R(\lambda,t)}{O(\lambda,t)}.
\]
That is a sensible new problem, but it is not a continuization of Theorem 5.1. The theorem only certifies that one greedy committee has a particular upper bound; it neither defines nor analyzes the optimum \(\Gamma(\mu)\). Any interesting complexity result about \(\Gamma\) would arise from inventing a new robust integral committee-selection problem, not from making the paper’s population continuous.
The same defeats the proposed alternatives. An ordinal mirror over ranking-type masses is a weighted version of the Expanding Approvals Rule: approval counters become masses, and the proof again transfers directly. A facility-location mirror with repeated resident locations is socially plausible, but it has exactly the same character. The paper’s known-metric algorithm already processes voters independently, so aggregation by location type is an immediate data compression. Sharp constants, optimal committees, or exact finite-to-continuous convergence could be worthwhile questions, but they would be new research programmes rather than mirrors of the paper’s proved result.
The no-augmentation boundary is also less attractive than the proponent suggests. The paper’s \(\alpha=1\) guarantee is \(O(n/k)\), while the constant guarantee is only for \(\alpha>1\). Passing to the normalized quota \(1/k\) removes the explicit \(n\), but does not automatically supply a meaningful continuum analogue of the \(\alpha=1\) theorem; that would require a separate argument. Thus the cleanest proposed extension is merely an immediate weighted restatement, while the genuinely nontrivial extensions are no longer anchored in a theorem of the paper.
So the universal claim is not literally defensible: a mathematically valid high-multiplicity mirror exists, and one could build a worthwhile new committee-optimization project around it. But the best case against is that this paper contributes representation definitions and approximation guarantees, not computational social-choice results whose population axis can reveal a new complexity landscape. Under ChoCo’s standard, its continuous version is at most a short weighted corollary, not a worthwhile continuization programme.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.