Answer: Both the cardinal and ordinal problems are in \(\mathrm{P}\). Every promised instance has a feasible committee, constructible in time polynomial in \(m,\tau,k,L\).
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe EXPANDING APPROVALS RULE out- puts a committee R of size k which is (α, γ(α))- proportionally representative for all α > 1, with γ(α) = 1 + 7+ √ 41 2 · α α−1 ≈1 + 6.71 · α α−1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), \(\alpha > 1\), a finite set of complete voter types \(T\) with rational masses \(\mu\), and either full type-to-candidate distances or ordinal rankings together with compatible pseudometric distances, choose a committee \(R \subseteq C\) of size \(k\) such that for every integer \(j\) with \(j\alpha/k \le 1\) and every subdistribution \(\sigma \le \mu\) of mass at least \(j\alpha/k\), the weighted cost of the best \(j\) members of \(R\) for \(\sigma\) is at most \(\gamma(\alpha) = 1 + (7 + \sqrt{41})\alpha/(2(\alpha-1))\) times the weighted cost of the best \(j\) candidates in \(C\) for \(\sigma\); determine whether such an \(R\) exists, construct one, and study the optimum achievable factor.
Let \(C\) contain \(m\) candidates, let \(1\le k<m\), and let \(\alpha>1\) be a binary rational.
A society is given by its support: the list \(T\) of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
In the cardinal model, all nonnegative rational distances \(d(t,c)\) are given and promised to extend to a pseudometric on \(T\cup C\). In the ordinal model, only a strict complete ranking \(\succ_t\) for each type is given; a compatible pseudometric satisfies \(c\succ_t c'\Rightarrow d(t,c)\le d(t,c')\), allowing distance ties.
A coalition is any real subdistribution \(0\le\sigma_t\le\mu_t\), with mass \(|\sigma|=\sum_t\sigma_t\). For \(R\subseteq C\) of size \(k\), define \(A_j(R,\sigma;d)=\sum_t\sigma_t\min_{Q\subseteq R,\,|Q|=j}\sum_{c\in Q}d(t,c)\) and \(B_j(\sigma;d)=\min_{Q\subseteq C,\,|Q|=j}\sum_t\sigma_t\sum_{c\in Q}d(t,c)\).
Call \(R\) feasible if \(A_j(R,\sigma;d)\le\gamma(\alpha)B_j(\sigma;d)\), where \(\gamma(\alpha)=1+\frac{(7+\sqrt{41})\alpha}{2(\alpha-1)}\), for every integer \(1\le j\le k\) and coalition satisfying \(|\sigma|\ge j\alpha/k\). In the ordinal model, the same \(R\) must satisfy these inequalities for every compatible pseudometric. The inequality applies also when \(B_j=0\).
For each information model, is deciding whether a feasible committee exists in \(\mathrm{P}\), with construction in time polynomial in \(m,\tau,k,L\) whenever one exists, or is the decision problem \(\mathrm{NP}\)-hard?
For explicitly listed finite voters, Expanding Approvals constructs a committee with the stated factor using only rankings in \(\widetilde{O}(mn)\) time, with coalition thresholds \(j\alpha\lceil n/k\rceil\). [Verified full version](https://arxiv.org/html/2312.10369v2).
No result settling exactly the support-encoded mass problem above was located in the literature search.
1. Result
Both information models are in \(\mathrm{P}\). More strongly, every promised instance has a feasible committee, and one can construct such a committee in time polynomial in \(m,\tau,k,L\).
The proof uses an exact compressed simulation of Expanding Approvals. Replication removes the ceiling in the finite-voter threshold, while invariance under further replication extends the guarantee to all real coalitions.
2. The finite-voter theorem used
We use the supplied result precisely as follows. On an electorate of \(n\) explicitly listed voters, Expanding Approvals selects a committee \(R\) of size \(k\). For every compatible pseudometric, every \(\alpha>1\), every \(1\le j\le k\), and every voter subset \(S\) satisfying
\[ |S|\ge j\alpha\lceil n/k\rceil, \]
the committee satisfies
\[ \sum_{v\in S}\min_{\substack{Q\subseteq R\\|Q|=j}} \sum_{c\in Q}d(v,c) \le \gamma(\alpha) \min_{\substack{Q\subseteq C\\|Q|=j}} \sum_{v\in S}\sum_{c\in Q}d(v,c). \]
We use Algorithm 1, with a fixed voter order and fixed arbitrary completion rule. Its sequential implementation elects a candidate when its neighborhood reaches exactly \(\lceil n/k\rceil\), and removes that neighborhood. The theorem allows pseudometrics, distance ties compatible with strict rankings, and the displayed inequality without division by its right-hand side. These are the conventions of [Algorithm 1, Theorem 4.1, and Section 3 of the supplied full version](https://arxiv.org/html/2312.10369v2).
3. A polynomial compressed implementation
First consider the ordinal model. Fix orders on the types and candidates. Write each mass as \(\mu_t=a_t/b_t\), where \(a_t,b_t\) are positive integers, and define
\[ D=k\prod_{t\in T}b_t,\qquad p=D/k. \]
Thus \(D\mu_t\) and \(p\) are integers. Conceptually, replace type \(t\) by \(D\mu_t\) identical voters and place these voters consecutively in the fixed type order. This electorate has exactly \(D\) voters, and its finite-voter quota is
\[ \lceil D/k\rceil=D/k=p. \]
We will simulate this electorate without listing its voters.
Maintain:
At the boundaries between type blocks, the meaning of \(F_{t,c}\), for an unselected candidate \(c\), is that all currently uncovered voters of type \(t\) belong to \(c\)'s neighborhood. A false flag means that none belong. Flags for types with \(u_t=0\) are immaterial.
For each rank \(q=1,\ldots,m\), process the types in their fixed order. For the current type \(t\):
\[ s=\sum_{\substack{b\in T\\F_{b,c}\text{ is true}}}u_b. \]
Leave the flags for other candidates unchanged. At termination, complete \(R\) to size \(k\), if necessary, using the fixed candidate order.
We now prove that these operations are well-defined and simulate the finite algorithm exactly.
At every type-block boundary, each unselected neighborhood has size strictly less than \(p\): additions elect its candidate immediately upon reaching \(p\), and removals only decrease other neighborhoods. Consequently, \(s<p\).
Furthermore, \(F_{t,c}\) is false when step 3 is reached. Indeed, type \(t\) has not previously processed candidate \(c\): that candidate occurs at exactly rank \(q\), and the current block is its first insertion opportunity.
Suppose first that \(s+u_t<p\). Processing the uncovered clones of \(t\) one at a time inserts all of them into \(c\)'s neighborhood without an election. Setting \(F_{t,c}\) to true therefore gives exactly the finite algorithm's state.
Otherwise,
\[ 1\le x=p-s\le u_t. \]
The first \(x\) uncovered clones of \(t\) bring \(c\)'s neighborhood to quota. At that moment, its neighborhood consists precisely of these \(x\) clones and all uncovered clones of the types already flagged for \(c\). Thus the finite algorithm removes exactly the voters specified in step 5. All remaining clones of \(t\) skip their insertion because \(c\) is now selected.
For every other unselected candidate, removing these voters preserves the all-or-none membership property within each type: a current type loses a prefix of its uncovered clones, and another participating type loses all its uncovered clones. Hence its unchanged flag, together with the updated \(u_t\), still describes its neighborhood correctly.
Induction over the rank and type blocks proves exact simulation. Each election removes exactly \(p\) voters, so there are at most \(D/p=k\) elections. The completion step consequently produces a committee of size \(k\), exactly as in the finite algorithm.
4. The output is invariant under replication
Replace \(D\) by \(rD\), for any positive integer \(r\). The resulting quota and initial uncovered counts are \(rp\) and \(rD\mu_t\).
Inductively, the two compressed runs have identical flags and committees, while their uncovered counts differ by the factor \(r\). Their computed neighborhood sizes therefore differ by that factor as well. In particular,
\[ s+u_t<p \quad\Longleftrightarrow\quad rs+ru_t<rp. \]
When an election occurs, the amount removed from the current type becomes
\[ rp-rs=r(p-s)=rx. \]
The updates preserve the induction hypothesis. The fixed completion rule also agrees between the runs.
Therefore, every replication size \(rD\) produces the same committee \(R\). This property will let us represent any rational coalition without changing the output.
5. Guarantee for every rational coalition and compatible pseudometric
Fix an arbitrary compatible pseudometric \(d\) on \(T\cup C\), an integer \(1\le j\le k\), and a rational subdistribution \(\sigma\) satisfying
\[ 0\le\sigma_t\le\mu_t, \qquad |\sigma|\ge j\alpha/k. \]
Choose a positive integer \(r\) such that \(n=rD\) makes every \(n\sigma_t\) integral. Create \(n\mu_t\) clones of each type and let \(S\) contain exactly \(n\sigma_t\) clones of type \(t\). Such a subset exists because \(0\le n\sigma_t\le n\mu_t\).
To define distances, map every clone of type \(t\) to \(t\), and map every candidate to itself. Define the distance between any two replicated points to be the \(d\)-distance between their images. This is a pseudometric: symmetry, nonnegativity, the zero diagonal, and the triangle inequality follow directly from the corresponding properties of \(d\). It is compatible with every clone's ranking.
Because \(k\) divides \(n\),
\[ |S|=n|\sigma| \ge j\alpha n/k =j\alpha\lceil n/k\rceil. \]
By Sections 3 and 4, the finite algorithm on this electorate returns our fixed committee \(R\). Its theorem therefore applies to \(S\).
Grouping the left-hand sum by type gives exactly \(nA_j(R,\sigma;d)\). For each fixed alternative \(Q\), grouping its sum gives
\[ \sum_{v\in S}\sum_{c\in Q}d(v,c) = n\sum_{t\in T}\sigma_t\sum_{c\in Q}d(t,c). \]
Taking the minimum over \(Q\) consequently gives \(nB_j(\sigma;d)\). Dividing the finite inequality by \(n>0\) proves
\[ A_j(R,\sigma;d)\le\gamma(\alpha)B_j(\sigma;d). \]
The committee is independent of both \(\sigma\) and \(d\). Since the compatible pseudometric was arbitrary, this establishes the required ordinal guarantee for every rational coalition, simultaneously for all compatible pseudometrics.
6. Extension to all real coalitions
Fix any real subdistribution \(\sigma\) meeting the threshold. For each positive integer \(\ell\), define the rational subdistribution
\[ \sigma_t^{(\ell)} = \min\left\{\mu_t,\frac{\lceil\ell\sigma_t\rceil}{\ell}\right\}. \]
Both entries in this minimum are at least \(\sigma_t\). Hence
\[ \sigma_t\le\sigma_t^{(\ell)}\le\mu_t, \qquad 0\le\sigma_t^{(\ell)}-\sigma_t\le1/\ell. \]
In particular,
\[ |\sigma^{(\ell)}|\ge|\sigma|\ge j\alpha/k, \]
so Section 5 applies to every \(\sigma^{(\ell)}\).
For fixed \(R,j,d\), the function \(A_j(R,\sigma;d)\) is linear in \(\sigma\): its coefficient for type \(t\) is the fixed sum of that type's \(j\) smallest distances within \(R\). The function \(B_j(\sigma;d)\) is continuous, being the minimum of finitely many linear functions of \(\sigma\).
Passing to the limit in the rational-coalition inequalities gives
\[ A_j(R,\sigma;d)\le\gamma(\alpha)B_j(\sigma;d). \]
This also covers \(B_j(\sigma;d)=0\). No division by \(B_j\) was used; the inequality then forces \(A_j(R,\sigma;d)=0\).
Thus \(R\) is feasible in the ordinal model.
7. Bit complexity and the cardinal model
Although \(D\) may be numerically large, its bit length satisfies
\[ \log_2D=\log_2k+\sum_{t\in T}\log_2b_t=O(L+\log k). \]
All uncovered counts, quotas, neighborhood sizes, and removal amounts are integers between zero and \(D\). Their arithmetic therefore has polynomial bit complexity.
There are \(m\tau\) type blocks. Computing a neighborhood size by scanning the types uses at most \(\tau\) additions per block; an election requires at most \(\tau\) updates. Thus the simulation uses
\[ O(m\tau^2+k\tau) \]
integer operations on numbers of polynomial bit length. Computing the initial counts and storing the rankings and flags also take polynomial time and space. Crucially, the algorithm never lists the replicated voters.
In the cardinal model, sort each type's candidates by the given rational distances, breaking equal-distance ties by a fixed candidate order. These strict rankings are compatible with every promised pseudometric extension of the given distances. Exact rational comparisons and sorting take polynomial time. Apply the ordinal construction to these rankings.
The resulting committee satisfies the desired inequalities for the given distances, since all quantities \(A_j\) and \(B_j\) depend only on the supplied type-to-candidate distances.
Consequently, both models admit polynomial-time construction on every promised instance, and their existence decision problems always answer yes.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument resolves both information models. The compressed algorithm correctly simulates the cited finite-voter algorithm, its output is invariant under integer replication, and the limiting argument covers every real coalition, including those with zero benchmark cost. I found no major or minor mathematical issues.
I checked Algorithm 1, Theorem 4.1, Definitions 2.1–2.2, and Section 3 of the [supplied full version](https://arxiv.org/html/2312.10369v2). The source explicitly permits pseudometrics and rankings consistent with nondecreasing distances, including distance ties. Its proportional-representation definition is an inequality rather than a quotient, so it includes zero benchmark costs.
Theorem 4.1 gives precisely the stated factor for every \(\alpha>1\), with coalition threshold \(j\alpha\lceil n/k\rceil\). Algorithm 1 processes voters sequentially in arbitrary order, elects a candidate upon its neighborhood reaching exactly the quota, removes that neighborhood from the uncovered voters and other unselected neighborhoods, and completes the committee arbitrarily if necessary.
Thus Section 2 accurately states the theorem and algorithm used. No stronger, unsupported finite-voter result is assumed.
Because each denominator \(b_t\) divides \(D=k\prod_t b_t\), every clone count \(D\mu_t\) is a positive integer. The normalization of the masses gives
\[
\sum_{t\in T}D\mu_t=D.
\]
Also, \(k\mid D\), so the finite-voter quota is exactly \(p=D/k\). This correctly removes the ceiling without changing the required normalized threshold.
The all-or-none neighborhood invariant holds initially. At a type-block boundary, each unselected neighborhood has fewer than \(p\) voters: reaching \(p\) immediately selects its candidate, and subsequent removals cannot increase any neighborhood.
When the current type processes candidate \(c\), its flag \(F_{t,c}\) is false because a strict complete ranking contains \(c\) exactly once. Therefore the computed \(s\) counts only previously inserted, currently uncovered voters, without counting the current block twice.
Both update cases are correct:
For any other unselected candidate, the current type previously had either all or none of its uncovered clones in that neighborhood. Removing a prefix preserves that property. Removing all uncovered clones of another participating type also preserves it. Consequently, leaving the other flags unchanged is valid.
The induction therefore establishes exact simulation. Each election removes \(p\) distinct uncovered voters, giving at most \(D/p=k\) elections. Committee completion is consequently well-defined and agrees with the fixed finite completion rule.
Under multiplication by a positive integer \(r\), initial counts and quota scale uniformly. The branch test is unchanged, and each partial removal scales by \(r\). The induction maintains identical flags, committee selections, and completion choices.
This proves that the same committee is returned for every electorate size \(rD\). The property is sufficient for the later argument: changing the replication size to accommodate a coalition does not change the committee being certified.
For any rational coalition, a suitable integer \(r\) makes all \(rD\sigma_t\) integral. The coordinate bounds ensure that the specified coalition subset exists among the clones.
Pulling back the fixed compatible pseudometric along the clone-to-type map preserves every pseudometric axiom. Each clone retains its type’s compatible ranking. With \(n=rD\), the threshold calculation
\[
|S|=n|\sigma|\ge j\alpha n/k
=j\alpha\lceil n/k\rceil
\]
is exact.
Grouping clone contributions gives \(nA_j\) on the left. For every fixed alternative committee, its cost is \(n\) times the corresponding type cost; taking the finite minimum therefore gives \(nB_j\). Division by \(n>0\) is legitimate.
The quantifiers are also correct: the committee depends only on rankings, masses, and fixed orders. The coalition and compatible pseudometric are chosen afterward and arbitrarily.
Each \(\sigma_t^{(\ell)}\) is rational because both arguments of its minimum are rational. The stated bounds hold:
\[
\sigma_t\le \sigma_t^{(\ell)}\le\mu_t,
\qquad
0\le\sigma_t^{(\ell)}-\sigma_t\le 1/\ell.
\]
Thus every approximation remains an admissible coalition and meets the threshold, even when the original coalition meets it exactly.
For fixed \(R,j,d\), the left side is linear in the coalition coordinates. The right-side benchmark is the minimum of finitely many linear functions and is therefore continuous. Coordinatewise convergence in this finite-dimensional setting justifies passage to the limit.
No division by \(B_j\) occurs. When \(B_j=0\), the resulting inequality and nonnegativity imply \(A_j=0\), as required.
The bit length of \(D\) is bounded by the combined denominator encoding lengths plus the bit length of \(k\). All maintained integer quantities have polynomial bit length. Constructing \(D\) and the initial counts requires only polynomial-time integer arithmetic.
There are \(m\tau\) blocks, each requiring at most a scan of \(\tau\) types. At most \(k\) elections require additional scans. The stated operation bound \(O(m\tau^2+k\tau)\), together with polynomial operand lengths and polynomial storage, establishes the required construction bound.
The algorithm need not evaluate the irrational constant \(\gamma(\alpha)\); it uses that constant only in its correctness guarantee.
Sorting the supplied rational distances, with fixed tie breaking, yields strict rankings compatible with any promised pseudometric extension. Exact rational comparisons take polynomial time. Applying the ordinal construction therefore certifies the supplied distances, since the two objective functions use only type-to-candidate distances.
Vacuous coalition constraints, including those arising when the threshold exceeds total mass, cause no difficulty. Both constructions still return a committee of the required size.
Consequently, every promised instance admits a feasible committee, and both existence decision problems are in polynomial time. No additional clarification or repair is needed.
⟨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.