Answer: Polynomial-time solvable.
Proposition 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateTop-$K$ rule is optimal for the random dictatorship rule in the probabilistic model.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(K\), a finite set of complete voter types \(T\), rational masses \(\mu_\theta\), and representation probabilities \(p_{\theta,c}\in[0,1]\), choose a \(K\)-element committee \(S\subseteq C\) maximizing \(U_\mu(S)=\frac{1}{K}\sum_{\theta\in T}\mu_\theta\sum_{c\in S}p_{\theta,c}\) under uniform random dictatorship.
Let \(C\) be a candidate set with \(m\geq 1\), and let \(1\leq K\leq m\) be an integer committee size.
A society is given by its support: the list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), normalized by \(\sum_{\theta\in T}\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type is specified by its complete vector of binary-rational representation probabilities \(p_{\theta,c}\in[0,1]\): the probability that candidate \(c\) agrees with that type on an important binary issue.
Under uniform random dictatorship, a committee member is chosen uniformly to decide each issue. Choose a set \(S\subseteq C\) with \(|S|=K\) maximizing \(U_\mu(S)=\frac{1}{K}\sum_{\theta\in T}\mu_\theta\sum_{c\in S}p_{\theta,c}\); any maximizing committee is acceptable.
Let \(L\) denote the total binary input length; state running times in \(m,\tau,K,L\).
Is exact maximization of \(U_\mu\) polynomial-time solvable in \(m,\tau,K,L\), or is it NP-hard?
For a finite list of voters with arbitrary representation probabilities, the top-\(K\) rule is optimal under uniform random dictatorship and is computable in polynomial time.
Exact maximization is polynomial-time solvable. The top-\(K\) rule applies directly to the weighted support representation; enumerating types outside the given support is unnecessary.
For each candidate \(c\in C\), define its weighted score by
\(w_c=\sum_{\theta\in T}\mu_\theta p_{\theta,c}\).
Interchanging the two finite sums in the objective gives
\(U_\mu(S)=\frac{1}{K}\sum_{c\in S}w_c\).
Since \(K\) is fixed and positive, maximizing \(U_\mu(S)\) is equivalent to maximizing \(\sum_{c\in S}w_c\) over committees of size \(K\).
Order the candidates as \(c_1,\ldots,c_m\) so that \(w_{c_1}\geq\cdots\geq w_{c_m}\), breaking ties arbitrarily, and set \(S^\star=\{c_1,\ldots,c_K\}\).
To prove optimality, let \(S\) be any committee of size \(K\). The sets \(S^\star\setminus S\) and \(S\setminus S^\star\) have equal cardinality. Every candidate in the former has score at least as large as every candidate in the latter, by the ordering. Pairing their elements therefore gives
\(\sum_{c\in S^\star\setminus S}w_c\geq\sum_{c\in S\setminus S^\star}w_c\).
Adding the scores of candidates in \(S^\star\cap S\) proves \(U_\mu(S^\star)\geq U_\mu(S)\). Thus \(S^\star\) is an exact maximizer, including when scores are tied or \(K=m\).
Represent each input rational as a binary-encoded numerator and positive denominator. The following argument covers arbitrary such rationals and, in particular, dyadic rationals.
Compute each \(w_c\) by multiplying \(\mu_\theta\) and \(p_{\theta,c}\), then adding these products using exact rational arithmetic. Fractions need not be reduced.
For a fixed candidate, an accumulated denominator can be chosen as the product of the denominators of the masses and probabilities used so far. Each of these input denominators appears at most once in this product. Their total encoded length is at most \(L\), so the accumulated denominator has \(O(L)\) bits.
Moreover, every partial score satisfies
\(0\leq\sum_{\theta\in T'}\mu_\theta p_{\theta,c}\leq\sum_{\theta\in T'}\mu_\theta\leq 1\)
for any processed subset \(T'\subseteq T\). Consequently, its nonnegative numerator is at most its denominator and also has \(O(L)\) bits. Intermediate products and sums likewise have \(O(L)\) bits. Schoolbook integer arithmetic therefore computes each rational multiplication or addition in \(O(L^2)\) bit operations.
Computing all scores takes \(O(m\tau L^2)\) bit operations. Comparing two scores exactly uses cross multiplication of their numerators and denominators, costing \(O(L^2)\) bit operations per comparison. Sorting takes \(O(m\log(m+1)L^2)\) bit operations, after which we output the first \(K\) candidate identifiers.
Including input reading and output, a valid bound is
\(O\!\left(L+m\tau L^2+m\log(m+1)L^2+K\log(m+1)\right)\).
This is polynomial in \(m,\tau,K,L\). The support size \(\tau\) enters only through the explicitly supplied weighted sums.
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the task. The optimality argument is correct, and the running-time bound accounts for exact rational arithmetic. No major or minor issues were found.
\[
O\!\left(L+m\tau L^2+m\log(m+1)L^2+K\log(m+1)\right).
\]
This is polynomial in the requested parameters. No enumeration beyond the explicit support is required.
None is required. The output establishes an exact polynomial-time algorithm for the stated input representation.
⟨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.