Answer: \(\mathrm{NP}\)-complete
Observation 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each rational numberX,X ≥1, the problem of deciding if there exists a size-k committee and a X-balanced k-CC- assignment function for it with at least a given voter satisfaction (for a given election and committee size k) is NP-complete. This problem is in FPT for both the parameterization by the number of voters and the parameterization by the number of candidates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) candidates, committee size \(k\), a support of \(\tau\) complete rankings with rational masses \(\mu_t\ge 0\) summing to \(1\), and a rational threshold \(\theta\), is there a size-\(k\) committee \(S\) and assignment masses \(y_{t,c}\ge 0\) such that \(\sum_{c\in S}y_{t,c}=\mu_t\), \(\sum_t y_{t,c}=1/k\) for every \(c\in S\), and \(\sum_t\sum_{c\in S}y_{t,c}(m-\operatorname{pos}_t(c))\ge\theta\)?
Let \(C\) be a set of \(m\ge 1\) candidates and let \(1\le k\le m\) be an input integer. A society is given by its support: a list of \(\tau\) distinct strict complete rankings of \(C\), each with positive mass \(\mu_t\) encoded as a binary rational, with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. The threshold \(\theta\in\mathbb{Q}\) is also encoded in binary; let \(L\) be the total input bit length.
A committee is a subset \(S\subseteq C\) with \(|S|=k\). Its assignment consists of divisible real masses \(y_{t,c}\ge 0\), indexed by supported types and committee members, satisfying \(\sum_{c\in S}y_{t,c}=\mu_t\) for every type and \(\sum_{t=1}^{\tau}y_{t,c}=1/k\) for every committee member.
Write \(\operatorname{pos}_t(c)\) for the position of \(c\) in ranking \(t\), starting at \(1\). An assignment meets the threshold when \(\sum_{t=1}^{\tau}\sum_{c\in S}y_{t,c}(m-\operatorname{pos}_t(c))\ge\theta\); any committee meeting it is admissible, with no tie-breaking requirement.
Is deciding whether such a committee and assignment exist in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,k,L\).
For finite societies with indivisible voters, Borda satisfaction, and exactly equal nonempty districts, threshold feasibility is NP-complete; it is FPT separately in the number of voters and candidates. [Faliszewski–Talmon](https://ifaamas.org/Proceedings/aamas2018/pdfs/p14.pdf)
Fractional representative assignments have previously been studied, but no complexity classification for the precise support-encoded problem above was located. [Potthoff–Brams](https://journals.sagepub.com/doi/10.1177/0951692898010002001)
The problem is \(\mathrm{NP}\)-complete. Divisibility does not remove the hardness: after suitable scaling, every fixed committee has an integral optimal assignment, so the finite-voter hardness transfers to the support encoding.
An exact deterministic algorithm runs in
\(\binom{m}{k}(m+\tau+k+L)^{O(1)}\)
bit operations. In particular, the problem is fixed-parameter tractable in \(m\), and polynomial-time solvable for every fixed \(k\).
We first prove the property needed to transfer hardness.
Lemma. Let \(a_1,\ldots,a_\tau\) and \(b_1,\ldots,b_k\) be nonnegative integers with equal total. Suppose the set of nonnegative real matrices satisfying
\(\sum_{j=1}^{k}x_{t,j}=a_t\) and
\(\sum_{t=1}^{\tau}x_{t,j}=b_j\)
is nonempty. For arbitrary real coefficients \(w_{t,j}\), the objective
\(\sum_{t,j}w_{t,j}x_{t,j}\)
has an integral maximizer.
Proof. The feasible set is closed and bounded: every entry lies between zero and the common total. Thus the objective attains its maximum. Among its maximizers, choose \(x\) with the fewest nonintegral entries.
Construct a bipartite graph with row vertices and column vertices, placing an edge exactly where \(x_{t,j}\) is nonintegral. No vertex has degree one. Indeed, if precisely one entry in a row or column were nonintegral, subtracting the other, integral entries from its integral prescribed sum would make that entry integral.
If this graph has any edges, every nonisolated vertex has degree at least two, so it contains a cycle. Being bipartite, that cycle has even length. Define a matrix \(h\) by putting alternating values \(+1\) and \(-1\) on the cycle and zero elsewhere. Each row and column sum of \(h\) is zero.
All cycle entries of \(x\) are positive. Consequently, for sufficiently small positive \(\varepsilon\), both \(x+\varepsilon h\) and \(x-\varepsilon h\) are feasible. Optimality of \(x\) then forces
\(\sum_{t,j}w_{t,j}h_{t,j}=0\):
otherwise one perturbation would improve the objective.
Now choose
\(\delta=\min\bigl(\{\lceil x_{t,j}\rceil-x_{t,j}:h_{t,j}=1\}\cup\{x_{t,j}-\lfloor x_{t,j}\rfloor:h_{t,j}=-1\}\bigr)\).
Every quantity in this minimum is positive. The matrix \(x+\delta h\) remains nonnegative and preserves all margins. Each changed entry remains between its original floor and ceiling, and at least one becomes integral. No originally integral entry changes.
The objective is unchanged because its coefficient along \(h\) is zero. This contradicts the choice of \(x\). Hence \(x\) is integral. \(\square\)
We use the finite-society hardness result supplied in the question: threshold feasibility for strict Borda rankings and exactly equal nonempty districts is \(\mathrm{NP}\)-complete. This is the case \(X=1\) of Observation 3.1 in [Faliszewski–Talmon](https://ifaamas.org/Proceedings/aamas2018/pdfs/p14.pdf).
Let a source instance have \(n\) explicitly listed voters, \(m\) candidates, committee size \(k\), and total satisfaction threshold \(B\).
Exactly equal nonempty districts require \(k\mid n\). Instances violating this condition are necessarily NO-instances and can be mapped to the fixed target NO-instance \(m=k=\tau=1\), \(\mu_1=1\), \(\theta=1\). Thus we may assume \(k\mid n\).
Group identical rankings. Let the resulting distinct rankings have multiplicities \(r_1,\ldots,r_\tau\), where each \(r_t\) is positive and \(\sum_t r_t=n\). Construct the target instance using the same candidates, rankings, and committee size, with
\(\mu_t=r_t/n\) and \(\theta=B/n\).
The masses are positive binary rationals summing to one. There are at most \(n\) supported rankings, and each mass has encoding length \(O(\log(n+1))\). Grouping rankings and forming these fractions take polynomial time in the source input length. The construction therefore has polynomial output length.
We prove equivalence.
Source YES implies target YES. Suppose a source assignment uses committee \(S\). Let \(x_{t,c}\) count voters of type \(t\) assigned to \(c\). Then
\(\sum_{c\in S}x_{t,c}=r_t\) and
\(\sum_t x_{t,c}=n/k\).
Setting \(y_{t,c}=x_{t,c}/n\) satisfies all target assignment constraints. Its satisfaction equals the source satisfaction divided by \(n\), so it meets \(\theta=B/n\).
Target YES implies source YES. Suppose a target assignment \(y\) with committee \(S\) meets the threshold. Set \(x_{t,c}=ny_{t,c}\). Its margins are
\(\sum_{c\in S}x_{t,c}=r_t\) and
\(\sum_t x_{t,c}=n/k\),
which are integers. Its objective satisfies
\(\sum_{t,c\in S}x_{t,c}(m-\operatorname{pos}_t(c))\ge B\).
Apply the lemma to this fixed committee, with coefficients \(m-\operatorname{pos}_t(c)\). An integral maximizer \(x^*\) exists and has objective at least that of \(x\), hence at least \(B\).
For every type \(t\), partition its \(r_t\) individual voters into groups of sizes \(x^*_{t,c}\), assigning the corresponding group to \(c\). This is possible because those entries are nonnegative integers summing to \(r_t\). Each committee member receives exactly \(n/k\) voters. Since all voters of a type share their ranking, this assignment has exactly the objective of \(x^*\).
Thus the source instance is YES. The reduction proves \(\mathrm{NP}\)-hardness.
Real assignments do not prevent polynomial-size certificates.
Write \(\mu_t=p_t/q_t\), with positive integer denominators \(q_t\), and define
\(D=k\prod_{t=1}^{\tau}q_t\).
Its binary encoding length is \(O(L+\log(k+1))\). Both \(D\mu_t\) and \(D/k\) are integers.
For any fixed committee, scaling assignments by \(D\) gives the margins
\(\sum_{c\in S}x_{t,c}=D\mu_t\) and
\(\sum_t x_{t,c}=D/k\).
This transportation set is nonempty: the assignment \(y_{t,c}=\mu_t/k\) is feasible.
If a committee admits a threshold-meeting assignment, the lemma gives an integral maximizer \(x^*\) for these scaled margins. Its normalized assignment \(x^*/D\) also meets the threshold.
A certificate therefore consists of the committee and the \(\tau k\) integers \(x^*_{t,c}\). Every entry lies between zero and \(D\), so the certificate length is
\(O(k\log(m+1)+\tau k(L+\log(k+1)))\).
The verifier checks nonnegativity, the row and column sums, and
\(\sum_{t,c\in S}x^*_{t,c}(m-\operatorname{pos}_t(c))\ge D\theta\).
All checks use exact integer arithmetic and rational cross-multiplication on polynomially many bits. Verification takes \((m+\tau+k+L)^{O(1)}\) bit operations.
Consequently, the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
For a fixed committee \(S\), threshold feasibility is a rational linear program with \(\tau k\) variables, \(\tau+k\) margin equations, nonnegativity constraints, and one satisfaction inequality. All coefficients have polynomial encoding length in \(m,\tau,k,L\). Polynomial-time rational linear programming therefore decides it in
\((m+\tau+k+L)^{O(1)}\)
bit operations.
Enumerating all committees gives the exact deterministic bound
\(\binom{m}{k}(m+\tau+k+L)^{O(1)}\).
Since \(\binom{m}{k}\le 2^m\) and \(\binom{m}{k}\le m^k\), this also yields bounds
\(2^m(m+\tau+k+L)^{O(1)}\) and
\(m^k(m+\tau+k+L)^{O(1)}\).
The first proves fixed-parameter tractability in \(m\); the second proves polynomial-time solvability for fixed \(k\). Neither bound involves expanding binary rational masses into individual voters. The general problem has no polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s output correctly establishes $\mathrm{NP}$-completeness for the support-encoded problem. The reduction preserves threshold feasibility in both directions, the integrality lemma is valid, and the certificate and running-time bounds are polynomial in the stated input parameters. I found no major or minor mathematical issues.
The lemma’s hypotheses are sufficient: the margins are nonnegative integers with equal total, feasibility is assumed, and the objective has finitely many real coefficients.
Every feasible entry is bounded by the common total. Consequently, the feasible set is compact, and the linear objective attains its maximum. Choosing a maximizer with the fewest nonintegral entries is legitimate because the number of such entries takes values in a finite set of integers.
The graph argument is correct:
Every cycle entry is positive because it is nonnegative and nonintegral. Both sufficiently small perturbations are therefore feasible. Optimality forces the objective’s coefficient along the perturbation to vanish.
The definition of $\delta$ is also correct. Each quantity being minimized lies strictly between zero and one. Under the positive perturbation, increasing entries cannot exceed their original ceilings, and decreasing entries cannot fall below their original floors. Nonnegativity is preserved, at least one nonintegral entry becomes integral, and originally integral entries remain unchanged. This contradicts minimality.
Finding: The lemma is rigorously proved, including zero margins and zero common total.
The source theorem is accurately identified. Observation 3.1 states $\mathrm{NP}$-completeness of threshold feasibility for each fixed rational balancedness parameter $X\ge 1$. Definition 2.3 requires exactly $k$ nonempty districts and bounds every district-size ratio by $X$. At $X=1$, these districts have exactly equal sizes. The paper uses complete rankings and Borda satisfaction $m-\operatorname{pos}(c)$, matching the reduction. [Faliszewski–Talmon, Definitions 2.3 and Observation 3.1](https://ifaamas.org/Proceedings/aamas2018/pdfs/p14.pdf)
Thus the prover invokes the exact-equality source problem, rather than relying on a version allowing district sizes to differ by one.
Finding: The cited theorem and its relevant hypotheses match the source problem as written.
Exactly equal nonempty districts imply $k\mid n$. Mapping instances violating divisibility to the stated fixed NO-instance is valid: its sole candidate has Borda satisfaction zero, while its threshold is one.
Grouping identical rankings produces positive multiplicities $r_t$ and distinct supported rankings. The constructed masses $r_t/n$ are positive and sum to one. Their numerator and denominator lengths are $O(\log(n+1))$.
Because voters are explicitly listed in the source instance, grouping them and writing at most $n$ distinct rankings takes polynomial time. Forming $B/n$ also has polynomial bit complexity and output length.
Finding: The reduction is a polynomial-time construction of a valid target instance.
For the forward direction, the type-level counts have row sums $r_t$ and column sums $n/k$. Dividing by $n$ gives exactly the required target margins and scales total satisfaction by $1/n$.
For the reverse direction, multiplying a feasible target assignment by $n$ gives integer prescribed margins, even though its entries may initially be real. The fixed-committee lemma applies because $k\mid n$. Its integral maximizer has satisfaction at least that of the scaled feasible assignment, hence at least $B$.
The reconstruction of individual assignments is justified: each row consists of nonnegative integer group sizes summing to the number of voters of that type. Each selected candidate receives exactly $n/k$ voters, which is positive. Identical rankings within each type ensure that reconstruction preserves satisfaction.
Both directions use the same committee and preserve the non-strict threshold comparison.
Finding: The equivalence is complete and establishes $\mathrm{NP}$-hardness.
The scaling factor
$$
D=k\prod_{t=1}^{\tau}q_t
$$
has polynomial bit length: its logarithm is bounded by $\log k+\sum_t\log q_t$, and the denominator encodings are included in $L$. Both $D\mu_t$ and $D/k$ are integers.
The proposed assignment $y_{t,c}=\mu_t/k$ satisfies every margin, establishing nonemptiness for every committee. Applying the lemma to the scaled transportation problem gives an integral optimum whenever the committee meets the threshold.
Every certificate entry lies between zero and $D$, so the stated certificate-size bound is valid. Checking the committee, margins, and threshold requires only polynomially many operations on polynomial-length integers. A rational threshold of either sign presents no difficulty: cross-multiplication uses its positive denominator.
Finding: The proof establishes polynomial-size certificates and polynomial-time verification.
For each committee, the stated linear program has $\tau k$ variables, $\tau+k$ margin equations, nonnegativity constraints, and one threshold inequality. Its coefficients are rational with polynomial total encoding length; Borda coefficients are integers between zero and $m-1$. The polynomial-time theorem for rational linear-program feasibility therefore applies.
Enumeration gives
$$
\binom{m}{k}(m+\tau+k+L)^{O(1)}
$$
bit operations. The inequalities $\binom{m}{k}\le 2^m$ and $\binom{m}{k}\le m^k$ justify both derived bounds.
Since $k\le m$, the first bound establishes fixed-parameter tractability in $m$. The second establishes polynomial time for each fixed $k$; the prover correctly does not claim that it establishes fixed-parameter tractability in $k$.
The boundary cases $k=1$ and $k=m$ remain covered. No algorithm expands binary rational masses into individual voters.
Finding: All stated running-time and parameterized-complexity claims follow.
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.