| paper | On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries |
| authors | Dimitris Fotakis, Laurent Gourvès, Panagiotis Patsilinakos |
| venue | AAAI 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given candidates C, committee size k, rational masses μ over finitely many repeated 1-Euclidean voter cohorts, their ordinal rankings, and hidden line coordinates consistent with those rankings, may an adaptive deterministic rule using O(k log N) candidate-distance queries output an integral k-subset S with normalized nearest-candidate cost at most 5 times the optimum for every consistent hidden world?
A finite candidate axis with τ repeated cohorts, each having a shared private cardinal location and reported ranking, rational mass μ_t, hidden candidate and cohort coordinates, adaptive candidate-distance queries, an integral k-committee decision, and minimax normalized nearest-candidate social cost.
The mirror must clarify whether complete cardinal cohort types are private latent attributes rather than disclosed input, since disclosure would remove the paper's query uncertainty.
fatal: False
The mirror covers the algorithmic results in Theorems 3–5 and, under a relaxed latent-cohort convention, the query lower bound in Theorem 1; it does not cleanly cover Theorem 2's 5n social-cost bound or the paper's open conjectures.
The strongest honest positive case is a faithful high-multiplicity version of the paper’s few-query committee problem. It is not a new outcome-space relaxation: candidates remain discrete, the committee remains an integral \(k\)-subset, and only the voter population is replaced by rational mass.
A plausible regime is a large electorate divided into repeated geographic or organizational cohorts. Voters in one cohort occupy the same position on a one-dimensional policy or service axis, therefore have the same complete cardinal preferences and the same ordinal ranking over the finite candidate slate. There may be \(N\) voters but only \(\tau\) such cohorts, with \(N\gg \tau\), while \(m\) and \(k\) remain moderate. This is credible for mass consultations, regional representative selection, or choosing \(k\) service locations for many repeated neighbourhood types.
Formally, let \(C=\{c_1,\ldots,c_m\}\), let \(k<m\), and let \(T\) be a finite set of complete metric voter types. Type \(t\) has mass \(\mu_t\in\mathbb Q_{\ge 0}\), \(\sum_t\mu_t=1\), and an ordinal ranking \(\succ_t\). In a hidden admissible world \(W\), candidates have unknown coordinates \(x(c)\) on the line and every unit of type-\(t\) mass has the same latent coordinate \(y_t\), so its cost for a committee \(S\) is
\[ d_W(t,S)=\min_{c\in S}|y_t-x(c)|. \]
The rule sees the ranking profile and masses, but not the coordinates, exactly as in the paper. It may adaptively query candidate-to-candidate distances \(|x(c)-x(c')|\), then must output an integral committee \(S\) of size \(k\). Its normalized social cost is
\[ SC_\mu^W(S)=\sum_{t\in T}\mu_t d_W(t,S), \]
and its distortion is the worst-case ratio against the optimal \(k\)-committee over all hidden worlds consistent with the observed rankings and query answers.
This respects the programme’s completeness requirement for types: two voters are called the same type only when their latent metric preferences as well as their rankings agree. The latent coordinates remain hidden, so the mirror does not trivialize the paper’s information model.
My lead anchor is Theorem 5, proved in this paper. It states that there is a polynomial-time deterministic rule using \(O(k\log n)\) distance queries and achieving distortion at most \(5\) for \(k\)-Committee Election on the line.
The corresponding continuous problem is:
HM-1E-FQCE. Given \(C,k\), a rational mass profile \(\mu\) over complete 1-Euclidean voter types, and only ordinal information plus candidate-distance queries, construct a deterministic adaptive rule that uses \(O(k\log N)\) queries and always returns a committee \(S\) satisfying
\[ SC_\mu^W(S)\le 5\min_{|S'|=k}SC_\mu^W(S') \]
for every consistent hidden world \(W\). Here \(N\) is any common denominator with \(\mu_t=a_t/N\).
What counts as a solution is the query policy together with the returned committee on each query transcript. The expected classification is Class A. If \(\mu_t=a_t/N\), replace type \(t\) by \(a_t\) identical clones. The normalized objective is exactly the original social-cost objective divided by \(N\), so the distortion is unchanged. The hierarchical partitioning and dynamic programming in Theorems 3–5 use cluster counts and interval weights; they can therefore be run on the \(a_t\)’s without materializing all \(N\) voters. The query bound is polynomial in the compressed input length because \(\log N\) is polynomial in the binary encoding length of the masses.
The paper’s Theorem 4, also proved here, supplies the structural heart of this mirror: the query procedure constructs an \(O(k\log n)\)-candidate set that is \((O(k\log n),2)\)-good. In the mass version, voter counts become cohort masses and the interval weight becomes mass times interval length. Theorem 3 then gives the factor-\(5\) committee guarantee. A natural sharper follow-up is whether the dependence can be written as \(O(k\log(k/\mu_{\min}))\), or even in terms of \(\tau\) rather than the smallest rational mass.
The second worthwhile anchor is Theorem 1, proved in this paper. It says that for every \(k\ge3\), any deterministic rule using at most \(k-3\) distance queries and selecting \(k\) of at least \(2(k-1)\) candidates has unbounded distortion, for both social and egalitarian cost.
Its continuous counterpart is:
HM-Query-Distortion Threshold. For fixed \(k\ge3\), \(m=2(k-1)\), and the uniform mass profile \(\mu_t=1/m\) over the \(m\) lower-bound voter types, determine whether a deterministic rule using at most \(k-3\) adaptive candidate-distance queries can guarantee any finite distortion. Equivalently, characterize
\[ \inf_R\sup_W \frac{SC_\mu^W(R(W))}{\min_{|S|=k}SC_\mu^W(S)}. \]
The answer predicted by Theorem 1 is no: the supremum is infinite. The construction survives unchanged after replacing each voter by an arbitrary number of identical clones. Thus this is a direct high-multiplicity mirror, and the inherited obstruction is not population multiplicity but uncertainty about the candidate geometry. In the programme’s trichotomy, this is not continuum-specific hardness; it is a lower-bound phenomenon that transfers to the continuous regime.
These two anchors cover the paper’s main computational content: the lower query barrier in Theorem 1, and the constant-distortion algorithmic side in Theorems 3–5. I would not use Theorem 2 as an anchor: its \(5n\) social-cost bound does not become a constant merely by normalizing voter mass, so it is less cleanly mirrorable.
The weakest point is that the paper does not itself prove the weighted compressed version. Theorem 5 is stated for an explicitly listed electorate and its proof uses \(n\) in the partition-depth bound. One must carefully show that all operations aggregate over type masses and that hidden metric signatures are shared by clones. If that reproof failed, the mirror would be an extension rather than a direct theorem transfer. A second, smaller caveat is that this is a faithful high-multiplicity compression of an information-theoretic voting problem, not a new LP-style complexity landscape. Nevertheless, the paper’s candidates, committee objective, hidden geometry, ordinal access, query actions, and distortion criterion all remain intact, so the authors should recognize these as their problem in continuous population form.
The strongest negative case is a modelling one: the proposed mirror does not preserve the paper’s information model while satisfying ChoCo’s requirement that a type be complete.
In the paper, a ranking is not a complete voter type. Given fixed candidate locations, many different voter positions can induce the same ranking, while producing different distances to every committee. Those distances determine the social-cost objective. Thus a mass \(\mu_r\) over rankings does not determine the continuous objective. Replacing all voters with ranking \(r\) by clones at one hidden coordinate \(y_r\) is an additional co-location promise, not a consequence of high multiplicity.
The alternative fares no better. If the type includes the voter’s complete cardinal cost vector, then publicly supplying the distribution over types supplies the information needed to evaluate every committee, largely eliminating the paper’s few-query uncertainty. If the cardinal type remains hidden, then the distribution over complete types is not actually the society given to the algorithm. The proposed HM-1E-FQCE therefore oscillates between an incomplete type model and a new latent-cohort promise.
This directly weakens the claimed anchor on Theorems 3–5. Their weighted proofs may well extend to masses, but that would establish a different promise problem: masses of cohorts whose hidden positions are stipulated to coincide. It would not be a high-multiplicity version of the paper’s ordinal-input model, where voters sharing a ranking may still have distinct cardinal locations. The interval-weight argument in Theorem 4 is especially revealing: replacing counts by masses is mathematically easy, but it does not resolve the missing latent-location distribution. The result would be a weighted query game over hidden geometry, not a continuous society of complete voter types.
Theorem 1 has the same problem more sharply. Its variants move a candidate and the voter colocated with that candidate. Consequently, the voter’s cardinal preferences change from one indistinguishable world to another. Cloning the voters separately inside each variant does not give one fixed mass profile over complete types across the lower-bound family. If types are merely rankings, the lower bound lifts—but those are incomplete types. If types include cardinal preferences, the variants no longer share the same continuous instance. Hence the advertised “direct” HM lower bound is not established under ChoCo’s type discipline.
A latent-cohort formulation is the strongest rescue: each cohort has a common hidden coordinate, the algorithm observes only its mass and ranking, and worlds may vary that coordinate. It is coherent and perhaps socially plausible. But it is a new partially observed promise model whose cohort identity is not determined by the supplied preferences. Calling it a continuous mirror requires accepting hidden, unreported type attributes—precisely what the programme’s completeness condition was intended to exclude.
That said, the negative case is ultimately weak. If ChoCo explicitly permits such latent co-located cohorts, then Theorems 4–5 plausibly yield a legitimate weighted mirror, and the paper’s repeated-neighbourhood interpretation is credible. Under that reading, I cannot honestly maintain that no worthwhile mirror exists. The defensible negative verdict is narrower: the proponent has not shown that its mirror is a faithful high-multiplicity continuization of this paper’s actual information model, and Theorem 1 does not transfer under complete types.
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.