Answer: \(\mathrm{NP\text{-}complete}\), and therefore \(\mathrm{NP\text{-}hard}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe decision version of the shortest reformist sequence problem is NP-complete even when mi ≤4 for every agent i ∈N and |{i ∈N | x ∈Mi}| ≤3 for every item x ∈M.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(A\) with masses \(\mu_a\ge0\), \(\sum_{a\in A}\mu_a=1\), finite item types \(X\) with capacities \(q_x\), strict acceptable orders \(\succ_a\), and an initial exact-envy-free allocation \(z^0\), where \(z_{a,x}\) is the mass of type \(a\) assigned to item type \(x\), determine the minimum total moved mass \(\sum_r\delta_r\) over finite sequences of legal moves. A move transfers \(\delta>0\) from \(z_{a,x}\) to \(z_{a,y}\), with \(y\succ_a x\), sufficient unassigned capacity, \(y\) the most-preferred legal unassigned item type, and exact envy-freeness preserved after every move; the sequence ends when no legal move exists.
Definitions. For each type \(a\), let \(X_a\) be its acceptable item types, ordered strictly by \(\succ_a\). A feasible allocation has \(z_{a,x}\ge 0\), \(\sum_{x\in X_a}z_{a,x}=\mu_a\), and \(\sum_{a:x\in X_a}z_{a,x}\le q_x\). It is exactly envy-free if, whenever \(z_{a,x}>0\) and \(z_{b,y}>0\), we have \(y\not\succ_a x\).
A move replaces \(z_{a,x}\) by \(z_{a,x}-\delta\) and \(z_{a,y}\) by \(z_{a,y}+\delta\), where \(\delta>0\), \(y\succ_a x\), \(z_{a,x}\ge\delta\), \(q_y-\sum_b z_{b,y}\ge\delta\), and the resulting allocation is exactly envy-free. Moreover, \(y\) must be \(\succ_a\)-maximal among item types for which a transfer of \(\delta\) satisfying these conditions is possible. A sequence is terminal when no legal move exists. All masses, capacities, and the threshold \(B\) are binary-encoded nonnegative rationals.
Target. Is the threshold problem—whether a terminal legal sequence from \(z^0\) has total moved mass at most \(B\)—solvable in polynomial time, or is it NP-hard?
Nearest known results. For indivisible items and one item per agent, the shortest reformist-sequence decision problem is NP-complete, even when every preference list has length at most \(4\) and every item is acceptable to at most \(3\) agents.
For that discrete problem, polynomial-time algorithms are known when every preference list has length at most \(3\), or every item is acceptable to at most \(2\) agents.
Under the existential interpretation—whether there exists a terminal legal sequence of total moved mass at most \(B\)—the problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when every positive mass and capacity equals \(1\), every preference list has length at most \(4\), and every item type is acceptable to at most \(3\) types.
Lemma 1. In every exactly envy-free allocation, each type \(a\) with \(\mu_a>0\) receives positive mass from exactly one item type.
Proof. Feasibility gives \(\sum_{x\in X_a}z_{a,x}=\mu_a>0\), so the support of \(a\) is nonempty.
Suppose distinct \(x,y\in X_a\) both satisfy \(z_{a,x}>0\) and \(z_{a,y}>0\). Because \(\succ_a\) is a strict total order, either \(y\succ_a x\) or \(x\succ_a y\). In the first case, apply exact envy-freeness with the two positive entries \(z_{a,x}\) and \(z_{a,y}\), taking \(b=a\). It requires \(y\not\succ_a x\), a contradiction. The second case is symmetric. Thus the support has size one. ∎
Consequently, if \(h(a)\) denotes the unique supported item type, then \(z_{a,h(a)}=\mu_a\).
Lemma 2. Suppose \(z\) is exactly envy-free and a legal move transfers mass \(\delta\) for type \(a\) from \(x\) to \(y\succ_a x\). Then \(\delta=\mu_a\).
Proof. By Lemma 1, \(x\) is the unique supported item of \(a\), and hence \(z_{a,x}=\mu_a\) and \(z_{a,y}=0\).
After the transfer, \(z'_{a,y}=\delta>0\). If \(\delta<\mu_a\), then also \(z'_{a,x}=\mu_a-\delta>0\). Since \(y\succ_a x\), this contradicts exact envy-freeness of the resulting allocation. Therefore \(\delta=\mu_a\). ∎
Thus arbitrary rational transfer sizes do not create genuinely fractional dynamics: after an exactly envy-free state is reached, a type moves as one indivisible token of weight \(\mu_a\).
Use the discrete shortest reformist-sequence problem stated in the prompt as the source problem. An instance consists of agents, unit-capacity items, strict preferences, an initial envy-free matching, and an integer threshold \(K\).
Construct a mass instance as follows.
This construction is polynomial-time.
By Lemma 1, every exactly envy-free allocation assigns each positive-mass type to exactly one item. Since all masses and capacities equal \(1\), no two types can be assigned to the same item. Hence exactly envy-free feasible allocations are precisely envy-free matchings.
Moreover, the mass envy-freeness condition says that if \(a\) holds \(x\) and \(b\) holds \(y\), then \(y\not\succ_a x\). This is exactly the discrete no-envy condition.
Consider a mass move by type \(a\) from its current item \(x\) to \(y\). Lemma 2 forces \(\delta=1\). The capacity condition
\[ q_y-\sum_b z_{b,y}\geq 1 \]
holds exactly when \(y\) is unassigned. The remaining requirements say precisely that \(y\succ_a x\), the new matching is envy-free, and \(y\) is the most preferred destination among those satisfying these conditions.
Therefore legal moves, including the maximal-destination rule, correspond one-for-one in the two instances. Terminal states also correspond.
Every mass move has moved mass \(1\). Hence a sequence containing \(t\) moves has total moved mass \(t\), and therefore
\[ \text{there is a terminal discrete sequence of length at most }K \]
if and only if
\[ \text{there is a terminal mass sequence of total moved mass at most }B. \]
The source problem is \(\mathrm{NP}\)-complete under the restrictions that preference lists have length at most \(4\) and each item is acceptable to at most \(3\) agents. The reduction preserves both restrictions. This proves \(\mathrm{NP}\)-hardness.
At an exactly envy-free state, every move changes the unique item of some type \(a\) to a strictly preferred item. Thus type \(a\) can move at most \(|X_a|-1\) times. Every legal sequence therefore has length at most
\[ \sum_a\bigl(|X_a|-1\bigr), \]
which is polynomial in the explicitly represented preference lists.
A certificate lists the moving type and destination at every step. The transfer amount is forced to be \(\mu_a\) by Lemma 2. For each step one can verify in polynomial time:
Terminality is verified by scanning every type and every better destination. If any feasible destination exists, its unique most-preferred member defines a legal move.
Therefore the problem belongs to \(\mathrm{NP}\).
The continuous-looking transfer rule does not fractionalize the reformist-sequence problem because exact support-based envy-freeness forces every type to remain concentrated on one item. The supplied discrete hardness result consequently transfers without a purification gadget.
⟨structured verdict parsed — rendered above⟩
The output makes genuine and substantial progress: Lemmas 1 and 2 are correct under their stated hypotheses, and the unit-mass embedding would establish the requested NP-hardness if the cited discrete reformist-sequence problem has exactly the asserted move rule.
However, the claimed NP-completeness is not fully established. The membership argument silently assumes that \(z^0\) is exactly envy-free, whereas the task only specifies that every resulting allocation after a move is exactly envy-free. Additionally, the discrete source problem’s move rule is never stated precisely enough to verify the crucial maximal-destination correspondence.
This lemma is correct, assuming “ordered strictly” means a strict total order on \(X_a\).
The use of \(b=a\) in the envy-freeness condition is legitimate. If two distinct items \(x,y\in X_a\) both have positive mass for type \(a\), totality gives either \(y\succ_a x\) or \(x\succ_a y\), contradicting exact envy-freeness.
The conclusion \(z_{a,h(a)}=\mu_a\) follows from feasibility.
The lemma explicitly applies only to \(\mu_a>0\), which matters later because the input permits zero masses.
Lemma 2 is correct as stated because it assumes that the allocation before the move is exactly envy-free.
Once \(a\) is concentrated on \(x\), a transfer \(0<\delta<\mu_a\) leaves positive mass on both \(x\) and \(y\), contradicting exact envy-freeness of the resulting allocation.
The later claim that the transfer amount is forced at every certified step does not follow unless \(z^0\) itself is exactly envy-free.
A concrete failure under the task as written is:
Moving \(\delta=1/2\) from \(x\) to \(y\) satisfies the capacity condition and produces the exactly envy-free allocation concentrated on \(y\). Thus the first legal move can have \(\delta\ne\mu_a\). Lemma 2 does not apply because \(z^0\) is not exactly envy-free.
For the constructed unit instance, the allocation correspondence is correct:
Thus such allocations correspond to complete unit-capacity matchings, with unused items allowed.
The construction also preserves the stated bounds on preference-list length and item acceptability degree.
Conditional on the discrete source problem having exactly the following features, the correspondence is correct:
The prover does not state the discrete move definition or a precise version of the cited NP-completeness theorem. The prompt merely identifies the “shortest reformist-sequence decision problem” and its restrictions. Consequently, the assertion that the maximal-destination rules “correspond one-for-one” cannot be independently verified from the write-up.
This is a major gap because dropping or modifying the maximal-destination rule changes the transition system to which the hardness theorem is being applied. The minimum clarification needed is a precise statement of the discrete legal-move and terminality definitions, together with confirmation that the cited NP-completeness result holds for exactly that definition.
Subject to that clarification, the reduction does establish NP-hardness even for unit masses and capacities.
The polynomial bound on the number of moves is correct after an exactly envy-free state has been reached: each move sends a positive-mass type to a strictly preferred item, so that type cannot move more than \(|X_a|-1\) times.
The verification procedure is also adequate for moves whose source allocation is exactly envy-free.
It does not verify a possible first move from a merely feasible, non-envy-free \(z^0\):
The prover must either identify an explicit input hypothesis that \(z^0\) is exactly envy-free or separately specify and justify verification of the first move. Without one of those clarifications, NP membership is not established as written.
There is also a minor zero-mass edge case. The claimed bound
\[ \sum_a \bigl(|X_a|-1\bigr) \]
can be negative or artificially reduced if a zero-mass type has \(X_a=\varnothing\). Zero-mass types cannot move, but the displayed bound must exclude them or otherwise account for empty lists.
The prover explicitly adopts an existential interpretation. This is consistent with the usual shortest-sequence decision problem, but the target’s wording does not formally display the existential quantifier. The decision language should be stated explicitly as asking whether there exists such a terminal sequence.
The concentration lemmas and unit-instance embedding are sound. The NP-hardness conclusion is promising but depends on a missing precise statement of the discrete source theorem’s move rule. The stronger NP-completeness claim additionally has a major gap at the first move unless \(z^0\) is assumed exactly envy-free.
⟨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.