Complexity of Manipulating Sequential Allocation (d4-conf-aaai-2017-0729)

Given finite role types \(A\), item types \(O\), rational role masses \(\mu_a\), item supplies \(\beta_o\), an ordered template of blocks \((a_q,\lambda_q)\), fixed rankings for nonstrategic roles, a common additive utility \(u_h\) for strategic cohort \(h\), and threshold \(\theta\), does there exist a strict report \(\widehat{\succ}_h\) such that sequential highest-ranked allocation of block mass, with marginal blocks split across item types, gives \(h\) average utility at least \(\theta\)?

A society is given by its support: a nonempty list \(A\) of \(\tau\) role types with positive binary-rational masses \(\mu_a\), normalized by \(\sum_{a\in A}\mu_a=1\). Here \(\tau=|A|\) is the support size, not the number of possible preference types. There are \(m\geq1\) divisible item types \(O\), each with positive binary-rational supply \(\beta_o\).
The input includes a strategic role \(h\in A\), complete strict rankings over \(O\) for every other role, pairwise distinct positive binary-rational utility densities \(u_h(o)\), and a binary-rational threshold \(\theta\). Utilities are additive; the truthful ranking of \(h\) is induced by \(u_h\).
An explicitly listed ordered template \((a_q,\lambda_q)_{q=1}^{Q}\) specifies \(a_q\in A\) and binary-rational block masses \(0<\lambda_q\leq\mu_{a_q}\), with \(\sum_{q=1}^{Q}\lambda_q=\sum_{o\in O}\beta_o\). Roles may recur, and their cumulative block mass need not equal their population mass.
In block \(q\), allocate exactly \(\lambda_q\) item mass to role \(a_q\): take as much as possible from its highest-ranked item type with remaining supply, then continue down its ranking until the block is filled. Every block of \(h\) uses the same chosen complete strict report \(\widehat{\succ}_h\); all other reports and the template are fixed.
Let \(x_{h,o}\) be the total mass of item type \(o\) allocated to \(h\). Its average utility is \(\mu_h^{-1}\sum_{o\in O}u_h(o)x_{h,o}\). Let \(L\) be the total input bit length; state running times in \(m,\tau,Q,L\).

Is deciding whether some report \(\widehat{\succ}_h\) gives \(\mu_h^{-1}\sum_{o\in O}u_h(o)x_{h,o}\geq\theta\) solvable in polynomial time in \(m,\tau,Q,L\), or is it NP-hard?

For indivisible items, the utility-threshold problem with one manipulating agent and an unrestricted number of other agents is NP-complete ([Aziz et al.](https://ojs.aaai.org/index.php/AAAI/article/download/10586/10445)); it is polynomial-time solvable for each fixed number of agents ([Xiao and Ling](https://arxiv.org/abs/1909.06747)).
No result settling this exact distribution-and-block problem was identified in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-complete when the support size \(\tau\) is part of the input. Hardness holds even when \(Q=m\) and every item supply and every block mass equals the same dyadic rational.

The proof embeds indivisible sequential allocation exactly: although the items are divisible, the constructed instances never split an item type.

1. The source problem

We use the following established result: given indivisible items, fixed complete strict rankings of the other agents, an explicitly specified picking sequence, positive integer utilities for one manipulator, and an integer threshold \(T\), deciding whether a single complete strict report attains utility at least \(T\) is \(\mathrm{NP}\)-complete. The utilities are consistent with a strict truthful ranking and hence pairwise distinct. This is the decision problem proved hard in [Aziz et al., Theorem 2](https://ojs.aaai.org/index.php/AAAI/article/download/10586/10445).

Write the agents as \(\{1,\ldots,n\}\), with manipulator \(1\), and the items as \(O\), where \(|O|=m\). Denote the utilities by \(v(o)\).

We may assume \(n\geq2\): an additional nonmanipulating agent with no turns changes no allocation. We may also assume the picking sequence has exactly \(m\) turns. If a source instance stops earlier, append turns of a nonmanipulating agent until all items are allocated. These appended turns do not change the manipulator’s bundle.

Let the resulting sequence be \((i_1,\ldots,i_m)\).

2. Polynomial reduction

Let \(K\) be the least power of two satisfying \(K\geq n\), and put \(c=1/K\).

Create one role for each source agent, so \(A=\{1,\ldots,n\}\), \(\tau=n\), and \(h=1\). Define population masses by

\(\displaystyle \mu_i=c\quad(1\leq i<n),\qquad \mu_n=1-(n-1)c.\)

These are positive dyadic rationals. Indeed,

\(\displaystyle \mu_n=\frac{K-n+1}{K}\geq\frac1K=c,\qquad \sum_{i=1}^{n}\mu_i=1.\)

In particular, \(\mu_h=c\).

For every item type set \(\beta_o=c\). Copy the rankings of all nonmanipulating agents, and set \(u_h(o)=v(o)\). These densities are positive, pairwise distinct integers, so they satisfy the target input requirements.

Set \(Q=m\) and use the template

\(\displaystyle (a_q,\lambda_q)=(i_q,c)\qquad(1\leq q\leq m).\)

Every block satisfies \(0<\lambda_q=c\leq\mu_{a_q}\). Moreover,

\(\displaystyle \sum_{q=1}^{Q}\lambda_q=mc=\sum_{o\in O}\beta_o.\)

Finally, set \(\theta=T\). Thus every target input condition holds. Repeated roles cause no difficulty because the problem imposes no constraint equating cumulative block mass with population mass.

If the source input has bit length \(S\), the constructed input has length \(O(S+(n+m)\log n)\): the copied data retain their encodings, and each new mass uses \(O(\log n)\) bits. The construction therefore takes polynomial time.

3. Exact allocation equivalence

Fix an arbitrary complete strict report of the manipulator, and use that same report in both instances.

We prove by induction on \(q\) that, after turn or block \(q\), an item is unallocated in the source instance exactly when its target supply remains \(c\); otherwise its target supply is zero. Whenever an item is allocated, its recipient is identical in both instances.

Before the first turn, every source item is available and every target supply equals \(c\).

Suppose the statement holds before turn \(q\). There are \(m-q+1\) available source items, so at least one remains. Agent \(i_q\) chooses its highest-ranked available item, say \(o\).

By the induction hypothesis, the item types with positive target supply are exactly the available source items. Role \(a_q=i_q\) uses the same ranking, so it also selects \(o\). Its remaining supply is \(c\), equal to the block mass \(\lambda_q\). Consequently, the block takes all of \(o\), fills immediately, and takes no other item type. This establishes the induction step.

Let \(B\) be the manipulator’s source bundle. The induction gives

\(\displaystyle x_{h,o}=\begin{cases}c,&o\in B,\\0,&o\notin B.\end{cases}\)

Since \(\mu_h=c\), its target average utility is exactly

\(\displaystyle \mu_h^{-1}\sum_{o\in O}u_h(o)x_{h,o}=\frac1c\sum_{o\in B}v(o)c=\sum_{o\in B}v(o).\)

This equality holds for every complete strict report. Hence some source report attains utility at least \(T\) if and only if some target report attains average utility at least \(\theta\). The reduction proves \(\mathrm{NP}\)-hardness.

4. Membership in \(\mathrm{NP}\) and running times

A certificate is a permutation of the \(m\) item types, encoding the strategic report in \(O(m\log(m+1))\) bits.

For exact verification, let \(D\) be the product of the denominators of all numerical input fields. Because their total encoding length is at most \(L\), \(D\) has \(O(L)\) bits. Multiplying all numerical fields by \(D\) produces integers of \(O(L)\) bits.

Simulate each block by scanning its role’s ranking and repeatedly allocating the minimum of the remaining block mass and remaining item supply. All allocation arithmetic then uses integers. Every block fills: at its start, total remaining supply equals the sum of its mass and all future block masses, and therefore is at least its own mass.

Let \(X_o=Dx_{h,o}\), \(U_o=Du_h(o)\), \(M_h=D\mu_h\), and \(\Theta=D\theta\). Since \(\mu_h>0\), the threshold test is exactly

\(\displaystyle \sum_{o\in O}U_oX_o\geq M_h\Theta.\)

All intermediate integers have \(O(L)\) bits: allocations are bounded by input supplies, and summing at most \(m\) terms adds only \(O(\log m)\) bits.

Scanning at most \(m\) entries per block, including input and certificate checks, gives a conservative verification bound of \(O((\tau+Q)mL^2)\) bit operations using elementary integer arithmetic. Thus the problem belongs to \(\mathrm{NP}\).

Enumerating all reports gives an exact algorithm running in \(O(m!(\tau+Q)mL^2)\) bit operations. A polynomial-time algorithm in \(m,\tau,Q,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the stated problem. The reduction is valid, the allocation equivalence holds for every strategic report, and the verification algorithm runs in polynomial time. The decision problem is \(\mathrm{NP}\)-complete when \(\tau\) is part of the input, including the claimed restriction \(Q=m\) with equal dyadic item supplies and block masses.

No major or minor issues were found.

Step-by-step verification

1. The cited source problem

The source theorem has the required hypotheses. Aziz et al. define complete strict preferences, positive utility values consistent with the manipulator’s strict preference order, and additive bundle utility. The proof of Theorem 2 explicitly formulates the decision problem with integer utilities and a target utility, asking whether a reported preference attains that target. Thus the cited result supports the source problem stated by the prover. Strict consistency ensures pairwise distinct utilities. [Aziz et al., preliminaries and Theorem 2](https://ojs.aaai.org/index.php/AAAI/article/download/10586/10445)

The source mechanism uses one fixed reported ranking throughout the picking sequence, as required for the reduction.

The two preprocessing steps are valid:

• Adding a nonmanipulating agent with no turns preserves every allocation and ensures \(n\geq 2\).
• Appending nonmanipulator turns to a sequence that stops before all items are allocated preserves the manipulator’s bundle for every report.

Neither step changes the decision answer, and both require only polynomial additional encoding.

2. Validity of the constructed input

Because \(K\geq n\), the proposed masses satisfy
\[ \mu_n=\frac{K-n+1}{K}\geq\frac{1}{K}=c>0. \]
Every other population mass equals \(c>0\), and their sum is exactly \(1\). All these numbers are dyadic rationals.

Since \(n\geq 2\), the strategic role \(h=1\) belongs to the range \(1\leq i<n\), so \(\mu_h=c\) follows from the definition.

For every block,
\[ 0<\lambda_q=c\leq\mu_{a_q}. \]
Every supply is positive, and
\[ \sum_{q=1}^{Q}\lambda_q=mc=\sum_{o\in O}\beta_o. \]
The copied rankings are complete and strict. The copied utility densities are positive, pairwise distinct integers, which are admissible binary rationals. The threshold \(T\) is also admissible.

The task explicitly permits repeated roles and cumulative block masses exceeding population masses. Consequently, no missing population constraint invalidates the construction.

3. Polynomial size of the reduction

The least power of two at least \(n\) has an encoding of \(O(\log n)\) bits. Each newly introduced rational therefore has \(O(\log n)\) bits.

The rankings, utilities, and sequence are copied from the source instance. There are \(O(n+m)\) new numerical fields, yielding the stated bound
\[ O\bigl(S+(n+m)\log n\bigr). \]
The preprocessing additions are also polynomial. The reduction’s size and construction-time claims are justified.

4. Exact allocation equivalence

The induction is correct.

Initially, every item is available in the source and has remaining supply \(c\) in the target. Before block \(q\), the induction hypothesis identifies the same available items in both instances.

Both acting agents use the same ranking, so they select the same highest-ranked available item. That item has target supply exactly \(c\), and the block mass is exactly \(c\). The block therefore exhausts precisely that item and immediately ends.

This preserves both availability and recipient identity. The condition \(q\leq m\) guarantees that an available item exists at every induction step.

The argument applies to an arbitrary complete strict strategic report, so it establishes equivalence for every report, not merely for a particular successful report.

5. Utility and decision equivalence

For the source bundle \(B\), the induction yields \(x_{h,o}=c\) exactly when \(o\in B\), and zero otherwise. Hence
\[ \mu_h^{-1}\sum_{o\in O}u_h(o)x_{h,o} =\frac{1}{c}\sum_{o\in B}v(o)c =\sum_{o\in B}v(o). \]

Together with \(\theta=T\), this proves both directions of the required existential equivalence. The source instance is a yes-instance exactly when the target instance is a yes-instance. The hardness conclusion follows.

6. Membership in \(\mathrm{NP}\) and running times

A permutation is a polynomial-size certificate specifying the complete strict report.

The common denominator construction is valid: the product of all input denominators has \(O(L)\) bits because their combined encoding length is at most \(L\). Scaling yields integer data of \(O(L)\) bits.

The block simulation correctly allocates the minimum of the remaining block mass and remaining supply. Its fill invariant is also correct: initially total supply equals total block mass, and completed blocks subtract equal quantities from both totals. Thus each pending block has sufficient remaining supply.

The threshold calculation is exact. With the prover’s definitions,
\[ \frac{\sum_o U_oX_o}{D M_h}\geq\frac{\Theta}{D} \quad\Longleftrightarrow\quad \sum_o U_oX_o\geq M_h\Theta, \]
because \(D>0\) and \(M_h>0\). This remains valid for negative thresholds.

The integer sizes stay within \(O(L)\) bits. Scanning at most \(m\) ranking entries per block and using elementary integer arithmetic gives the claimed conservative verification bound
\[ O\bigl((\tau+Q)mL^2\bigr). \]
Input and certificate validation and denominator preprocessing fit within that bound.

Enumerating all \(m!\) reports consequently gives the stated exact running time
\[ O\bigl(m!(\tau+Q)mL^2\bigr). \]

Repair feedback

No repair or additional clarification is needed. The proof establishes hardness for variable support size; it makes no unsupported claim about fixed \(\tau\).

⟨structured verdict parsed — rendered above⟩