Answer: Polynomial-time solvable, with exact computation in \(\mathrm{FP}\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor each decomposable committee scoring rule Rf defined via polynomial-time computable single-winner scoring functions, there is a polynomial-time algorithm that computes the (restricted) Banzhaf values for each candidate in a given election. We leave the question of whether there are natural com- mittee scoring rules for which computing restricted Banzhaf values is NP-hard as interesting future work. Experimental Evaluation We performed two sets of experiments to evaluate our algo- rithms. In the first one, we tested how the performance of our heuristics for the t-Borda family of rules changes with t.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\) of size \(m\), committee size \(k\), a decomposable committee scoring rule with polynomial-time computable rational component scores, a partial committee \(W\subseteq C\) with \(|W|<k\), and a society supported on \(\tau\) complete rankings \(t\), each with positive rational mass \(\mu_t\) summing to \(1\), define \(Q_\mu(S)=\sum_t\mu_t f_{m,|S|}(\operatorname{pos}_t(S))\) and \(Q_\mu(\varnothing)=0\). Compute, exactly, for every \(c\in C\setminus W\), \(B_\mu(c;k,W)=\sum_{S\subseteq C:\,W\subseteq S,\,|S|=k-1}\bigl(Q_\mu(S\cup\{c\})-Q_\mu(S)\bigr)\), and return a candidate maximizing this value. Is this computable in time polynomial in \(m\), \(\tau\), and the input bit length \(L\)?
Let \(C\) be a candidate set with \(m\geq 1\), let \(1\leq k\leq m\), and let \(W\subseteq C\) satisfy \(|W|<k\).
A society is given by its support: a list of \(\tau\) distinct strict complete rankings \(t\), each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
A decomposable committee scoring rule is specified by binary rational tables \(\gamma^{(j)}_{m,s}:\{1,\ldots,m\}\to\mathbb Q\), for \(1\leq j\leq s\leq m\), each non-increasing; scores may have either sign. Define \(f_{m,s}(i_1,\ldots,i_s)=\sum_{j=1}^{s}\gamma^{(j)}_{m,s}(i_j)\) for increasing position tuples. No consistency between different committee sizes is required.
For nonempty \(S\subseteq C\), let \(\operatorname{pos}_t(S)\) be its members' positions in ranking \(t\), sorted increasingly, with position \(1\) best. Set \(Q_\mu(S)=\sum_t\mu_t f_{m,|S|}(\operatorname{pos}_t(S))\) and \(Q_\mu(\varnothing)=0\).
For each \(c\in C\setminus W\), define \(B_\mu(c;k,W)=\sum_{S\subseteq C:\,W\subseteq S,\,|S|=k-1}\bigl(Q_\mu(S\cup\{c\})-Q_\mu(S)\bigr)\). Coalitions containing \(c\) are included and contribute zero. The computational problem is to output all these values exactly and any maximizing candidate.
Is this computational problem solvable in time polynomial in \(m,\tau,k,L\), where \(L\) is the total binary input length, or is it NP-hard?
For finite unweighted elections, restricted Banzhaf values under decomposable rules with polynomial-time computable components are polynomial-time computable ([discrete result](https://martin.lackner.xyz/publications/effheur.pdf)). No separately stated complexity result for this rational-mass formulation was located.
The problem is polynomial-time solvable, including exact output of every value and a maximizing candidate. The proof below gives an explicit counting algorithm and bounds its bit complexity.
The cited paper establishes the corresponding discrete-election result in Theorem 2. Here we prove the rational-mass formulation directly, without expanding rational masses into voters. [Faliszewski, Lackner, Peters, and Talmon, *Effective Heuristics for Committee Scoring Rules*](https://martin.lackner.xyz/publications/effheur.pdf).
Fix a ranking \(t\), and write \(p_t(a)\) for the position of candidate \(a\). Define its individual committee score by
\(q_t(T)=f_{m,|T|}(\operatorname{pos}_t(T))\) for nonempty \(T\), and \(q_t(\varnothing)=0\).
For disjoint sets \(R,E\subseteq C\) and \(0\leq s\leq m\), define
\[ H_t(s;R,E)= \sum_{\substack{T\subseteq C\setminus E\\R\subseteq T,\ |T|=s}}q_t(T). \]
Thus \(R\) contains required candidates and \(E\) contains excluded candidates. We will evaluate this sum without enumerating committees.
Let \(F=C\setminus(R\cup E)\), the set of optional candidates. For each \(a\in C\setminus E\), define
\[ \begin{aligned} r_{<}(a)&=|\{b\in R:p_t(b)<p_t(a)\}|,\\ r_{>}(a)&=|\{b\in R:p_t(b)>p_t(a)\}|,\\ u_{<}(a)&=|\{b\in F:p_t(b)<p_t(a)\}|,\\ u_{>}(a)&=|\{b\in F:p_t(b)>p_t(a)\}|. \end{aligned} \]
Use the convention \(\binom{n}{h}=0\) when \(h<0\) or \(h>n\).
Lemma. For \(s\geq1\), the number of admissible committees in which \(a\) is the \(j\)-th best-ranked member is
\[ N_t(a,j;s,R,E)= \binom{u_{<}(a)}{j-1-r_{<}(a)} \binom{u_{>}(a)}{s-j-r_{>}(a)}. \]
Consequently,
\[ H_t(s;R,E)= \sum_{a\in C\setminus E}\sum_{j=1}^{s} \gamma^{(j)}_{m,s}(p_t(a))\,N_t(a,j;s,R,E). \tag{1} \]
For \(s=0\), \(H_t(0;R,E)=0\).
Proof. An admissible committee containing \(a\) must contain every candidate in \(R\). To make \(a\) its \(j\)-th best-ranked member, it must have exactly \(j-1\) members above \(a\) and \(s-j\) below it. The required candidates already supply \(r_{<}(a)\) and \(r_{>}(a)\) of these members. Therefore we must choose exactly
\[ j-1-r_{<}(a) \quad\text{and}\quad s-j-r_{>}(a) \]
optional candidates above and below \(a\), respectively.
These choices are independent because the two sets are disjoint. If \(a\) is optional, it is included separately; the strict position inequalities ensure that neither optional set contains \(a\). Each pair of choices therefore gives exactly one admissible committee, and every such committee gives exactly one pair. This proves the count, including impossible cases through the binomial convention.
By decomposability, each committee contributes \(\gamma^{(j)}_{m,s}(p_t(a))\) for its member \(a\) of committee rank \(j\). Summing these contributions and regrouping by \(a,j\) proves (1). At size zero, every contributing committee has score zero. \(\square\)
Fix \(c\in C\setminus W\). Coalitions containing \(c\) contribute zero, so
\[ B_\mu(c;k,W)= \sum_{\substack{S\subseteq C\setminus\{c\}\\W\subseteq S,\ |S|=k-1}} \bigl(Q_\mu(S\cup\{c\})-Q_\mu(S)\bigr). \]
The map \(S\mapsto S\cup\{c\}\) is a bijection from this coalition family to
\[ \{T\subseteq C:W\cup\{c\}\subseteq T,\ |T|=k\}. \]
Its inverse is \(T\mapsto T\setminus\{c\}\). Expanding \(Q_\mu\) and interchanging finite sums therefore gives
\[ B_\mu(c;k,W)= \sum_t\mu_t\Bigl( H_t(k;W\cup\{c\},\varnothing) - H_t(k-1;W,\{c\}) \Bigr). \tag{2} \]
Equations (1) and (2) are an explicit exact algorithm. They use the size-\(k\) and size-\((k-1)\) tables separately, so they require no consistency between committee sizes.
For \(k=1\), necessarily \(W=\varnothing\); the second aggregate is zero, and (2) gives \(B_\mu(c;1,\varnothing)=Q_\mu(\{c\})\). Thus this boundary case needs no size-zero scoring table.
Precompute all binomial coefficients with upper argument at most \(m\) using Pascal’s recurrence. This takes \(O(m^2)\) integer additions.
For a fixed ranking and fixed \(R,E\), all four counts in the lemma can be computed in \(O(m)\) time by scanning the ranking and maintaining prefix counts. Formula (1) then has at most \(ms\) terms.
For each candidate, equation (2) requires two aggregates per ranking, with sizes at most \(k\). There are at most \(m\) candidates and \(\tau\) rankings. Hence, apart from reading and preparing the input, the algorithm uses
\[ O(m^2+\tau m^2k) \]
arithmetic operations. The exponentially many committees have been replaced by binomial counts.
An arithmetic-operation bound alone is insufficient for binary rational input. We now bound all integer lengths.
Write each mass as \(\mu_t=a_t/b_t\), and each table entry as \(p_e/q_e\), with positive denominators. Let
\[ D=\left(\prod_t b_t\right)\left(\prod_e q_e\right), \]
where the second product ranges over all supplied table entries, including repeated denominator values as separate factors.
The sum of the denominator encoding lengths is at most \(L\), so \(D\) has \(O(L)\) bits. For every mass and table entry, \(b_tq_e\) divides \(D\). Thus
\[ G_{t,e}=a_tp_e\,\frac{D}{b_tq_e} \]
is an integer satisfying
\[ \mu_t\,\frac{p_e}{q_e}=\frac{G_{t,e}}{D}. \]
We can consequently evaluate (1) and (2) entirely with integer numerators over the common denominator \(D\).
Each input numerator has \(O(L)\) bits, so every \(G_{t,e}\) has \(O(L)\) bits. Moreover,
\[ \binom{n}{h}\leq 2^n \]
for valid arguments. In a coefficient \(N_t\), the two upper arguments satisfy \(u_{<}(a)+u_{>}(a)\leq m\); hence \(N_t\leq2^m\). Each scaled summand therefore has \(O(L+m)\) bits.
For one candidate, the numerator is a signed sum of at most \(2\tau mk\) such terms. Every intermediate partial sum has
\[ O\bigl(L+m+\log(\tau mk+1)\bigr) \]
bits, because its absolute value is bounded by the sum of the absolute values of its terms. Standard integer addition, multiplication, and exact division on these lengths take polynomial time. Constructing \(D\) and the scaled entries also takes polynomial time in the stated parameters.
Thus every output has a polynomial-length representation \(N_c/D\). Since \(D>0\), comparing the integers \(N_c\) determines a maximizing candidate exactly. Such a candidate exists because \(|W|<k\leq m\) implies \(C\setminus W\neq\varnothing\). Fractions may optionally be reduced using the polynomial-time Euclidean algorithm.
This proves polynomial-time solvability in \(m,\tau,k,L\). Signed scores cause no difficulty, and the algorithm does not require their assumed monotonicity.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The counting formula, its application to restricted Banzhaf values, and the binary bit-complexity analysis are sound. No mathematical repair or additional lemma is needed.
The definition of \(H_t(s;R,E)\) correctly describes committees of size \(s\) containing all required candidates and excluding all forbidden candidates. Its stated hypothesis \(R\cap E=\varnothing\) ensures these requirements are compatible.
For every \(a\in C\setminus E\), exactly one of the following holds: \(a\in R\) or \(a\in F\). The proof correctly handles both:
Consequently, the lower binomial arguments count precisely the additional members needed above and below \(a\). These pools are disjoint, so multiplying their choice counts is justified. Strict complete rankings ensure every other candidate lies on exactly one side of \(a\).
The stated binomial convention correctly makes impossible configurations contribute zero. This includes insufficient optional candidates, too many required candidates on either side, and \(s<|R|\).
Equation (1) is valid: decomposability expresses each committee score as one contribution per member, indexed by that member’s rank within the committee. The regrouping counts every such contribution exactly once.
The declaration \(H_t(0;R,E)=0\) is also correct. If the empty committee is admissible, its score is zero; otherwise the defining sum is empty.
Finding: The lemma is proved for its stated domain.
Removing coalitions containing \(c\) is justified by the set identity \(S\cup\{c\}=S\) for those coalitions. Their contribution is zero irrespective of score signs or consistency between committee sizes.
The asserted map \(S\mapsto S\cup\{c\}\) is a bijection between the two stated families. Its inverse removes \(c\), preserves all members of \(W\), and changes the size from \(k\) to \(k-1\). The necessary hypothesis \(c\notin W\) follows from the candidate domain in the task.
Both applications of the lemma satisfy its disjointness requirement:
Expanding \(Q_\mu\) and interchanging finite sums requires no additional analytic assumption. Equation (2) therefore computes exactly the requested, unnormalized values.
The two aggregate scores use their respective size-specific tables. The argument does not assume any relationship between those tables.
Finding: Equation (2) is correct.
The prover explicitly handles \(k=1\): the hypothesis \(|W|<1\) forces \(W=\varnothing\), and the size-zero aggregate contributes zero. No undefined table is accessed. This also covers \(m=1\).
For \(k=m\), both aggregate families in equation (2) remain valid, and the lemma applies without modification. Likewise, \(|W|=k-1\) introduces no exception: the counting formula already accommodates committees whose members are all forced.
Signed table entries cause no difficulty because the proof uses finite linear sums and bounds absolute values when analyzing intermediate numerators. Monotonicity is unused, as the prover states.
The algorithm iterates over the supplied \(\tau\) rankings. It neither enumerates all possible rankings nor expands rational masses into individual voters.
Finding: The intended domain and relevant boundary cases are covered.
Pascal’s recurrence computes the necessary binomial coefficients using \(O(m^2)\) integer additions.
For fixed \(t,R,E\), ranking scans and prefix counts suffice to compute the four counts for all candidates in \(O(m)\) operations. Equation (1) contains at most \(ms\) terms.
There are at most \(m\) output candidates, two aggregates per candidate and ranking, and aggregate sizes at most \(k\). Since \(k\geq1\), the ranking-scan overhead is absorbed by the claimed bound
\(O(m^2+\tau m^2k)\).
Finding: The arithmetic-operation count is valid.
The common denominator construction is correct. Each mass denominator and each table-entry denominator appears as a separate factor in \(D\). Therefore \(b_tq_e\) divides \(D\), even when the two denominator values coincide or share prime factors.
The sum of input denominator encoding lengths bounds the binary length of their product, so \(D\) has \(O(L)\) bits. The scaled coefficients \(G_{t,e}\) are integers with \(O(L)\) bits and represent the weighted table entries exactly.
The coefficient bound is also correct. Each binomial coefficient is at most \(2^n\), and the two optional pools have total size at most \(m\). Hence their product is at most \(2^m\), giving scaled summands of \(O(L+m)\) bits.
For each candidate, equation (2) expands into at most \(2\tau mk\) signed summands. Bounding every partial sum by the sum of the absolute values of its terms justifies the stated numerator-length bound, including arbitrary cancellation.
Constructing \(D\), forming the scaled coefficients, computing binomial counts, and accumulating the numerators all require polynomially many operations on integers of polynomial length. The total number of output fractions is at most \(m\), so total output length is polynomial as well.
Finding: The proof establishes polynomial bit complexity, not merely polynomial arithmetic complexity.
All output fractions have the same positive denominator. Comparing their signed integer numerators therefore gives an exact maximizing candidate, including ties and negative values. The candidate domain is nonempty because \(|W|<k\leq m\).
The bibliographic attribution is accurate: Theorem 2 states polynomial-time computation of restricted Banzhaf values for decomposable rules whose component scoring functions are polynomial-time computable. The prover treats this as background and supplies an independent argument for the rational-mass input model, so no transfer of that theorem to a different encoding is assumed. [Source: Theorem 2](https://martin.lackner.xyz/publications/effheur.pdf).
Actionable feedback: None required. The write-up establishes the claimed polynomial-time exact algorithm.
⟨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.