Answer: \(\mathsf{NP}\)-hard under polynomial-time Turing reductions, already for \(m=\tau=2\) and \(\mu_1=\mu_2=\tfrac12\).
Proposition 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf there exists a polynomial-time algorithm α that finds a seat assignment s that provides WLQo whenever such a seat assignment exists, then P = NP. This holds even when restricted to the case where there are only two parties. But with extra assumptions, we obtain a more positive result.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) party-choice types with rational masses \(\mu_p>0\), \(\sum_p\mu_p=1\), and a fixed full-supply slate of indivisible seats with binary-encoded positive integer weights \(w_1\ge\cdots\ge w_k\), let \(\omega=\sum_t w_t\), \(q(p)=\omega\mu_p\), and \(\ell_o(p)=\max\{\sum_{t\in S}w_t:S\subseteq[k],\ |S|\le\lfloor k\mu_p\rfloor,\ \sum_{t\in S}w_t\le q(p)\}\). Find an assignment \(\sigma:[k]\to[m]\) such that \(\sum_{t:\sigma(t)=p}w_t\ge\ell_o(p)\) for every \(p\), whenever such an assignment exists.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types. Here each type chooses one party, all \(m\geq1\) parties have positive mass, and \(\tau=m\).
The masses satisfy \(\mu_p>0\) and \(\sum_{p=1}^{m}\mu_p=1\). There are \(k\geq1\) indivisible seats with binary-encoded integer weights \(w_1\geq\cdots\geq w_k\geq1\). Every party can fill all seats.
Define \(\omega=\sum_{t=1}^{k}w_t\), \(q(p)=\omega\mu_p\), and \(\ell_o(p)=\max\{\sum_{t\in S}w_t:S\subseteq\{1,\ldots,k\},\ |S|\leq\lfloor k\mu_p\rfloor,\ \sum_{t\in S}w_t\leq q(p)\}\); the empty subset is allowed.
Find an assignment \(\sigma:\{1,\ldots,k\}\to\{1,\ldots,m\}\) satisfying \(\sum_{t:\sigma(t)=p}w_t\geq\ell_o(p)\) for every party whenever such an assignment exists. The cardinality bound defines the quota only; it does not constrain the assignment. On infeasible inputs the output is unrestricted.
Let \(L\) be the total input bit length; state running times in \(m,\tau,k,L\).
Is this search problem solvable in polynomial time in \(m,\tau,k,L\), or is it \(\mathsf{NP}\)-hard under polynomial-time Turing reductions?
For integer vote counts, finding such an assignment whenever one exists is hard even for two parties; every two-party instance is feasible. [Source](https://arxiv.org/html/2405.18102v2)
The verified hardness result already covers the rational-mass formulation with two equal masses and indivisible seats, so this target is already settled on the hardness side.
The search problem is \(\mathsf{NP}\)-hard under polynomial-time Turing reductions, already for \(m=\tau=2\) and \(\mu_1=\mu_2=\tfrac12\). This is the restriction established by [Proposition 3 of the cited paper](https://arxiv.org/html/2405.18102v2#S8.SS1). Here is the reduction with the cardinality and encoding details explicit.
For arbitrary positive masses with \(\mu_1+\mu_2=1\), choose a subset \(S\) attaining \(\ell_o(1)\); such a subset exists because the maximization is finite and includes the empty subset. Give \(S\) to party \(1\) and its complement to party \(2\). Their weights satisfy
\(\displaystyle r(1)=\ell_o(1),\qquad r(2)=\omega-\ell_o(1)\geq\omega-q(1)=q(2)\geq\ell_o(2).\)
Thus every two-party instance is feasible. The complement need not satisfy a cardinality bound, since that bound defines the quota only.
Use the standard \(\mathsf{NP}\)-completeness of binary-encoded Partition: given positive integers \(a_1,\ldots,a_k\), decide whether some subset sums to half their total.
Construct two supported types, each of mass \(\tfrac12\), and use the integers \(a_t\), sorted nonincreasingly, as seat weights. Write \(A=\sum_t a_t=\omega\). Query any oracle solving the stated search problem, and accept exactly when its output satisfies \(2r(1)=A\).
If Partition is a yes-instance, one side of an equal-sum partition has at most \(\lfloor k/2\rfloor\) elements. That side witnesses
\(\displaystyle \ell_o(1)=\ell_o(2)=A/2,\)
because both quota maximizations are identical and bounded above by \(A/2\). Every valid oracle output therefore gives both parties weight \(A/2\).
Conversely, an output satisfying \(2r(1)=A\) itself supplies an equal-sum partition. Hence the test cannot accept a no-instance. Every query is feasible by the preceding proof.
Let \(N\) be the Partition input length and \(L\) the constructed input length. The construction has \(m=\tau=2\), preserves \(k\), and satisfies \(L=O(N)\): weights are merely reordered, and both masses have constant-size binary encodings.
Sorting takes \(O(k\log(k+1)L)\) bit operations; summing and checking the output takes \(O(kL)\). If the search solver runs in time \(T(m,\tau,k,L)\), the reduction runs in
\(\displaystyle O(k\log(k+1)L)+T(2,2,k,L).\)
It uses one oracle call and works for every valid oracle output. Consequently, a solver polynomial in \(m,\tau,k,L\) would imply \(\mathsf{P}=\mathsf{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes \(\mathsf{NP}\)-hardness under polynomial-time Turing reductions, already for \(m=\tau=2\) with equal masses. No major or minor issues were found.
Each constructed instance has exactly two supported types, with positive binary-rational masses \(\mu_1=\mu_2=\tfrac12\). Their masses sum to \(1\). The positive integer Partition inputs become positive integer seat weights, sorted into the required nonincreasing order. The construction imposes no cardinality restriction on assignments.
The invoked source problem is stated precisely: Partition on binary-encoded positive integers asks whether an indexed subset sums to half the total. Its standard \(\mathsf{NP}\)-completeness applies to this domain. Repeated weights cause no ambiguity because subsets refer to seat indices.
The maximization defining \(\ell_o(1)\) has a finite, nonempty candidate family, since it includes the empty subset. Consequently, an attaining subset \(S\) exists.
Giving \(S\) to party \(1\) and every remaining seat to party \(2\) yields
\[
r(1)=\ell_o(1),\qquad
r(2)=\omega-\ell_o(1)\geq\omega-q(1)=q(2)\geq\ell_o(2).
\]
Each step follows from the definitions: \(\ell_o(1)\leq q(1)\), the masses sum to \(1\), and \(\ell_o(2)\leq q(2)\).
The complement’s cardinality is irrelevant under the task’s assignment rules. This establishes feasibility of every oracle query, including queries arising from no-instances of Partition.
If an equal-sum partition exists, its two sides have cardinalities summing to \(k\). Therefore, at least one side has cardinality at most \(\lfloor k/2\rfloor\). Its weight is \(A/2\), so it is admissible in both quota maximizations: the masses, cardinality bounds, and weight bounds are identical for the two parties.
Thus the asserted equality \(\ell_o(1)=\ell_o(2)=A/2\) follows. Every valid oracle output gives each party weight at least \(A/2\). Since their weights sum to \(A\), both weights must equal \(A/2\). The acceptance test therefore accepts every yes-instance, regardless of which valid assignment the oracle returns.
An assignment satisfying \(2r(1)=A\) identifies a subset of the input weights summing to \(A/2\). Its complement also sums to \(A/2\), so the original Partition instance is a yes-instance.
Consequently, no valid oracle output can cause false acceptance. If \(A\) is odd, the equality cannot hold because \(r(1)\) is an integer. The case \(k=1\) is also covered: both quota cardinality bounds are zero, feasibility still holds, and the positive single weight cannot be partitioned equally.
Sorting preserves the weight encodings, and the additional party and mass information has constant size. Hence \(L=O(N)\). All intermediate sums have \(O(L)\) bits. The stated bounds \(O(k\log(k+1)L)\) for sorting and \(O(kL)\) for summation and checking are valid conservative bit-operation bounds.
There is exactly one oracle call, on parameters \(m=\tau=2\), with unchanged \(k\) and polynomial input length. The displayed total running time therefore establishes the claimed polynomial-time Turing reduction.
[Proposition 3 and its appendix proof](https://arxiv.org/html/2405.18102v2#S8.SS1) use two parties with equal votes and a Partition reduction. The prover’s explicit rational-mass construction matches this restriction and independently supplies the necessary verification.
No additional clarification or repair is needed. The proof establishes hardness; its exclusion of a polynomial-time solver is correctly conditional on \(\mathsf{P}\ne\mathsf{NP}\).
⟨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.