Answer: Polynomial-time solvable.
Theorem 5.1 — class: algorithmic
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} \).
Given a candidate set \(C\) with \(m=|C|\) and an integer \(1\le k<m\), a society is given by its support: the list \(\Theta\) of its \(\tau\) types with positive mass, each mass \(\mu_\theta\) a binary rational, with \(\sum_{\theta\in\Theta}\mu_\theta=1\). Here \(\tau=|\Theta|\) is the support size, not the number of possible types.
The input includes the full binary-rational distance table of a known nonnegative pseudo-metric \(d\) on \(\Theta\cup C\); distinct points may have zero distance. Let \(L\) be the total input bit length.
A coalition is any real submass \(\lambda\in\mathbb R^\Theta\) satisfying \(0\le\lambda_\theta\le\mu_\theta\). The normalized representation quota is \(1/k\).
Find an integral committee \(R\subseteq C\), \(|R|=k\), such that simultaneously for every real \(\alpha>1\), every integer \(1\le t\le k\), and every coalition with \(\sum_\theta\lambda_\theta\ge t\alpha/k\),
\(\displaystyle \sum_{\theta\in\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\in\Theta}\lambda_\theta\sum_{c\in Q'}d(\theta,c),\qquad\gamma(\alpha)=1+(2+\sqrt2)\frac{\alpha}{\alpha-1}.\)
The minimizing subcommittee on the left may differ by type; the comparison subcommittee on the right is shared by the coalition. Equal distances require no prescribed tie-breaking.
Can a committee with this simultaneous approximation guarantee be found in time polynomial in \(m,\tau,k,L\), or is this search problem NP-hard?
For a finite list of \(n\) voters with known distances, Truncated Greedy Capture provides the same simultaneous approximation guarantee in \(\widetilde O(nm)\) time, using coalition thresholds \(t\alpha\lceil n/k\rceil\). [Kalayci, Kempe, and Kher](https://arxiv.org/html/2312.10369v2).
No result settling this precise divisible-mass problem was located in the literature search.
The search problem is polynomial-time solvable. An exact-quota version of Truncated Greedy Capture satisfies the requested guarantee for every real coalition, simultaneously for every \(\alpha>1\) and every permitted \(t\).
The construction adapts [Kalayci, Kempe, and Kher’s Truncated Greedy Capture](https://arxiv.org/html/2312.10369v2#S5). The proof below establishes the divisible-mass extension and its polynomial bit complexity explicitly.
For \(k=1\), the guarantee is vacuous because the required coalition mass exceeds \(1\). The argument below also covers all nonvacuous cases.
Write \(q=1/k\). Maintain residual masses \(u_\theta\), initially \(u_\theta=\mu_\theta\), and a committee \(R\), initially empty.
Repeat the following exactly \(k\) times:
\[ h_c=\min\left\{\delta\in\{d(\theta,c):\theta\in\Theta\}: \sum_{\theta:\,d(\theta,c)\le\delta}u_\theta\ge q\right\}. \]
\[
0\le a_\theta\le u_\theta,\qquad
a_\theta=0\ \text{if }d(\theta,r)>\delta,\qquad
\sum_\theta a_\theta=q.
\]
Update \(u_\theta\leftarrow u_\theta-a_\theta\), and add \(r\) to \(R\).
All choices can use arbitrary fixed orders.
After \(j<k\) iterations, the residual mass is \(1-jq\ge q\). Consequently, every remaining candidate has a finite \(h_c\), and Step 3 is feasible. Thus the algorithm selects exactly \(k\) distinct candidates and consumes all mass.
For the proof, realize the population as the disjoint union
\[
X=\bigsqcup_{\theta\in\Theta}\bigl(\{\theta\}\times[0,\mu_\theta)\bigr),
\]
with Lebesgue measure \(\nu\). Every point of type \(\theta\) has distance \(d(\theta,c)\) to candidate \(c\).
When the algorithm chooses \(r\), realize its consumed amounts as a measurable set \(B_r\) of currently unconsumed population. For example, consume the leftmost available interval of each type. These sets satisfy:
For a measurable set \(A\subseteq X\), define
\[
R[A]=\{r\in R:\nu(A\cap B_r)>0\}.
\]
This construction distinguishes different portions of the same type. In particular, deleting \(B_r\) deletes precisely its captured portion, rather than every point of any type represented in that portion.
Lemma. Let \(\rho=1+\sqrt2\). For every measurable \(A\subseteq X\) with \(\nu(A)\ge q\), and every \(c\in C\setminus R\), there exist \(r\in R[A]\) and a type \(\theta\) having positive mass in \(A\) such that
\[
d(\theta,r)\le\rho\,d(\theta,c).
\]
Proof. Define
\[
D=\max\{d(\theta,c):\nu(A\cap X_\theta)>0\},
\]
where \(X_\theta=\{\theta\}\times[0,\mu_\theta)\). This maximum exists because there are finitely many types and \(A\) has positive mass.
Because the captured sets partition \(X\), some captured set intersects \(A\) in positive measure. Let \(B_r\) be the first such set in the algorithm’s selection order.
Immediately before \(r\) is selected, the previously consumed portion of \(A\) has measure zero. Therefore the unconsumed mass within distance \(D\) of \(c\) is at least \(\nu(A)\ge q\). Candidate \(c\) remains available, since \(c\notin R\). Hence \(h_c\le D\), and the algorithm’s minimizing choice gives
\[
\delta_r\le D.
\]
Choose a type \(\theta_0\) with \(\nu(A\cap B_r\cap X_{\theta_0})>0\). Then
\[
d(\theta_0,r)\le D.
\]
Also choose a type \(\theta_*\) having positive mass in \(A\) and satisfying \(d(\theta_*,c)=D\).
If \(D=0\), then \(d(\theta_0,r)=d(\theta_0,c)=0\), proving the claim.
Suppose \(D>0\), and put \(x=d(\theta_0,c)\). If \(x\ge D/\rho\), then
\[
d(\theta_0,r)\le D\le\rho x.
\]
Otherwise, the triangle inequality gives
\[
d(\theta_*,r)
\le d(\theta_*,c)+d(c,\theta_0)+d(\theta_0,r)
\le 2D+x
<\left(2+\frac1\rho\right)D
=\rho D,
\]
where the final equality follows from \(\rho=1+\sqrt2\).
Thus either \(\theta_0\) or \(\theta_*\) supplies the required type, and \(r\in R[A]\) by construction. No positive-distance assumption was used. \(\square\)
Fix arbitrary \(\alpha>1\), an integer \(1\le t\le k\), and a real coalition \(\lambda\) with total mass
\[
s=\sum_\theta\lambda_\theta\ge\alpha tq.
\]
Represent it by the measurable set
\[
S=\bigsqcup_{\theta\in\Theta}\bigl(\{\theta\}\times[0,\lambda_\theta)\bigr).
\]
Thus \(\nu(S)=s\), and integrating any type-dependent cost over \(S\) gives its \(\lambda\)-weighted sum.
For a candidate \(c\), write
\[
F_S(c)=\sum_\theta\lambda_\theta d(\theta,c).
\]
Let \(C^*=\{c_1,\ldots,c_t\}\) minimize \(\sum_{c\in C^*}F_S(c)\), ordering its members so that those in \(C^*\cap R\) come first. We construct distinct \(r_1,\ldots,r_t\in R\).
For each \(c_i\in R\), set \(r_i=c_i\). For each subsequent index \(i\), define
\[
S_i=S\setminus\bigcup_{j<i}B_{r_j}.
\]
The captured sets each have mass \(q\), so
\[
\nu(S_i)\ge s-(i-1)q>q,
\]
using \(s>tq\) and \(i\le t\).
Choose a measurable subset \(T_i\subseteq S_i\) of mass exactly \(q\), taking the portions closest to \(c_i\). Such a subset exists: process the finitely many type distances in increasing order and, if necessary, take only part of the mass at the final distance.
Let
\[
D_i=\max\{d(\theta,c_i):\nu(T_i\cap X_\theta)>0\}.
\]
The choice of \(T_i\) ensures that, up to measure zero, every point of \(S_i\) whose distance to \(c_i\) is strictly less than \(D_i\) belongs to \(T_i\).
Apply the stability lemma to \(T_i\) and \(c_i\notin R\). It gives a type \(\theta_i\) having positive mass in \(T_i\), and \(r_i\in R[T_i]\), such that
\[
d(\theta_i,r_i)\le\rho\,d(\theta_i,c_i).
\]
Moreover, \(r_i\) differs from every earlier \(r_j\): the set \(T_i\subseteq S_i\) is disjoint from each earlier captured set \(B_{r_j}\), whereas \(r_i\in R[T_i]\) requires a positive-measure intersection with \(B_{r_i}\).
The construction therefore produces a subcommittee \(Q=\{r_1,\ldots,r_t\}\subseteq R\) of size exactly \(t\).
Consider an index \(i\) with \(c_i\notin R\). Since \(d(\theta_i,c_i)\le D_i\), the triangle inequality gives, for every type \(\theta\),
\[
d(\theta,r_i)
\le d(\theta,c_i)+d(c_i,\theta_i)+d(\theta_i,r_i)
\le d(\theta,c_i)+(1+\rho)D_i.
\]
Consequently,
\[
F_S(r_i)\le F_S(c_i)+(1+\rho)sD_i.
\]
We now bound \(D_i\). Define
\[
P_i=\{x\in S:d(x,c_i)<D_i\}.
\]
The portion of \(P_i\) outside \(S_i\) has mass at most \((i-1)q\). Its portion inside \(S_i\) belongs to \(T_i\), up to measure zero, and has mass at most \(q\). Hence
\[
\nu(P_i)\le iq.
\]
Every point of \(S\setminus P_i\) has distance at least \(D_i\) from \(c_i\). Nonnegativity therefore implies
\[
F_S(c_i)\ge(s-\nu(P_i))D_i\ge(s-iq)D_i.
\]
Since \(s>tq\ge iq\), the denominator \(s-iq\) is positive, and thus
\[
F_S(r_i)
\le\left(1+(1+\rho)\frac{s}{s-iq}\right)F_S(c_i).
\]
Finally, \(iq\le tq\le s/\alpha\), so
\[
\frac{s}{s-iq}\le\frac{\alpha}{\alpha-1}.
\]
It follows that
\[
F_S(r_i)
\le\left(1+(2+\sqrt2)\frac{\alpha}{\alpha-1}\right)F_S(c_i)
=\gamma(\alpha)F_S(c_i).
\]
For the indices with \(c_i\in R\), the same inequality holds because \(r_i=c_i\).
Summing over all indices gives
\[
\sum_{\theta}\lambda_\theta\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).
\]
For each type, its minimizing size-\(t\) subcommittee of \(R\) costs no more than this particular \(Q\). Therefore the requested inequality follows.
The algorithm does not depend on \(\alpha\), \(t\), or \(\lambda\), and these were arbitrary. Its guarantee is therefore simultaneous.
For each candidate, sort the types by distance once. In each iteration, scan these sorted lists to compute all \(h_c\), then consume mass in a fixed type order. This requires
\[
O\bigl(m\tau\log(\tau+1)+km\tau\bigr)
\]
arithmetic operations and distance comparisons.
To implement mass updates exactly, write the input masses as \(\mu_\theta=p_\theta/b_\theta\), and use the common denominator
\[
H=k\prod_{\theta\in\Theta}b_\theta.
\]
Each mass and the quota \(q\) is an integer number of units of size \(1/H\). The binary length of \(H\) is \(O(L+\log k)\). Residual masses, quota values, and partial sums all have this polynomial bit length.
Distances are compared as input rationals by cross-multiplication. Selection radii are input distances; the algorithm never needs to compute \(\sqrt2\). Thus every operation has polynomial bit cost, and the total running time is polynomial in \(m,\tau,k,L\).
This proves the polynomial-time classification for the stated search problem.
⟨structured verdict parsed — rendered above⟩
The prover establishes the claimed polynomial-time result. Every substantive step is valid for the stated divisible-mass model, including pseudo-metrics with zero distances. I found no major or minor issues requiring repair.
After \(j\) iterations, exactly \(jq\) mass has been consumed, leaving \(1-jq\). For every \(j<k\), this is at least \(q=1/k\).
For any remaining candidate, the largest distance in its finite type-distance list includes all residual mass. Thus the set defining \(h_c\) is nonempty, and its minimum exists. At the chosen radius, the eligible residual mass is at least \(q\), so Step 3 can consume exactly \(q\).
There is always an unselected candidate because \(j<k<m\). Consequently, the algorithm selects exactly \(k\) distinct candidates, maintains nonnegative residual masses, and consumes total mass \(kq=1\). These conclusions do not require positive distances or a particular tie-breaking rule.
The interval construction correctly represents each type’s mass and every real coalition vector satisfying \(0\le\lambda_\theta\le\mu_\theta\).
Each consumption step can be realized by measurable portions of the eligible type intervals. Choosing currently unconsumed portions makes the sets \(B_r\) pairwise disjoint, each of measure \(q\). The suggested interval implementation consumes the entire population after the final iteration; coverage up to a null set would also suffice for every subsequent argument.
The construction correctly distinguishes different portions of one type. Removing \(B_r\) therefore removes only the captured portion, which is essential to the later distinctness argument.
The maximum \(D\) exists because \(A\) has positive measure and only finitely many types occur.
The first captured set intersecting \(A\) in positive measure exists because the captured sets cover the population. Before that selection, the intersection of \(A\) with all previously consumed sets has measure zero: there are only finitely many such sets, each having zero-measure intersection with \(A\).
All but a null subset of \(A\) lies at distance at most \(D\) from \(c\). Hence at least \(q\) residual mass lies within that radius. Since \(c\notin R\), it remains available throughout the algorithm. The deductions \(h_c\le D\) and \(\delta_r\le D\) follow.
Positive-measure intersection with \(B_r\) supplies a type \(\theta_0\) satisfying \(d(\theta_0,r)\le D\). A maximizing type \(\theta_*\) exists and has positive mass in \(A\).
The case \(D=0\) is handled correctly: both relevant distances for \(\theta_0\) are zero.
For \(D>0\), both branches are valid. In the second branch, symmetry and repeated triangle inequality justify the displayed bound \(d(\theta_*,r)\le 2D+x\). The constant identity is exact: for \(\rho=1+\sqrt2\), one has \(1/\rho=\sqrt2-1\), hence \(2+1/\rho=\rho\).
A potentially delicate point is handled correctly: the lemma only requires the witnessing type to have positive mass in \(A\). It does not require that type to belong to \(B_r\). Thus using \(\theta_*\) in the second branch satisfies the stated conclusion.
A minimizing comparison subcommittee exists because there are finitely many size-\(t\) subsets of \(C\).
Ordering the candidates already in \(R\) first makes their assignments \(r_i=c_i\) distinct and ensures that every subsequent comparison candidate lies outside \(R\).
Removing the earlier captured sets removes at most \((i-1)q\) coalition mass. Since \(s\ge\alpha tq>tq\), the claimed inequality \(\nu(S_i)>q\) holds for every relevant index.
A closest mass-\(q\) subset \(T_i\) exists by processing finitely many distance levels and taking a partial portion at the final level. Its construction ensures that all strictly closer residual coalition mass is included, up to measure zero.
The stability lemma applies with its exact hypotheses: \(T_i\) is measurable, has mass \(q\), and \(c_i\notin R\).
The resulting representative is distinct from every earlier representative. Indeed, \(T_i\) is disjoint from each earlier \(B_{r_j}\), whereas membership in \(R[T_i]\) requires positive-measure intersection with its own captured set. Therefore the constructed \(Q\) has exactly \(t\) members.
Symmetry and triangle inequality justify the pointwise bound using the witnessing type \(\theta_i\). Since that type has positive mass in \(T_i\), its distance to \(c_i\) is at most \(D_i\). Integrating the bound over \(S\) gives the stated inequality for \(F_S(r_i)\).
The estimate for \(P_i\) is also valid. Its portion outside \(S_i\) has measure at most \((i-1)q\); its portion inside \(S_i\) lies in \(T_i\), up to measure zero, and therefore has measure at most \(q\). Hence \(\nu(P_i)\le iq\).
Every point outside \(P_i\) has distance at least \(D_i\). Nonnegativity therefore gives \(F_S(c_i)\ge(s-iq)D_i\). The denominator is strictly positive because \(s>tq\ge iq\).
Finally, \(iq\le tq\le s/\alpha\) implies the claimed ratio bound. With \(1+\rho=2+\sqrt2\), the resulting constant is exactly \(\gamma(\alpha)\).
No division by \(D_i\) or \(F_S(c_i)\) occurs. Thus zero radii and zero comparison costs are covered. For comparison candidates already selected, the same bound follows from equality of their assigned costs and \(\gamma(\alpha)>1\).
Summing the individual bounds is legitimate because the representatives are distinct. The result bounds the coalition’s cost for one shared size-\(t\) subcommittee \(Q\).
For each type, minimizing over all size-\(t\) subcommittees of \(R\) can only reduce its cost relative to this particular \(Q\). Multiplication by nonnegative coalition masses and summation therefore yields precisely the requested inequality.
The algorithm is fixed independently of \(\alpha\), \(t\), and \(\lambda\). Their arbitrary selection occurs only in the analysis, so the simultaneous guarantee follows.
When the threshold exceeds total mass, no eligible coalition exists. In particular, the stated vacuity for \(k=1\) is correct.
Sorting once and scanning the candidate lists in each iteration gives the stated polynomial arithmetic-operation count.
The denominator \(H=k\prod_\theta b_\theta\) is divisible by every input mass denominator and by \(k\). Its binary length is \(O(L+\log k)\); its potentially large numerical value does not imply a large encoding.
Consuming eligible masses in fixed order preserves integer multiples of \(1/H\). Residual masses and partial sums remain bounded by total mass, so their integer representations have polynomial bit length.
Rational distance comparisons by cross-multiplication also have polynomial bit cost. Selection uses only input distances, and the algorithm need not compute \(\sqrt2\).
Thus the write-up establishes polynomial running time in the requested parameters without expanding the population into individual voters.
No repair feedback is needed. The proof is self-contained; its correctness does not depend on importing an unstated theorem from the cited paper.
⟨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.