Answer: polynomial-time solvable (the bounded-distortion existence answer is always no)
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is a polynomial-time deterministic rule for k-Committee Election that uses O(k log n) distance queries and achieves a distortion of at most 5.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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?
There are \(m\) labeled candidates and at most \(\tau\) strict complete \(1\)-Euclidean ranking types, with rational masses \(\mu_\rho\ge0\) summing to \(1\); all mass of type \(\rho\) is colocated with \(\operatorname{top}(\rho)\).
A realization \(z\) assigns unknown real coordinates \(x_z(c)\) to candidates, realizes every type's ranking by increasing distance, and answers any adaptive candidate-distance queries consistently. A deterministic rule receives the types and \(\mu\), makes at most \(q\) such queries, and returns \(S\) with \(|S|=k\).
Its social cost is \(\mathrm{SC}_{\mu,z}(S)=\sum_\rho\mu_\rho\min_{c\in S}|x_z(\operatorname{top}(\rho))-x_z(c)|\); distortion is the worst-case ratio to the minimum social cost of a \(k\)-candidate committee over compatible realizations.
For \(q\le k-3\), is the continuous rule-existence problem solvable in polynomial time or NP-hard, even for \(m=2(k-1)\), \(\tau=m\), and uniform \(\mu\)?
For finite voter profiles, every deterministic rule using at most \(k-3\) candidate-distance queries has unbounded social-cost distortion for \(k\ge3\) and \(m\ge2(k-1)\), even with voters colocated with their top candidates.
With \(O(k)\) candidate-distance queries, a deterministic finite-voter rule achieves social-cost distortion at most \(5n\).
The definitions do not explicitly state a decision language. I use the natural global interpretation suggested by the distortion results:
Given \(k\) and \(q\), does there exist a deterministic rule using at most \(q\) candidate-distance queries whose distortion is finite on every promised continuous profile?
Under this interpretation, the problem is polynomial-time solvable for \(k\geq 3\) and \(q\leq k-3\): the answer is always no. In fact, one fixed uniform profile already defeats every such rule.
If “rule existence” merely means existence of any rule, the answer is instead trivially yes: return a fixed \(k\)-set without making queries. A profile-specific synthesis problem with a distortion threshold would be a different problem and has not been defined here.
For every \(k\geq 3\), let \(m=2(k-1)\). There exists a fixed collection of exactly \(\tau=m\) strict complete \(1\)-Euclidean ranking types, each of mass \(1/m\), such that every deterministic rule using at most \(q\leq k-3\) candidate-distance queries has infinite worst-case social-cost distortion on that single profile.
The construction is a continuous, uniform-mass version of the candidate-pair adversary underlying the finite lower bound of [Fotakis, Gourvès, and Patsilinakos](https://arxiv.org/abs/2408.11755).
Put \(r=k-1\), so \(m=2r\), and partition the candidates into pairs \(P_i=\{a_i,b_i\}\) for \(i\in\{1,\ldots,r\}\).
Fix an integer \(D\geq r+1\), and define \(M=100D\), \(H=10M2^r\), and \(G_i=H+M2^i\) for \(i\in\{1,\ldots,r-1\}\).
The base coordinates are defined recursively by \(x^0(a_1)=0\), \(x^0(b_i)=x^0(a_i)+1\), and \(x^0(a_{i+1})=x^0(b_i)+G_i\). Thus, each pair has internal distance \(1\), whereas successive pairs are extremely far apart.
There are \(2r\) variants. Variant \(z_{2i-1}\) moves \(a_i\) distance \(D\) to the left, while variant \(z_{2i}\) moves \(b_i\) distance \(D\) to the right. All other candidates retain their base coordinates. Hence the internal distance of pair \(P_i\) is \(D+1\) in its two variants, and every other pair still has internal distance \(1\).
For every candidate \(c\), introduce one type \(\rho_c\), located at \(c\), whose ranking is the distance ranking induced by the base realization. Assign every type mass \(1/m\).
Consider a voter located at a candidate in pair \(P_p\).
First, her own candidate remains uniquely first. Her pair-mate remains second: its distance is either \(1\) or \(D+1\), whereas every candidate in another pair is at distance at least \(\min_i G_i-D>D+1\).
Candidates belonging to the same remote pair retain their relative order. Moving \(a_i\) to the left or \(b_i\) to the right moves that candidate outward from its mate. Thus an observer to the left continues to rank \(a_i\) before \(b_i\), and an observer to the right continues to rank \(b_i\) before \(a_i\).
It remains to compare candidates in different pairs. A base distance crossing \(h\) inter-pair gaps has the form \(hH+M\sum_{\ell\in I}2^\ell+\eta\), where \(I\) is an interval of \(h\) consecutive gap indices and \(|\eta|\leq r+1\) accounts for unit intra-pair gaps and endpoint choices.
If two distances cross different numbers of inter-pair gaps, their difference is at least \(H-M2^r-r>2D\).
If they cross the same number \(h\) of gaps, the targets must lie on opposite sides of the voter. Their index intervals have different starting points. Since \(\sum_{\ell=s}^{s+h-1}2^\ell=2^s(2^h-1)\), the corresponding sums are distinct, and the distance difference is at least \(M-2>2D\).
Moving the voter or one compared candidate changes a difference of distances by at most \(2D\). Consequently, none of these comparisons can reverse. All rankings are strict and identical in the base realization and every variant. Their order is also independent of the chosen \(D\).
Thus the same fixed \(m\) ranking types are compatible with every \(z_j\).
Fix a variant whose exceptional pair is \(P_i\). Consider the committee containing both members of \(P_i\) and one member of every other pair. Exactly one voter in each of the remaining \(r-1=k-2\) pairs incurs cost \(1\). Therefore its normalized social cost is \((k-2)/m\).
This committee is optimal. Indeed:
It follows that the optimum is exactly \((k-2)/m>0\).
Run an arbitrary deterministic rule and answer every query with its base-realization distance. Let \(U\) be the set of candidates occurring as endpoints of queried pairs. Since there are at most \(q\) queries, \(|U|\leq 2q\).
For every \(j\notin U\), variant \(z_j\) gives exactly the same answers to all queries: only distances incident to the moved candidate \(c_j\) differ from their base values. Therefore the completed adaptive transcript is compatible with every such \(z_j\).
Because \(q\leq k-3=r-2\), the number of uneliminated variants is at least \(2r-2q\geq 4\). Since each candidate pair accounts for only two variants, these variants include at least two possible exceptional pairs.
Let \(S\) be the rule’s returned committee.
If \(S\) leaves a pair empty, its cost is already at least \((\min_iG_i-D)/m\) in every compatible variant.
Otherwise, \(S\) meets every pair and doubles exactly one pair. Among the at least two compatible exceptional pairs, choose one that is not doubled by \(S\). In the corresponding variant, the unselected member of that exceptional pair incurs cost at least \(D+1\). Hence \(\mathrm{SC}_{\mu,z}(S)\geq D/m\).
By Lemma 2, the distortion on this compatible realization is at least \(D/(k-2)\). Since \(D\) is arbitrarily large while the ranking types and masses remain fixed, the rule’s worst-case distortion is infinite.
Replacing each mass-\(1/m\) type by one finite voter gives \(\mathrm{SC}_{\mu,z}(S)=\mathrm{SC}_{V,z}(S)/m\). The optimal cost is scaled by the same factor, so every distortion ratio and every adaptive candidate-distance transcript is preserved exactly. Thus no rounding or limiting argument is involved.
Consequently, for \(k\geq3\), \(q\leq k-3\), \(m=2(k-1)\), \(\tau=m\), and uniform masses, no bounded-distortion deterministic rule exists.
Therefore the global bounded-distortion rule-existence problem on this promised parameter range is decidable by constant-time rejection, and hence is polynomial-time solvable. The finite distortion lower bound does not yield an NP-hardness result; it yields a uniform impossibility.
⟨structured verdict parsed — rendered above⟩
The prover establishes a substantial conditional impossibility theorem: under its explicitly chosen “global bounded-distortion” interpretation, the construction appears sound and shows that no deterministic rule with \(q\leq k-3\) has finite distortion.
However, this does not unconditionally resolve the stated complexity question. The original task never defines a decision language, its encoded inputs, or whether rule existence is global or profile-specific. The prover selects one interpretation and then classifies that interpretation. Under a profile-specific interpretation, constructing one negative profile would not justify constant-time rejection of every instance.
Accordingly, the output contains genuine and largely correct mathematical progress but does not settle the target as written.
The prover defines the question as:
“Given \(k\) and \(q\), does there exist a deterministic rule using at most \(q\) candidate-distance queries whose distortion is finite on every promised continuous profile?”
This is not stated in the task. In particular, the task does not specify:
These distinctions materially affect the complexity problem. Thus the “constant-time rejection” conclusion is valid only for the prover’s chosen global interpretation.
Minimum clarification required: state the formal decision language and confirm that the quantified object is one global rule required to have finite distortion on every promised profile.
The candidate count is correct. With \(r=k-1\), the \(r\) pairs contain \(2r=2(k-1)=m\) candidates.
There is one type per candidate, and types associated with different candidates are distinct because they have different top-ranked candidates. The masses \(1/m\) are rational, uniform, and sum to \(1\).
The construction respects colocation: in every realization, the voter of type \(\rho_c\) is located at candidate \(c\), including when \(c\) is the moved candidate.
The pair-mate comparison is valid. Its distance is at most \(D+1\), while every candidate outside the pair is separated by an inter-pair gap much larger than \(D+1\).
The argument that the order of the two candidates in a remote pair is preserved is also valid: the moved endpoint is displaced outward, and the large gaps prevent it from crossing the observer.
For comparisons between different remote pairs, the scale separation is sufficient, but two displayed numerical bounds do not follow exactly from the preceding estimate:
These inaccuracies do not appear fatal because the chosen constants are much larger than necessary. For example, \(M-2(r+1)\geq 98D>2D\) when \(D\geq r+1\). Nevertheless, the written lower bounds require correction or an explicit cancellation calculation.
The claim that the ranking types are independent of \(D\) is important because unbounded distortion is obtained by allowing \(D\) to grow while keeping the ordinal profile fixed. The proof establishes non-reversal between the base realization and its variants for each fixed \(D\), but independence across different values of \(D\) is only asserted. The preceding affine scale-separated expressions strongly support the assertion, but the sign of each comparison should explicitly be shown independent of \(D\), rather than merely bounded away from zero separately for each \(D\).
The proposed committee has the claimed cost. It selects both candidates in the exceptional pair and one candidate in every other pair. Thus exactly one voter in each of \(r-1=k-2\) ordinary pairs pays distance \(1\), giving normalized cost
\[ \frac{k-2}{m}. \]
If a committee leaves a pair empty, at least one voter in that pair must cross an inter-pair gap, with distance at least \(\min_i G_i-D\). This is greater than \(k-2\), so its normalized cost exceeds the proposed cost.
If the committee meets every pair, its \(r+1\) members over \(r\) pairs force exactly one doubled pair. If the exceptional pair is not doubled, its unselected candidate pays \(D+1>k-2\), again exceeding the proposed total unnormalized cost.
Therefore the optimum calculation is correct, including the edge case \(k=3\).
With at most \(q\) queries, at most \(2q\) candidates occur as query endpoints. If candidate \(c_j\) is not such an endpoint, moving \(c_j\) changes no queried distance.
For an adaptive deterministic rule, compatibility of the entire transcript follows inductively: identical previous answers cause the same next query, and that query again avoids \(c_j\). This induction is implicit but routine.
The count is correct:
\[ 2r-2q\geq 2r-2(r-2)=4. \]
Since each exceptional pair produces only two variants, at least two distinct exceptional pairs remain compatible.
If the returned committee leaves a pair empty, the large-gap lower bound applies. Otherwise it doubles exactly one pair, so one of the at least two compatible exceptional pairs is not doubled. In that variant, an unselected candidate in the exceptional pair pays \(D+1\). Hence
\[ \mathrm{SC}_{\mu,z}(S)\geq \frac{D}{m}, \]
and division by the optimum gives distortion at least \(D/(k-2)\).
Provided the ranking profile is indeed independent of \(D\), taking arbitrarily large integer \(D\) correctly proves infinite worst-case distortion.
Replacing each uniform mass-\(1/m\) type by one finite voter scales both the rule’s cost and optimal cost by \(m\). The distortion ratio is unchanged. Candidate-distance query answers depend only on candidate coordinates and are likewise unchanged. This check is correct.
The mathematical construction proves a global impossibility statement under the prover’s interpretation. It does not, by itself, establish that an unspecified “continuous rule-existence problem” is polynomial-time solvable.
In particular, if profiles are instances, one negative profile is not enough to conclude that every instance should be rejected. The missing formal definition is therefore a major blocker rather than a purely expositional omission.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.