| paper | Distortion of Multi-winner Elections on the Line Metric: The Polar Comparison Rule |
| authors | Negar Babashah, Hasti Karimi, Masoud Seddighin, Golnoosh Shahkarami |
| venue | SAGT 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time computable in \(m,\tau,L\), with \(D_\mu(S_\mu)\le 1+\sqrt2\) for every promised input. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) candidates, \(k=2\), and a rational distribution \(\mu\) over complete rankings with a common line realization, compute the mass version \(S_\mu\) of the Polar Comparison Rule using pairwise masses \(\mu(a\succ b)\). For every compatible candidate placement \(y\) and unit-mass voter-location measure \(\nu\) whose ranking marginal is \(\mu\), require \(\sup_{(y,\nu)\models\mu}\frac{\int \sum_{a\in S_\mu}|z-y_a|\,d\nu(t,z)}{\min_{S\in\binom{C}{2}}\int \sum_{a\in S}|z-y_a|\,d\nu(t,z)}\le 1+\sqrt{2}\).
Types are complete ordinal rankings \(t\in T\) with masses \(\mu_t\); hidden realizations are line locations \(y\) and a unit measure \(\nu\) over \((t,z)\); the decision is an integral committee \(S\in\binom{C}{2}\), optimized for worst-case utilitarian additive distortion.
The continuous input \(\mu\) does not itself determine the hidden location measure \(\nu\), so exact evaluation of \(D_\mu(S)\) and the resulting computational payoff may be less direct than the mass comparisons used by the rule.
fatal: False
It directly covers the utilitarian Polar rules and their composition in Theorems 1 and 3, and can restate Theorem 2's two-cohort lower bound; it leaves the egalitarian analysis in Theorem 8, \(k\)-Extremes, and purely geometric lemmas outside the anchored mirror.
There is a credible continuous mirror, although with an important qualification: the paper contains no named NP-hardness, \(P\), FPT, or other complexity-class theorem. Its strongest anchors are named algorithmic distortion theorems. I would therefore present this as a continuous high-multiplicity version of the paper’s ordinal committee-selection problem, not as an already-proved complexity classification.
The mirror keeps the candidates and committee discrete, and continuizes only the electorate. Let \(C\) be the \(m\) candidates and let \(T\subseteq\mathcal L(C)\) be the line-realizable voter rankings. A continuous society is a rational distribution \(\mu\) over \(T\); \(\mu_t\) is the fraction of the electorate with ranking \(t\). The action is still an integral committee \(S\in {C\choose k}\).
The hidden metric is represented by a line realization \((y,\nu)\), where \(y_a\) is the location of candidate \(a\), and \(\nu\) is a unit mass measure over voter locations and rankings whose ranking marginal is \(\mu\). Almost every voter-location/ranking pair must agree with the distances to the candidate locations. For such a realization,
\[ \mathrm{SC}_{\nu,y}(S) = \int \sum_{a\in S}|z-y_a|\,d\nu(t,z), \]
and the robust distortion of \(S\) is
\[ D_\mu(S) = \sup_{(y,\nu)\models\mu} \frac{\mathrm{SC}_{\nu,y}(S)} {\min_{S'\in {C\choose k}}\mathrm{SC}_{\nu,y}(S')}. \]
The continuous problem is therefore: given \(\mu\), \(m\), and \(k\), output an integral committee minimizing \(D_\mu(S)\), or, for the constructive versions below, output a committee satisfying the stated distortion guarantee.
This is a sensible high-multiplicity regime for the paper’s problem. Think of a city with millions of residents but only a few dozen recurring complete rankings, produced by large ideological or neighbourhood cohorts. The relevant comparison is \(N\gg\tau=|{\rm supp}(\mu)|\), not “all voters are literally identical.” The latent location is hidden exactly as cardinal costs are hidden in the paper; the public type is the complete ordinal information available to the voting rule. A finite election with \(n_t\) voters of type \(t\) becomes \(\mu_t=n_t/n\), and every finite metric realization becomes a finitely supported measure \(\nu\). Conversely, rational \(\mu\) can be lifted to a finite profile by clearing denominators. Normalizing social cost by \(n\) leaves distortion unchanged.
My lead anchor is Theorem 1, proved in this paper. It states that the \(2\)-Winner Polar Comparison Rule, under the line metric and utilitarian additive social cost, satisfies
\[ \operatorname{dist}(f(\succ),\instance;d)\le 1+\sqrt2 \]
for every election and every metric consistent with the ordinal profile; consequently \(\operatorname{dist}(f)\le1+\sqrt2\). The rule selects the first two candidates in the paper’s majority order, then compares the nearest candidate \(c\) on the opposite side of the first candidate using the thresholds \(1/(1+\sqrt2)\).
The corresponding continuous question is:
\[ \textbf{Continuous Polar-2-Committee:} \]
Given a line-realizable distribution \(\mu\) over complete rankings, compute the mass version of the Polar Comparison Rule and return a pair \(S_\mu\). The required certificate is
\[ D_\mu(S_\mu)\le1+\sqrt2. \]
All comparisons in the rule become comparisons of masses such as
\[ \mu(c\succ b) = \sum_{t:c\succ_t b}\mu_t \]
with \(1/(1+\sqrt2)\). The committee remains integral; only the population is fractional. This is recognisably the authors’ problem: same hidden line geometry, same ordinal input, same additive committee cost, same objective, and the same Polar rule. It is not a tractable surrogate obtained by replacing committees with lotteries.
I would expect this guarantee problem to be Class A in the explicit-type representation. Pairwise masses, Pareto domination, the majority order, and the threshold tests are computable in polynomial time in \(m\), \(\tau\), and the encoding length of \(\mu\). The theorem itself does not state a \(P\)-bound, so that complexity claim is an extension to be proved, not something falsely attributed to the paper.
The second anchor is Theorem 2, also proved here. It states that every \(2\)-winner voting rule on the line under additive social cost has distortion at least
\[ 1+\sqrt2. \]
Its continuous version is the natural minimax design problem
\[ \inf_F\sup_{\mu}D_\mu(F(\mu)), \]
where \(F\) ranges over deterministic ordinal rules mapping a continuous type distribution to a pair. The continuous lower-bound certificate uses two voter types: mass \(1/(1+\sqrt2)\) with ranking \(a'\succ b'\succ a\succ b\), and mass \(\sqrt2/(1+\sqrt2)\) with ranking \(a\succ b\succ a'\succ b'\). The candidates \(a,b\) occupy one side of the line and \(a',b'\) the other; two different consistent realizations place the two masses at different locations. Whatever pair \(F(\mu)\) returns, one of those realizations gives distortion at least \(1+\sqrt2\).
Thus Theorems 1 and 2 together suggest the exact continuous minimax answer
\[ \inf_F\sup_{\mu}D_\mu(F(\mu))=1+\sqrt2. \]
This is not computational hardness; it is an information-theoretic boundary. But it is a strong mirror because the continuous mass formulation removes the paper’s integer-rounding nuisance and makes the two ambiguous realizations exact. The coincident candidate locations in the lower-bound picture can be replaced by arbitrarily small distinct perturbations, as the paper itself notes.
The third anchor is Theorem 3, proved here. For every \(k>2\), it asserts the existence of a \(k\)-winner voting rule with utilitarian line-metric distortion at most
\[ \begin{cases} \dfrac73, & k\equiv0\pmod 3,\\[4pt] \dfrac73+\dfrac{4(\sqrt2-\frac43)}{k}, & k\equiv1\pmod 3,\\[8pt] \dfrac73+\dfrac{2(\sqrt2-\frac43)}{k}, & k\equiv2\pmod 3. \end{cases} \]
The continuous question is:
\[ \textbf{Continuous Polar-Block Committee:} \]
Given \(\mu\) and \(k>2\), return a \(k\)-committee by applying the mass version of the \(3\)-winner Polar rule to \(3\)-blocks and the \(2\)-winner Polar rule to the remaining candidates. The required guarantee is the displayed bound. For \(k=3q\), use \(q\) three-winner blocks; for \(k=3q+2\), use \(q\) three-winner blocks and one two-winner block; for \(k=3q+1\), use \(q-1\) three-winner blocks and two two-winner blocks.
I would again expect this particular guarantee problem to be Class A for explicit \(\mu\). The rule is built from polynomially many majority-mass comparisons, candidate-order computations, and recursive applications of the two- and three-winner rules. Exact minimization of \(D_\mu(S)\), however, is a separate and more interesting question: the paper proves a universal guarantee, not an algorithm for the pointwise optimal robust committee.
The scope of this mirror is the paper’s utilitarian additive results: Theorems 1–3, the Polar rules, and their block composition. I would not claim that the egalitarian result is automatically covered; its maximum-over-voters objective behaves differently and depends mainly on support and extreme locations rather than population proportions.
The weakest point is that the paper is not really a computational-complexity paper in the programme’s sense. Its theorems establish distortion guarantees, not \(P\)-versus-NP boundaries, LP formulations, or separation problems. Moreover, because the proofs are written with voter counts and are largely linear in those counts, much of the transfer to \(\mu\) may turn out to be a clean extension rather than a new complexity phenomenon. If one insists that a continuous type must expose the voter’s exact cardinal location, the mirror also fails: that would reveal information the original voting rule explicitly does not receive.
Under the paper’s actual ordinal-information model, though, the mirror is genuine and plausible. It replaces indexed voters by a distribution over complete public types, keeps the hidden metric uncertainty, preserves the integral committee decision, and turns the paper’s finite theorems into precise high-multiplicity robust-selection questions. The main new tasks are to formalize the measure-valued realization space, compute \(D_\mu(S)\) exactly, and determine whether the general-\(k\) gap between the Polar upper bounds and the paper’s lower bounds is tractable or continuum-specifically hard.
The negative case is narrower than the universal claim suggests. The population model itself is sensible: voters are anonymous, the objective is additive, and large ideological or geographic cohorts provide a credible high-multiplicity interpretation. I cannot honestly argue that no continuous model can be formulated.
The strongest objection is instead that none of the proposed anchors is a computational result in the programme’s sense. The paper contains no theorem about \(P\), NP-hardness, approximation algorithms, parameterized complexity, or an optimization problem over a continuous society. Theorems 1–3 are distortion guarantees and information-theoretic lower bounds. Replacing voter counts by normalized masses therefore yields a valid translation, but not a complexity mirror.
There is also a modelling fork that the proposed mirror does not fully resolve. A distribution \(\mu\) over rankings does not determine utilitarian social cost: voters with the same ranking may occupy different positions, and the hidden positions determine all distances. The proponent repairs this by introducing a hidden location measure \(\nu\) and taking a supremum over all compatible \((y,\nu)\). That is mathematically legitimate, but the resulting computational object is primarily the original uncertainty over line metrics. If \(\nu\) is supplied, cardinal information has been added and the ordinal model has changed; if \(\nu\) remains hidden, the population distribution alone does not specify a cost instance. The continuous population is consequently not doing the central modelling work.
Theorem 1, the \(2\)-winner Polar Comparison Rule, is the best apparent anchor, but its continuous version is only the finite theorem with every count divided by \(n\). Every test becomes a mass comparison such as \(\mu(c\succ b)\), and the proof inequalities are homogeneous in voter counts. The theorem neither computes the robust distortion \(D_\mu(S)\) nor gives an algorithm for choosing a committee minimizing it. The proposed exact robust-committee problem would be a legitimate new project, but it is not a continuous version of Theorem 1; it replaces a distortion guarantee for a fixed rule by a new optimization problem over hidden embeddings.
Theorem 2 is even less useful as a computational anchor. Its lower bound already uses only two voter cohorts and two compatible metrics. Passing to exact masses removes rounding, but does not create a new computational question. The proposed minimax expression
\[
\inf_F\sup_\mu D_\mu(F(\mu))
\]
is a rule-design or information-theoretic problem, not an algorithmic problem on a given continuous society. It could be interesting independently, but the paper’s lower-bound construction already supplies its essential witness without any population limit.
Theorem 3 has the same defect at larger \(k\). The block construction merely composes the \(2\)- and \(3\)-winner rules, with thresholds and weighted averages replacing integer counts by masses. Keeping committees integral preserves the paper’s model but produces no new continuous optimization problem; allowing fractional committees would create outcome-space continuity, which is outside the programme. The suggested study of the general-\(k\) distortion gap is worthwhile as a voting-rule question, but it is not specifically a computational consequence of continuizing the electorate.
Thus the proponent has shown a clean high-multiplicity restatement, not a ChoCo-style complexity mirror. The honest negative verdict is therefore weak rather than absolute: the continuous formulation is coherent, and Theorem 2 in particular survives formally. But none of the three anchors exposes the computational landscape that the programme is meant to study.
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.