Answer: \(\mathrm{NP}\)-hard for Hamilton and every fixed divisor method specified in the question, even when \(s_j=1\) in every district.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor R being a divisor sequence method or LRM, R- THRESHOLD-MAB is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given fixed districts and parties, district seat counts, an apportionment method \(R\), a target party \(P^\star\), a seat target \(\ell\), rational masses \(\mu_{j,i}\) on district–party voter types with \(\sum_{j,i}\mu_{j,i}=1\), a rational global eligibility threshold \(\theta\), and a rational mass budget \(\beta\), is there a within-district transfer \(x_{j,i,k}\geq 0\) with \(\sum_k x_{j,i,k}\leq\mu_{j,i}\) and \(\sum_{j,i,k}x_{j,i,k}\leq\beta\) such that \(P^\star\) receives at least \(\ell\) seats? After transfer, party \(i\) is eligible in every district if its total mass is at least \(\theta\); its support in district \(j\) is then its post-transfer mass there, or zero if it is ineligible. Apply \(R\) separately in each district using the paper’s tie-breaking rule.
There are \(q\geq1\) districts and \(m\geq1\) parties \(P_1,\ldots,P_m\), all running in every district. Districts and parties are part of the input and cannot be changed. Each district has an integer seat count \(s_j\geq1\), encoded in unary; write \(s=\sum_j s_j\). The input also specifies \(P^\star\), an integer \(1\leq\ell\leq s\), and nonnegative binary rationals \(\theta\) and \(\beta\).
A society is given by its support: the list of the \(\tau\) district–party types with positive mass, each mass a binary rational. Omitted masses are zero, and \(\sum_{j,i}\mu_{j,i}=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total input bit length.
For each fixed apportionment method \(R\), consider either Hamilton's largest-remainder method or a divisor method with a fixed strictly increasing sequence of positive integers \(d_1,d_2,\ldots\), polynomially bounded and computable in the index. All ties favor the party with smaller index. Seats remain indivisible.
A transfer consists of real masses \(x_{j,i,k}\geq0\), with \(x_{j,i,i}=0\), \(\sum_k x_{j,i,k}\leq\mu_{j,i}\), and \(\sum_{j,i,k}x_{j,i,k}\leq\beta\). Transfers may go to any party in the same district, and their cost is the transferred mass; there are no district budgets.
The resulting masses are \(\nu_{j,i}=\mu_{j,i}-\sum_k x_{j,i,k}+\sum_k x_{j,k,i}\). Party \(P_i\) is globally eligible exactly when \(\sum_j\nu_{j,i}\geq\theta\); its district support is \(a_{j,i}=\nu_{j,i}\) if eligible and zero otherwise.
Apply \(R\) separately to each district's support vector. For a divisor method, allocate its \(s_j\) seats using the largest quotients \(a_{j,i}/d_t\), \(1\leq t\leq s_j\). Hamilton uses total eligible district support as its denominator. Require \(\sum_i a_{j,i}>0\) in every district; outcomes with undefined district allocations are inadmissible.
For each fixed method \(R\) above, is deciding whether an admissible transfer gives \(P^\star\) at least \(\ell\) seats overall in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L,q,s\).
With indivisible unit-cost voters and a global threshold, this decision problem is \(\mathrm{NP}\)-complete for these methods, even with one seat per district and every party running everywhere ([Kaczmarek, Rothe, and Seeger](https://doi.org/10.3233/FAIA251236)). Without a threshold, discrete multidistrict seat-target bribery restricted to transfers to the target party is polynomial-time solvable ([Bredereck et al.](https://martin.lackner.xyz/publications/ijcai20-apportionment.pdf)).
No result settling this exact divisible-mass problem was located.
For Hamilton and every fixed divisor method in the question, the decision problem is \(\mathrm{NP}\)-hard, even when every district has exactly one seat.
The reduction below uses divisible masses throughout. Its essential feature is that making a party ineligible has a positive minimum cost, while district margins prevent direct transfers from changing winners within the available budget.
For either method, a district with one seat and positive total eligible support awards that seat to the eligible party with greatest district mass, with ties resolved by party index.
For a divisor method, all first quotients have the same denominator \(d_1\), so their ordering is the ordering of district supports.
For Hamilton, the quotas are \(a_i/\sum_h a_h\). If some party has quota \(1\), it receives the seat. Otherwise all lower quotas are zero, and the largest remainder is precisely the largest support divided by the common denominator.
Consequently, one construction suffices for all the methods under consideration.
Let \(G=(V,E)\) be a simple graph, with \(n=|V|\) and \(e=|E|\), and let \(k\) be the requested clique size. We may assume
\[ 2\leq k\leq n,\qquad e\geq \binom{k}{2}. \]
Instances outside these conditions are immediately decidable and can be mapped to fixed yes- or no-instances of the transfer problem.
Define
\[ h=\left\lceil\log_2(100(n+1))\right\rceil,\qquad \varepsilon=2^{-h},\qquad B=\left(k+\frac12\right)\varepsilon. \]
These choices imply \(B<1/100\).
We first describe unnormalized masses. There are the target party \(P^\star\), one vertex party \(P_v\) for each \(v\in V\), and a guard party \(H\). Give the target index \(1\); the remaining indices can be assigned arbitrarily. All parties run in every district.
Every district has one seat.
Edge districts. For each edge \(\{u,v\}\in E\), create a district with masses
\[ P_u:1,\qquad P_v:1,\qquad P^\star:\frac12. \]
All other masses in that district are zero.
Vertex padding districts. For each vertex \(v\), put
\[ C_v=n+\varepsilon-\deg_G(v). \]
Create a district with masses
\[ P_v:C_v,\qquad H:C_v+1. \]
Because \(\deg_G(v)\leq n-1\), we have \(C_v\geq1+\varepsilon\).
Reservoir district. Create one further district with masses
\[ P^\star:n,\qquad H:n+1. \]
Let \(W\) be the total mass described so far. Choose \(Z\) to be the least power of two satisfying \(Z\geq W\), and add \(Z-W\) to the guard’s reservoir mass. The total unnormalized mass is now \(Z\).
Divide every mass by \(Z\), and set
\[ \theta=\frac nZ,\qquad \beta=\frac BZ,\qquad \ell=\binom{k}{2}. \]
The resulting instance has
\[ m=n+2,\qquad q=e+n+1,\qquad s=q,\qquad \tau=3e+2n+2. \]
In particular, \(\ell\leq e\leq s\). Every input mass is positive on its listed support, and all masses sum to \(1\). The normalization even makes all input masses, the threshold, and the budget dyadic rationals.
For the proof, multiply any transfer in the normalized instance by \(Z\). We can therefore work with the unnormalized masses, eligibility threshold \(n\), and transfer budget \(B\).
For any transfer of total cost at most \(B\), each individual district–party mass changes by at most \(B\): its increase is bounded by total incoming mass, and its decrease by total outgoing mass.
Initially, the guard’s reservoir mass alone is at least \(n+1\). Its global mass can decrease by at most \(B<1\). Thus its global mass always remains strictly greater than \(n\).
In the padding district for \(v\), the target initially has zero mass, so its final support is at most \(B\). The eligible guard has final support at least
\[ C_v+1-B>B. \]
Thus the target cannot win that district.
In the reservoir district, the target’s final support is at most \(n+B\), whereas the eligible guard’s support is at least \(n+1-B\). Since \(2B<1\), the guard strictly defeats the target there.
Hence every target seat must come from an edge district.
Consider the district for \(\{u,v\}\). If \(P_u\) remains eligible, its support is at least \(1-B\). The target’s support is at most \(1/2+B\), whether or not the target is eligible. Since
\[ 1-B>\frac12+B, \]
the target cannot win. The same argument applies to \(P_v\).
Therefore, a target victory in this district requires both endpoint parties to be ineligible.
The initial global mass of each vertex party is exactly
\[ \deg_G(v)+C_v=n+\varepsilon. \]
To become ineligible, its final global mass must be strictly below \(n\). Its total outgoing mass must consequently exceed \(\varepsilon\), even if it also receives incoming transfers.
If \(r\) vertex parties become ineligible, their outgoing transfers are disjoint terms in the total transfer cost. Therefore, when \(r>0\),
\[ r\varepsilon<B=\left(k+\frac12\right)\varepsilon. \]
Since \(r\) is an integer, \(r\leq k\). This also holds when \(r=0\).
Suppose an admissible transfer gives the target at least \(\binom{k}{2}\) seats. Let \(U\subseteq V\) consist of the vertices whose parties become ineligible.
By the preceding arguments, \(|U|\leq k\), and every target seat corresponds to an edge induced by \(U\). Thus
\[ \binom{k}{2}\leq |E(G[U])| \leq\binom{|U|}{2}\leq\binom{k}{2}. \]
All inequalities must be equalities. Because \(k\geq2\), equality forces \(|U|=k\). Moreover, \(G[U]\) has every possible edge, so \(U\) is a \(k\)-clique.
Conversely, suppose \(K\subseteq V\) is a clique of size \(k\).
For each \(v\in K\), transfer
\[ \varepsilon+\frac{\varepsilon}{4k} \]
from \(P_v\) to the target in \(v\)’s padding district. This is available because \(C_v\geq1+\varepsilon\). The total transfer cost is
\[ k\varepsilon+\frac{\varepsilon}{4} < k\varepsilon+\frac{\varepsilon}{2} =B. \]
Each selected vertex party now has global mass
\[ n+\varepsilon-\left(\varepsilon+\frac{\varepsilon}{4k}\right) =n-\frac{\varepsilon}{4k}<n, \]
so it is ineligible. The target remains eligible because its initial global mass is at least \(n\), and it only receives mass.
Edge districts are unchanged by these transfers. In every edge district whose endpoints belong to \(K\), both vertex parties are ineligible, and the target is the only party with positive eligible support. It therefore wins all \(\binom{k}{2}\) such districts.
Every district remains admissible: edge districts have positive eligible target support, and all padding districts and the reservoir have positive eligible guard support.
This proves the equivalence and establishes \(\mathrm{NP}\)-hardness for every specified method.
The constructed weights have \(O(\log(n+1))\) bits. Indeed, \(W=O(n^2)\), hence \(Z=O(n^2)\), and the dyadic denominators also have \(O(\log(n+1))\) bits. The reduction takes
\[ O\!\left((n+e)\operatorname{poly}(\log(n+1))\right) \]
bit operations and produces an instance of total length
\[ L=O((n+e)\log(n+1)). \]
Thus, unless \(\mathrm{P}=\mathrm{NP}\), there is no algorithm with running time polynomial in \(m,\tau,L,q,s\).
For completeness, the exact problem has the following general, finite upper bound:
\[ 2^m[2(s+1)]^{qm}\operatorname{poly}(m,\tau,L,q,s). \]
Here is a justification that handles real transfers, strict eligibility conditions, and tie-breaking.
First, district mass conservation and transfer cost can be expressed using final masses \(\nu_{j,i}\). The minimum cost of realizing these masses is
\[ D(\nu)=\sum_{j,i}\max\{\nu_{j,i}-\mu_{j,i},0\}, \]
provided every district preserves its total mass. Necessity follows because every positive increase requires incoming transfers. Sufficiency follows by matching, within each district, parties with decreases to parties with increases. Conservation makes their total decreases and increases equal, and this matching costs exactly \(D(\nu)\).
Introduce variables \(z_{j,i}\geq0\), with
\[ z_{j,i}\geq\nu_{j,i}-\mu_{j,i}, \qquad \sum_{j,i}z_{j,i}\leq\beta. \]
Enumerate the globally eligible set, then enumerate each district’s allocation data:
\[
b_{j,i}T_j\leq s_j a_{j,i}<(b_{j,i}+1)T_j.
\]
Compare the linear remainder expressions \(s_j a_{j,i}-b_{j,i}T_j\) for selected and unselected remainder recipients, with strictness determined by party indices.
Also enforce the guessed global eligibility inequalities, \(T_j>0\), district conservation, the budget, and the target seat requirement. Each guess yields a rational linear system with \(O(qm)\) variables and \(O(qm^2)\) constraints.
Strict feasibility is decidable by introducing a common slack \(\delta\): replace every strict inequality \(f>0\) by \(f\geq\delta\), impose \(0\leq\delta\leq1\), and maximize \(\delta\). The original system is feasible exactly when the optimum is positive. This equivalence holds because there are finitely many strict inequalities. Rational linear programming then takes polynomial time in the stated parameters.
There are at most \(2^m\) eligibility guesses and at most \([2(s+1)]^{qm}\) allocation guesses, proving the upper bound.
⟨structured verdict parsed — rendered above⟩
The hardness reduction is correct and settles the main question for both Hamilton and every specified divisor method. It uses divisible transfers and establishes hardness even with one seat per district. The supplementary upper-bound algorithm needs a few explicit constraints and a clarification about divisor computation.
There are no major issues in the reduction.
The claimed equivalence between the methods is correct.
For a divisor method, the only candidate quotient for each party is its support divided by the common positive denominator \(d_1\). Thus the greatest support wins.
For Hamilton, positive total eligible support makes the denominator well-defined. Either one quota equals \(1\), or every lower quota is zero and the largest fractional remainder determines the winner. In both cases, the party with greatest eligible support wins, with the specified index tie-breaking.
The restrictions \(2\leq k\leq n\) and \(e\geq\binom{k}{2}\) discard only immediately decidable CLIQUE instances. Mapping these cases to fixed instances is routine.
The numerical bounds are valid. The definition of \(h\) gives
\(\varepsilon\leq 1/[100(n+1)]\), so
\(B\leq(n+1/2)/[100(n+1)]<1/100\).
Each padding mass satisfies
\(C_v=n+\varepsilon-\deg_G(v)\geq1+\varepsilon>0\).
The normalization is valid: \(Z-W\geq0\), and adding this quantity to the guard’s existing positive reservoir mass introduces no additional support type. Dividing by \(Z\) produces total mass \(1\). The counts
\(m=n+2\), \(q=s=e+n+1\), and \(\tau=3e+2n+2\) are correct. Also,
\(1\leq\ell=\binom{k}{2}\leq e\leq s\).
Scaling transfers by \(Z\) preserves all transfer constraints, eligibility comparisons, and district outcomes.
Every individual mass changes by at most \(B\), since its incoming and outgoing transfers are each bounded by the total transfer cost.
The guard remains eligible: its reservoir mass alone starts at least \(n+1\), and its global loss is at most \(B<1\).
The target cannot win padding districts because its support is at most \(B\), while the eligible guard’s support is at least \(C_v+1-B>B\). The reservoir comparison is also correct:
\(n+1-B>n+B\), since \(2B<1\).
In an edge district, any eligible endpoint has support at least \(1-B\), exceeding the target’s maximum possible support \(1/2+B\). Thus a target victory requires both endpoints to become ineligible. All these comparisons are strict, so tie-breaking introduces no exception.
Each vertex party initially has global mass exactly \(n+\varepsilon\). Ineligibility requires a net loss strictly greater than \(\varepsilon\), hence outgoing mass strictly greater than \(\varepsilon\). Transfers outgoing from different vertex parties are distinct cost terms, including transfers between those parties. Consequently, \(r\varepsilon<B=(k+1/2)\varepsilon\) for \(r>0\), which implies \(r\leq k\).
This direction is rigorous.
Every target seat corresponds to an edge induced by the set \(U\) of disqualified vertex parties, and \(|U|\leq k\). Therefore
\(\binom{k}{2}\leq |E(G[U])|\leq\binom{|U|}{2}\leq\binom{k}{2}\).
Equality forces \(|U|=k\), including the boundary case \(k=2\), and forces every pair of vertices in \(U\) to be adjacent.
The argument does not assume that every edge induced by \(U\) necessarily becomes a target seat; it uses only the necessary condition, which suffices.
The proposed transfer amount
\(\varepsilon+\varepsilon/(4k)\) is available in every selected padding district. Its total cost is
\(k\varepsilon+\varepsilon/4<B\).
Each selected vertex party ends strictly below the eligibility threshold. Every unselected vertex party retains its initial mass. The target starts with global mass at least \(n\) and only receives transfers, so it remains eligible.
Edge districts are unchanged. In every clique-edge district, the target is the only party with positive eligible support and therefore wins. All edge districts remain admissible through the target; padding and reservoir districts remain admissible through the guard.
This establishes the required equivalence.
The encoding estimates are correct.
There are \(O(n+e)\) support entries, each with \(O(\log(n+1))\) bits for its mass and identifiers. Also \(W=O(n^2)\) and \(Z=O(n^2)\). The dyadic denominators have \(O(\log(n+1))\) bits.
The reduction therefore has the stated polynomial running time and output size. Its hardness proof uses only \(d_1\), and hence does not require computing a long prefix of the divisor sequence.
The conclusion excluding a running time polynomial in \(m,\tau,L,q,s\), unless \(\mathrm{P}=\mathrm{NP}\), follows.
The underlying approach is sound:
The following omissions require minor clarification.
The linear-system description does not explicitly impose \(\nu_{j,i}\geq0\). This is essential to interpreting its variables as realizable final masses and to the sufficiency of the transfer-cost formula. Add these inequalities. Nonnegativity is already implicit in the phrase “final masses,” so this is an expositional omission.
The write-up should explicitly require, for divisor guesses, integer counts \(0\leq b_{j,i}\leq s_j\) with \(\sum_i b_{j,i}=s_j\). For Hamilton guesses, require integer lower quotas in the stated range, binary remainder indicators, and \(\sum_i(b_{j,i}+r_{j,i})=s_j\). These are implicit in “allocation data,” but the displayed inequalities alone do not impose them.
Specify that a last selected quotient exists only when \(b_{j,i}>0\), and a first unselected candidate exists only when \(b_{j,i}<s_j\), within the question’s finite candidate list. This makes the comparison rule defined for all guesses.
Explicitly state whether “polynomially bounded and computable” means polynomial-time computable. The claimed polynomial factor uses that interpretation. If the task permits merely computable sequences, the supplementary runtime must additionally account for generating the required divisors. This clarification does not affect the hardness classification.
⟨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.