Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k_{\max}\); not \(\mathrm{FPT}\) unless \(\mathrm{FPT}=\mathrm{W}[1]\).
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDetermining if there exists a successful manipulation for \(a_1\) is W[1]-hard w.r.t. parameter \(\mu^{\mathtt{max}}\).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given item categories \(I\) with rational supplies \(q_i\), a finite set of types \(T\) with masses \(\mu_t>0\), their strict rankings and turn schedules, and a positive-mass manipulator type \(t^\star\) with a true ranking and additive utility \(u\), does there exist a common reported ranking for \(t^\star\) that gives its members greater average utility than truthful reporting? At each scheduled occurrence of a type, its mass takes one unit per member from the remaining supplies, greedily by its ranking.
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. Require \(\sum_{t\in T}\mu_t=1\).
There are \(m\geq1\) divisible item categories with positive binary-rational supplies \(q_i\). Each type has a strict total ranking of the categories. An explicitly listed sequence \(\pi\in T^h\) specifies the turns; require \(\sum_iq_i=\sum_{s=1}^h\mu_{\pi(s)}\).
At turn \(s\), type \(t=\pi(s)\) receives aggregate quantity \(\mu_t\), exhausting its highest-ranked remaining category before continuing down its ranking until that quantity is filled. A category may be consumed at multiple turns.
A designated type \(t^\star\), occurring at least once, has positive binary-rational per-unit utilities \(u_i\), strictly consistent with its true ranking. All other types report truthfully; the manipulator submits one strict total ranking used by all its members at every turn.
Let \(x_i(r)\) be the total quantity of category \(i\) allocated to \(t^\star\) under report \(r\), and define average utility \(U(r)=\mu_{t^\star}^{-1}\sum_i u_i x_i(r)\). The decision problem asks whether some report \(r\) satisfies \(U(r)>U(r_{\mathrm{true}})\).
Put \(k_{\max}=\max_{t\in T}|\{s:\pi(s)=t\}|\), and let \(L\) be the total binary input length. State running times in \(m,\tau,h,L\) and \(k_{\max}\).
Is this decision problem in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard; if it is \(\mathrm{NP}\)-hard, is it nevertheless \(\mathrm{FPT}\) parameterized by \(k_{\max}\)?
For indivisible items and individual-agent turns, existence of a report improving on truth is \(\mathrm{NP}\)-complete ([Aziz et al.](https://www.cse.unsw.edu.au/~haziz/seqbr.pdf)) and \(\mathrm{W}[1]\)-hard parameterized by the maximum number of turns of any agent ([Flammini and Gilbert](https://ecai2020.eu/papers/719_paper.pdf)).
No result settling this exact mass protocol was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[1]\)-hard parameterized by \(k_{\max}\). Consequently, it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\), and it is not \(\mathrm{FPT}\) in \(k_{\max}\) unless \(\mathrm{FPT}=\mathrm{W}[1]\).
The key point is that the mass protocol contains an exact, scaled copy of indivisible sequential allocation. Normalization and the requirement that the support consist of distinct types can both be accommodated while preserving \(k_{\max}\).
A certificate is a strict total report \(r\), represented by a permutation of the \(m\) categories. We show that its outcome and its improvement over truth can be checked exactly in polynomial time.
Write every supply and mass as a rational with positive denominator, and let \(D\) be the product of these denominators. Its binary length is at most the sum of their binary lengths, hence is \(\mathrm{O}(L)\). Scale all quantities by \(D\). Supplies, turn quantities, residual supplies, and allocations are then integers.
Normalization implies \(\mu_t\leq 1\), and the balance condition gives
\(\displaystyle \sum_i q_i=\sum_{s=1}^{h}\mu_{\pi(s)}\leq h.\)
Thus every scaled quantity arising during simulation is at most \(hD\) and has \(\mathrm{O}(L+\log(h+1))\) bits. Because the sequence is explicitly listed, this is \(\mathrm{O}(L)\).
For each type, maintain a pointer into its ranking. Whenever its pointed-to category is exhausted, advance the pointer. This is valid because exhausted categories never become available again. Each pointer advances at most \(m\) times, giving at most \(\tau m\) advances altogether.
Every positive consumption operation either exhausts a category or completes a turn, or both. Consequently, there are at most \(m+h\) such operations. Each uses an integer comparison and subtraction on \(\mathrm{O}(L)\)-bit integers.
For the utility comparison, let \(E\) be the product of the denominators of the utilities, and put \(v_i=Eu_i\). These are integers of polynomial binary length. Since \(\mu_{t^\star}>0\), improvement is equivalent to
\(\displaystyle \sum_i v_i(Dx_i(r))>\sum_i v_i(Dx_i(r_{\mathrm{true}})).\)
All products and sums in this comparison have \(\mathrm{O}(L)\) bits. Using schoolbook arithmetic, preprocessing, both simulations, and the comparison take
\(\displaystyle \mathrm{O}\bigl((\tau m+h)L^2\bigr)\)
bit operations. Checking that the report is a permutation also fits within this bound.
Therefore the decision problem belongs to \(\mathrm{NP}\).
We use the following two established results for indivisible sequential allocation. In that model, each turn allocates one remaining item according to the agent’s single reported strict ranking; other agents report truthfully, and the manipulator has positive additive utilities strictly consistent with its true ranking.
The second result concerns successful manipulation, defined as strict improvement over truth, rather than merely reaching an externally specified utility threshold.
We now construct a polynomial-time reduction that preserves this decision question and the maximum-turn parameter.
Let an indivisible instance have agents \(a_1,\ldots,a_n\), items \(o_1,\ldots,o_{m_0}\), and a sequence \(\rho\) of length \(m_0\). Let \(a^\star\) be its manipulator, with utilities \(v_o>0\). Write
\(\displaystyle k_0=\max_a|\{s:\rho(s)=a\}|.\)
We may restrict to \(n\geq 2\), since with one agent the final allocation contains every item and is independent of its report. The hardness results therefore remain applicable on this restriction.
The construction below also ensures that all types have distinct true rankings, even if some source agents have identical rankings.
Introduce one marker category \(z_a\) for each source agent \(a\). The category set is
\(\displaystyle O\cup Z,\qquad Z=\{z_{a_1},\ldots,z_{a_n}\}.\)
Set
\(\displaystyle b=\lceil\log_2(2n)\rceil,\qquad c=2^{-b}.\)
Every original category and every marker category has supply \(c\).
For each source agent \(a\), create an original type \(t_a\) of mass \(c\), and a collector type \(d_a\) of mass \(c\). If
\(\displaystyle \delta=1-2nc\)
is positive, add one further type \(p\) of mass \(\delta\), which receives no turns. The task requires only the designated type to occur, so this additional support type is permitted.
All masses are positive dyadic rationals, and their sum is exactly \(1\).
For each \(a\), the true ranking of \(t_a\) lists:
Collector \(d_a\) ranks \(z_a\) first, then all original categories in a fixed order, then the other markers.
When \(p\) is present, give it a ranking beginning with \(z_{a_1},z_{a_2}\), followed by the original categories and the remaining markers.
These true rankings are pairwise distinct. Original types are distinguished by their marker suffixes; collectors have distinct first categories; original types rank an original category first, whereas collectors rank a marker first. The optional type \(p\) differs from \(d_{a_1}\) in its second category and from every other collector in its first category.
The sequence is
\(\displaystyle \pi=(d_{a_1},\ldots,d_{a_n},t_{\rho(1)},\ldots,t_{\rho(m_0)}).\)
Thus
\(\displaystyle m=m_0+n,\qquad h=m_0+n,\qquad \tau\in\{2n,2n+1\}.\)
Every occurring type has mass \(c\), so the required balance holds:
\(\displaystyle \sum_iq_i=(m_0+n)c=\sum_{s=1}^{h}\mu_{\pi(s)}.\)
The designated type is \(t^\star=t_{a^\star}\).
For each original category \(o\), set \(u_o=v_o\). Let
\(\displaystyle v_{\min}=\min_{o\in O}v_o>0.\)
If the designated type’s marker suffix is \(z_{\sigma(1)},\ldots,z_{\sigma(n)}\), set
\(\displaystyle u_{z_{\sigma(j)}}=2^{-j}v_{\min}\qquad(1\leq j\leq n).\)
These values are positive, strictly decreasing along that suffix, and smaller than every original-item utility. Hence all utilities are strictly consistent with the designated type’s true ranking.
Their binary descriptions have polynomial length. The complete construction, including all explicitly listed rankings, takes polynomial time in the source input length.
First consider the collector prefix. At collector \(d_a\)’s turn, its own marker \(z_a\) still has supply \(c\): earlier collectors have consumed only their own distinct markers. Its turn quantity is \(c\), so it consumes precisely \(z_a\).
Consequently, after the prefix:
Now fix any report of \(t^\star\). Delete its markers to obtain a strict ranking \(r_O\) of the original items.
We prove by induction along the remaining sequence that its mass allocations reproduce the source allocation under \(r_O\).
Before its first turn, every original category has remaining supply either \(0\) or \(c\), in correspondence with whether the source item has already been allocated. Suppose this correspondence holds before a turn. The acting type chooses the same highest-ranked remaining original item as its corresponding source agent. Its turn quantity and that category’s remaining supply are both \(c\), so it consumes the entire category and completes its turn. The correspondence therefore holds after the turn.
This proves the induction. In particular, if \(S(r_O)\) is the manipulator’s source bundle, then
\(\displaystyle x_o(r)=c\,\mathbf{1}_{\{o\in S(r_O)\}},\qquad x_z(r)=0\quad(z\in Z).\)
Because \(\mu_{t^\star}=c\),
\(\displaystyle U(r)=c^{-1}\sum_{o\in O}v_o\,c\,\mathbf{1}_{\{o\in S(r_O)\}}=\sum_{o\in S(r_O)}v_o.\)
The same equality holds for the truthful reports.
Conversely, every source report extends to a report over all categories by inserting the exhausted markers anywhere. Thus
\(\displaystyle \exists r:\ U(r)>U(r_{\mathrm{true}})\)
holds exactly when the source indivisible instance admits a report improving on truth.
The reduction is polynomial, so the indivisible \(\mathrm{NP}\)-hardness result transfers. Together with Section 1, this proves \(\mathrm{NP}\)-completeness.
For the parameter, every original type has exactly its source agent’s turn count, every collector has one turn, and the optional normalization type has none. Hence
\(\displaystyle k_{\max}=\max\{k_0,1\}=k_0.\)
The reduction therefore also transfers \(\mathrm{W}[1]\)-hardness in the maximum-turn parameter.
In particular, an algorithm with running time
\(\displaystyle f(k_{\max})\operatorname{poly}(m,\tau,h,L)\)
would give an \(\mathrm{FPT}\) algorithm for the cited \(\mathrm{W}[1]\)-hard indivisible problem. Such an algorithm therefore cannot exist unless \(\mathrm{FPT}=\mathrm{W}[1]\).
An unconditional exhaustive algorithm enumerates all strict reports and uses the verifier above. Its running time is
\(\displaystyle \mathrm{O}\bigl(m!\,(\tau m+h)L^2\bigr).\)
Thus the established classification is complete in the usual complexity-theoretic sense: \(\mathrm{NP}\)-complete, and \(\mathrm{W}[1]\)-hard in \(k_{\max}\), with the corresponding standard conditional exclusions of polynomial time and fixed-parameter tractability.
⟨structured verdict parsed — rendered above⟩
The proof resolves the assigned problem. The normalization gadget, allocation correspondence, exact verifier, and parameter preservation are correct. The cited theorems concern the required strict-improvement decision question and the required maximum-turn parameter. I found no major or minor issues requiring repair.
The established conclusion is \(\mathrm{NP}\)-completeness and \(\mathrm{W}[1]\)-hardness parameterized by \(k_{\max}\), with the stated conditional exclusions of polynomial time and fixed-parameter tractability.
A permutation of the \(m\) categories specifies precisely the allowed manipulation: one strict ranking used at every designated-type turn. Its encoding has polynomial length.
The denominator product \(D\) is a valid common denominator for all supplies and masses. Its binary length is bounded by the sum of the input denominator lengths, hence by \(\mathrm{O}(L)\). Scaling by \(D\) makes every quantity used in allocation integral.
The bound
\[
\sum_i q_i=\sum_{s=1}^{h}\mu_{\pi(s)}\leq h
\]
follows from normalization and positivity, which give \(\mu_t\leq1\). Thus residual supplies, allocations, and turn quantities are bounded by \(hD\). Since the turn sequence is explicit, the claimed \(\mathrm{O}(L)\) bit bound is valid.
The ranking-pointer implementation is valid. A pointer skips only exhausted categories, and no exhausted category becomes available again. Across all types, there are at most \(\tau m\) pointer advances.
Every positive consumption operation exhausts a category, completes a turn, or does both. Charging each operation to one such event gives at most \(m+h\) operations.
The balance condition also ensures that simulation cannot run out of supply before filling a turn: remaining total supply equals the total quantity required by all remaining turns.
Multiplying utilities by their denominator product \(E\) produces integers \(v_i\) of polynomial binary length. The comparison in the output is equivalent to strict improvement because the omitted factors \(E\), \(D\), and \(\mu_{t^\star}\) are positive.
Products and sums retain \(\mathrm{O}(L)\) bits. The stated schoolbook-arithmetic bound
\[
\mathrm{O}\bigl((\tau m+h)L^2\bigr)
\]
covers preprocessing, both simulations, permutation checking, and utility comparison. Therefore membership in \(\mathrm{NP}\) is established.
The theorem citations match the claims being transferred:
Thus neither citation is being substituted for a different threshold or optimization problem. The source parameter also matches the one used in the reduction.
The restriction to at least two source agents is legitimate: the one-agent case allocates every item to that agent regardless of its report.
For \(b=\lceil\log_2(2n)\rceil\) and \(c=2^{-b}\), one has \(2nc\leq1\). Consequently, the optional residual mass \(\delta=1-2nc\) is nonnegative.
When \(\delta=0\), the residual type is omitted. When \(\delta>0\), it is included with positive mass. In both cases every listed support type has positive mass and the masses sum exactly to one.
A support type receiving no turns is permitted by the task. Only the designated type must occur, and the source hard instances have manipulator turns.
The construction’s distinctness argument is correct:
The last comparison uses \(n\geq2\) and the nonempty original-item set, both satisfied by the source hard instances.
There are \(m_0+n\) categories and \(m_0+n\) turns. Every category has supply \(c\), and every occurring type has mass \(c\). The required supply-turn balance therefore holds exactly.
The explicitly listed rankings have polynomial total size. The normalization quantities have polynomial binary descriptions.
Marker utilities are positive, strictly decreasing along the designated type’s marker suffix, and below every original utility. They therefore satisfy the task’s strict consistency requirement. Multiplication by \(2^{-j}\), for \(j\leq n\), increases encoding length only polynomially.
Each collector encounters its own marker untouched: earlier collectors consume exactly their own distinct markers. Its mass and its marker supply both equal \(c\), so its turn consumes that marker completely.
The prefix exhausts every marker, consumes no original category, and allocates nothing to the designated type. This remains true for every manipulator report because the manipulator does not act during the prefix.
Deleting markers from any manipulator report produces a strict ranking of the original categories.
After the prefix, each original category has supply \(c\). The induction preserves remaining supplies in \(\{0,c\}\): at each source turn, the corresponding mass-protocol type chooses the same remaining original category and consumes exactly \(c\).
This verifies the claimed correspondence for every report, including reports placing markers above original categories. All markers are already exhausted.
The allocation identities
\[
x_o(r)=c\,\mathbf{1}_{\{o\in S(r_O)\}},\qquad x_z(r)=0
\]
follow directly from the induction.
Dividing aggregate utility by the designated mass \(c\) gives exactly the source bundle utility. The equality holds for truthful reports as well.
Every source report extends to a target report, and every target report restricts to a source report. Consequently, the reduction preserves both yes-instances and no-instances of strict improvement.
Original types retain their source turn counts; collectors receive one turn; the optional type receives none. Since \(k_0\geq1\),
\[
k_{\max}=\max\{k_0,1\}=k_0.
\]
The polynomial reduction is therefore also a parameter-preserving reduction. Both hardness conclusions follow from the verified source theorems.
The exhaustive runtime
\[
\mathrm{O}\bigl(m!\,(\tau m+h)L^2\bigr)
\]
correctly enumerates all reports and applies the verifier. The polynomial-time and \(\mathrm{FPT}\) exclusions are appropriately conditional.
No corrective clarification or additional lemma is required.
⟨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.