d4-conf-ecai-2024-0062 (d4-conf-ecai-2024-0062)

Given finite-support distributions μ_x and μ_y over welfare levels in a common interval \(X\), with rational levels and masses, equal mean welfare, and continuous Lorenz dominance \(\int_0^r Q_{μ_x}(s)\,ds \leq \int_0^r Q_{μ_y}(s)\,ds\) for every \(r\in[0,1]\), can μ_y be reached from μ_x in at most \(k\) moves? Each move chooses submeasures α,β of the current distribution μ with \(α+β\leqμ\), equal positive mass, and recipient welfare levels below donor welfare levels; for some \(t>0\) that keeps the shifted levels in \(X\), it replaces μ by \(μ-α-β+(z\mapsto z+t)_\#α+(z\mapsto z-t)_\#β.

Given a rational interval \(X=[a,b]\) with \(a<b\), let \(\mu_x,\mu_y\) be finite-support probability distributions over scalar welfare levels in \(X\); negative levels are allowed. A society is given by its support: the list of types with positive mass, each mass a binary rational. Let \(\tau\) be the larger input support size, not the number of possible types; welfare has dimension \(m=1\). All input levels are binary rationals, and \(L\) is the total input bit length, including the positive integer \(k\) encoded in binary.
Promise equal mean welfare and \(\int_0^r Q_{\mu_x}(s)\,ds\leq\int_0^r Q_{\mu_y}(s)\,ds\) for every \(r\in[0,1]\), where \(Q_\mu\) is the quantile function.
A move chooses nonnegative submeasures \(\alpha,\beta\) with \(\alpha+\beta\leq\mu\) and \(\alpha(X)=\beta(X)>0\), with every level in \(\operatorname{supp}\alpha\) strictly below every level in \(\operatorname{supp}\beta\), and a real \(t>0\). It replaces \(\mu\) by \(\mu-\alpha-\beta+(z\mapsto z+t)_\#\alpha+(z\mapsto z-t)_\#\beta\), where \(\#\) denotes pushforward; all resulting levels must remain in \(X\).
The move must preserve welfare order, including relative to unchanged mass: define \(\Gamma=\{(z,z+t):z\in\operatorname{supp}\alpha\}\cup\{(z,z-t):z\in\operatorname{supp}\beta\}\cup\{(z,z):z\in\operatorname{supp}(\mu-\alpha-\beta)\}\); require \(u'\leq v'\) whenever \((u,u'),(v,v')\in\Gamma\) and \(u<v\). Ties may split and resulting ties are allowed. Selected masses and intermediate levels may be real; each entire move counts once.
Is deciding whether \(\mu_y\) is reachable from \(\mu_x\) in at most \(k\) such moves solvable in polynomial time in \(\tau\) and \(L\), with \(m=1\), or is it NP-hard?
For finite lists of \(n\) agents, deciding whether an equal-total Lorenz improvement admits at most \(k\) order-preserving pairwise redistributive transfers is NP-hard; such improvements admit a chain of at most \(n\) transfers ([Willot, Belahcene and Destercke](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240587)). No complexity classification for exactly the mass moves defined above was located.

Partial result: an exact decomposition of the minimum move count

The polynomial-time-versus-$\mathsf{NP}$-hardness classification remains unresolved. I prove a new structural result: the minimum number of moves is additive over the rank intervals on which the target-minus-source Lorenz gap is positive.

This decomposition is computable in polynomial time. It gives polynomially computable lower bounds, an exact algorithm for a nontrivial subclass, and a polynomial-time oracle reduction to instances whose Lorenz gap is strictly positive at every interior rank.

1. Definitions and quantile representation of a move

Let $\lambda$ be Lebesgue measure on $(0,1)$. Write
$$ F(r)=\int_0^r\bigl(Q_{\mu_y}(s)-Q_{\mu_x}(s)\bigr)\,ds. $$
The promise states that $F(r)\geq 0$ for all $r\in[0,1]$, with
$$ F(0)=F(1)=0. $$

For distributions $\mu,\nu$, let $T(\mu,\nu)$ denote the minimum number of legal moves from $\mu$ to $\nu$, with value $+\infty$ if no finite chain exists. Zero moves are allowed.

We first justify using ranks throughout a chain.

Lemma 1. Suppose a finite-support coupling $\pi$ of $\mu,\nu$ satisfies
$$ u<v\quad\Longrightarrow\quad u'\leq v' $$
for every two support pairs $(u,u'),(v,v')$. Then $\pi$ is the law of
$$ \bigl(Q_\mu(r),Q_\nu(r)\bigr),\qquad r\sim\lambda. $$

Proof. Fix thresholds $c,d$, and let
$$ A=\{u\leq c\},\qquad B=\{u'\leq d\}. $$
If both $A\setminus B$ and $B\setminus A$ had positive probability, finite support would provide pairs satisfying
$$ u_1\leq c<u_2,\qquad u'_1>d\geq u'_2, $$
contradicting the order condition. Consequently,
$$ \pi(A\cap B) = \min\{\mu((-\infty,c]),\nu((-\infty,d])\}. $$
These joint cumulative probabilities determine $\pi$ and agree with those of the quantile coupling. $\square$

A legal move supplies precisely such a coupling, including its unchanged mass. Therefore, if $q,q'$ are the quantiles immediately before and after a move with shift $t$, there are measurable rank sets $A,B$ such that, almost everywhere,
$$ q'(r)-q(r)=t\,\mathbf 1_A(r)-t\,\mathbf 1_B(r). $$
Here $A$ represents recipient mass and $B$ donor mass. They satisfy
$$ \lambda(A)=\lambda(B)>0. $$
Strict separation of the selected welfare levels implies that every rank in $A$ precedes every rank in $B$, apart from null sets.

Define the move’s cumulative gain by
$$ G(r)=\int_0^r(q'(s)-q(s))\,ds =t\bigl(\lambda(A\cap(0,r))-\lambda(B\cap(0,r))\bigr). $$

Lemma 2. There are numbers $\ell<u$ such that
$$ G(r)>0\quad\Longleftrightarrow\quad \ell<r<u. $$
In particular, $G(r)\geq0$ everywhere.

Proof. The rank sets are finite unions of intervals, because the distributions and the coupling have finite support. Take $\ell$ to be the leftmost endpoint of $A$ and $u$ the rightmost endpoint of $B$, ignoring null sets.

Before donor ranks begin, any rank strictly after $\ell$ has accumulated positive recipient mass and no donor mass. Once donor ranks begin, all recipient mass has been accumulated; at every rank strictly before $u$, some donor mass remains unaccumulated. Equal total selected masses then imply $G(r)>0$ throughout $(\ell,u)$.

Before $\ell$ neither selected set has contributed. After $u$ both have contributed their equal total masses. Thus $G$ is zero outside $(\ell,u)$. $\square$

This argument includes comparisons with unchanged mass and permits splitting at ties.

2. Tight Lorenz ranks are barriers

Consider any successful chain with quantiles
$$ q_0=Q_{\mu_x},\ q_1,\ldots,q_h=Q_{\mu_y}. $$
Let $G_j$ be the cumulative gain of move $j$. Telescoping gives
$$ F(r)=\sum_{j=1}^hG_j(r). $$
Every summand is nonnegative by Lemma 2. Hence
$$ F(r)=0\quad\Longrightarrow\quad G_j(r)=0 \quad\text{for every }j. $$

Let
$$ J_1,\ldots,J_g $$
be the connected components of
$$ \{r\in(0,1):F(r)>0\}. $$
Write $J_i=(c_i,d_i)$ and $w_i=d_i-c_i$.

Proposition 3. In every successful chain, all selected rank mass of each move belongs to one component $J_i$, up to null sets.

Proof. By Lemma 2, the positivity set of that move’s cumulative gain is a nonempty interval $(\ell,u)$. Since its gain is bounded above by $F$, this interval lies in $\{F>0\}$ and therefore in one connected component.

The selected recipient and donor ranks lie in $[\ell,u]$. Endpoints have zero rank mass, so all selected mass belongs to that component. $\square$

Thus a move cannot batch selected mass from different positive-gap components. This remains true even when its numerical shift could be used in both components.

3. Exact additivity theorem

For $J_i=(c_i,d_i)$, define normalized local distributions
$$ \mu_x^{(i)} = \frac1{w_i}(Q_{\mu_x})_\#(\lambda|_{J_i}), \qquad \mu_y^{(i)} = \frac1{w_i}(Q_{\mu_y})_\#(\lambda|_{J_i}). $$
Their quantiles satisfy, almost everywhere,
$$ Q_{\mu_x^{(i)}}(s)=Q_{\mu_x}(c_i+w_i s), \qquad Q_{\mu_y^{(i)}}(s)=Q_{\mu_y}(c_i+w_i s). $$

Because $F(c_i)=F(d_i)=0$, the local means agree. Their Lorenz gap is
$$ \int_0^s \bigl(Q_{\mu_y^{(i)}}(v)-Q_{\mu_x^{(i)}}(v)\bigr)\,dv = \frac{F(c_i+w_i s)}{w_i}. $$
It is strictly positive for every $s\in(0,1)$. Thus every local instance satisfies the promise, with no interior tight rank.

Theorem 4. With the convention that a sum containing $+\infty$ equals $+\infty$,
$$ T(\mu_x,\mu_y) = \sum_{i=1}^gT(\mu_x^{(i)},\mu_y^{(i)}). $$
If $g=0$, the sum is zero.

Proof: lower bound. Take any successful global chain of length $h$. Proposition 3 assigns each move to exactly one component. Let $h_i$ be the number assigned to $J_i$.

Restrict the quantile chain to $J_i$ and normalize its rank mass by $w_i$. Moves assigned to other components change nothing in this restriction. Each assigned move becomes a legal local move: both selected masses are divided by the same factor, strict support separation persists, and the global order condition implies the local one. Therefore,
$$ h_i\geq T(\mu_x^{(i)},\mu_y^{(i)}). $$
Summing yields the required lower bound. It also shows that if any local minimum is infinite, no successful global chain exists.

Proof: upper bound. Suppose all local minima are finite, and choose a shortest local chain for each component.

We need to verify that these chains can be embedded into the global society. First, every legal move keeps all resulting levels between the current minimum and maximum. Indeed, for any recipient level $u$ and donor level $v$, legality gives
$$ u+t\leq v-t. $$
Thus both moved outputs lie between $u$ and $v$. By induction, a local chain stays within its initial support interval.

Initial support intervals of successive rank components are ordered and can overlap only at boundary levels. Any intervening ranks outside the components retain their initial quantile values: on such intervals $F=0$, so its derivative
$$ Q_{\mu_y}-Q_{\mu_x} $$
is zero almost everywhere.

Consequently, replacing one component by any stage of its local chain preserves the order of the global quantile, including across component boundaries. Scale that local move’s selected masses by $w_i$. They are valid global submeasures. Strict recipient–donor separation remains valid, and the nondecreasing global output quantile verifies the order condition relative to all unchanged mass. Shared boundary levels cause no problem because the rule permits splitting at ties.

Concatenating the embedded local chains therefore gives a global chain of length
$$ \sum_iT(\mu_x^{(i)},\mu_y^{(i)}). $$

Finally, if $g=0$, then $F$ is identically zero. Differentiating its piecewise-affine expression shows that the two quantiles agree almost everywhere, so $\mu_x=\mu_y$. $\square$

4. Polynomial-time construction and consequences

Merge the cumulative-mass breakpoints of the two input distributions. There are at most
$$ n_x+n_y-1\leq2\tau-1 $$
positive-length intervals in the resulting partition, and $F$ is affine on each.

A nonnegative affine function cannot have an isolated zero in the interior of one of these intervals. Therefore every endpoint of a positive-gap component is a merged breakpoint. Exact rational arithmetic constructs all components and their normalized local distributions in time polynomial in $\tau$ and $L$. Restricting rank masses and dividing by $w_i$ produces rational numbers of polynomial bit length.

There are two useful consequences.

Reduction to strictly positive Lorenz gaps

Suppose there is a polynomial-time decision algorithm for promised instances satisfying
$$ F(r)>0\qquad(0<r<1). $$
Then the general promised problem is also polynomial-time solvable.

For each component, first ask whether its target is reachable within $k$ moves. A negative answer makes the global answer negative. Otherwise, binary search determines its exact minimum in $\{1,\ldots,k\}$ using
$$ O(\log(k+1)) $$
decision calls. Theorem 4 then decides the global instance by summing the local minima.

Since the number and sizes of the local instances are polynomially bounded, and $\log(k+1)$ is bounded by the input length, this is a polynomial-time oracle reduction. Conversely, an algorithm for the general problem applies to the strictly positive-gap subclass.

Thus the unresolved polynomial-time question can be concentrated on that subclass.

A polynomially solvable subclass and a lower bound

For completeness, the following one-move criterion is sufficient to recognize an exact subclass.

Let $\mu\ne\nu$ have equal means, and put
$$ D(r)=Q_\nu(r)-Q_\mu(r). $$
One move is possible if and only if some $t>0$ satisfies:

• $D(r)\in\{-t,0,t\}$ almost everywhere;
• both nonzero signs occur on positive-measure rank sets;
• recipient and donor initial levels satisfy

$$ \max\{Q_\mu(r):D(r)=t\} < \min\{Q_\mu(r):D(r)=-t\}. $$

Necessity follows from Lemma 1 and the move’s strict support separation.

For sufficiency, select exactly the rank masses with displacements $t$ and $-t$. They define disjoint submeasures of $\mu$. Equal means give
$$ 0=\int_0^1D(r)\,dr =t\bigl(\lambda\{D=t\}-\lambda\{D=-t\}\bigr), $$
so the selected masses are equal and positive. Condition 3 gives strict separation. Their outputs are the target quantile, whose monotonicity verifies the full order condition. All outputs lie in $X$.

The criterion is polynomial-time checkable on the merged quantile partition: any nonzero displacement fixes the sole possible value of $t$.

Apply it to every component. If all $g$ components pass, then
$$ T(\mu_x,\mu_y)=g. $$
More generally, if $b$ components fail, then
$$ T(\mu_x,\mu_y)\geq g+b. $$
Indeed, each positive-gap component requires at least one move, and every failed component requires at least two, or is unreachable. Both $g$ and $b$ are polynomial-time computable.

5. Exact additive families with arbitrarily long local chains

The decomposition gives examples where batching cannot shorten the sum of several independently long chains.

Choose positive integers $q_0,\ldots,q_{s-1}$ and put
$$ p_i=2^{-q_i}. $$
On $X=[0,2s-1]$, define
$$ \mu_x = \frac1s\sum_{i=0}^{s-1} \left( p_i\delta_{2i}+(1-p_i)\delta_{2i+1} \right), $$
$$ \mu_y = \frac1s\sum_{i=0}^{s-1}\delta_{\,2i+1-p_i}. $$
Then
$$ T(\mu_x,\mu_y)=\sum_{i=0}^{s-1}q_i. $$

Here is a complete verification.

Promise and components

For the normalized two-point source
$$ p\delta_0+(1-p)\delta_1 $$
and target $\delta_{1-p}$, the Lorenz gap is
$$ f_p(r)= \begin{cases} (1-p)r,&0\leq r\leq p,\\ p(1-r),&p\leq r\leq1. \end{cases} $$
The means agree, and $f_p$ is strictly positive on $(0,1)$.

Translations preserve these properties. Each block in the displayed construction has equal source and target means. Therefore its global Lorenz gap, for
$$ \frac{i}{s}\leq r\leq\frac{i+1}{s}, $$
equals
$$ F(r)=\frac1s f_{p_i}(sr-i). $$
Its positive-gap components are exactly
$$ \left(\frac{i}{s},\frac{i+1}{s}\right), \qquad 0\leq i<s. $$

Each block needs exactly $q_i$ moves

It suffices to prove this for $p=2^{-q}$ on $[0,1]$.

Let $m,M$ be the current extrema and $m',M'$ the extrema after a move. The support-interval argument above gives
$$ m\leq m',\qquad M'\leq M. $$
If minimum-level mass remains unchanged, then $m'=m$. Otherwise all minimum-level mass must be selected as recipient mass. It cannot be donor mass, because recipients would have to lie strictly below it. Order preservation makes its output $m+t$ the new minimum, and any selected donor level $v$ satisfies
$$ m+t\leq v-t. $$
Hence
$$ m'\leq\frac{m+M}{2}. $$

Starting from extrema $0,1$, induction therefore yields
$$ m_h\leq1-2^{-h} $$
after $h$ moves. Reaching the singleton target at $1-2^{-q}$ requires $h\geq q$.

For achievability, define
$$ \nu_j = 2^{j-q}\delta_{\,1-2^{-j}} + (1-2^{j-q})\delta_1, \qquad 0\leq j\leq q, $$
omitting zero-mass terms. For $j<q$, select all lower-level mass and an equal amount at level $1$, and choose
$$ t_j=2^{-(j+1)}. $$
The available lower mass satisfies $2^{j-q}\leq1/2$. Both selected groups arrive at
$$ 1-2^{-(j+1)}. $$
Any unchanged mass stays at $1$, so the full order condition holds. This produces $\nu_{j+1}$ and reaches the target in $q$ moves.

Thus every local optimum is $q_i$. Theorem 4 proves the asserted global optimum.

The source has support size $2s$, and the target has support size $s$. For fixed $s$, specifying the decision threshold
$$ k=\sum_iq_i $$
gives total input length
$$ L=\Theta\!\left(\sum_iq_i\right). $$
This also incorporates the threshold-encoding clarification identified in the previous verifier report.

6. Remaining classification question

The proved decomposition isolates the remaining difficulty: a promised instance with
$$ F(r)>0\qquad(0<r<1). $$
It does not provide a polynomial-time algorithm or an $\mathsf{NP}$-hardness reduction for such instances.

A proposed short consensus construction was discarded because later midpoint moves could cross unchanged mass already placed at the mean. No polynomial bound on general successful-chain length is claimed here.

⟨structured verdict parsed — rendered above⟩

The output establishes a valid structural decomposition and several consequences, but does not resolve the requested complexity classification. I found no mathematical error in the partial results. The missing classification is explicitly acknowledged by the prover.

1. Quantile representation

Lemma 1 is correct. If both threshold events $A\setminus B$ and $B\setminus A$ have positive probability, finite support supplies the two support pairs displayed in the proof. Their initial coordinates are strictly ordered, while their final coordinates are oppositely ordered, contradicting the hypothesis.

Consequently, the formula
$$ \pi(A\cap B)=\min\{\mu((-\infty,c]),\nu((-\infty,d])\} $$
holds for every pair of thresholds. These joint cumulative probabilities determine the coupling and coincide with those of the quantile coupling.

The treatment of ties is valid: the contradiction requires distinct initial levels, and does not impose an additional restriction on pairs with the same initial level.

The application to a legal move is valid. Its selected and unchanged mass define a finite-support coupling satisfying precisely the order condition in Lemma 1. Therefore the rank displacement takes values in $\{-t,0,t\}$ almost everywhere.

The recipient and donor rank sets have equal positive measure. Strict separation of their initial welfare levels places all recipient ranks before all donor ranks, up to null sets. Finite support makes these sets finite unions of intervals, again up to null sets.

2. Positivity interval and barriers

Lemma 2 is correct. The endpoint choices ensure that:

• Every rank strictly after $\ell$ and before donor ranks begin has accumulated positive recipient mass.
• After donor ranks begin, all recipient mass has already accumulated.
• At every rank strictly before $u$, some donor mass remains unaccumulated.

Equal selected masses therefore give exactly the claimed positivity set $(\ell,u)$. The gain vanishes outside that interval and is nonnegative everywhere.

The telescoping argument is correct. For a successful chain,
$$ F(r)=\sum_{j=1}^hG_j(r). $$
Since all summands are nonnegative, a zero of $F$ forces every summand to vanish there. No cancellation is possible.

Proposition 3 follows. Each move has a nonempty connected positivity interval contained in $\{F>0\}$, so that interval lies in a unique component. Its selected rank mass lies between its endpoints. Endpoints have zero Lebesgue mass, including when a rank endpoint cuts through an atom of the welfare distribution.

Thus the claimed barrier property is established.

3. Local distributions and exact additivity

The local distributions are well defined. Each component has positive length $w_i$, and restriction followed by normalization produces a finite-support probability distribution.

The displayed local quantile formula is correct. Since $F(c_i)=F(d_i)=0$, the local source and target means agree. The local Lorenz gap is
$$ \frac{F(c_i+w_i s)}{w_i}, $$
which is strictly positive for every $s\in(0,1)$.

The lower bound in Theorem 4 is valid. Proposition 3 assigns each global move to one component. Restricting to that component preserves the move’s displacement, strict support separation, and order condition. Normalization scales both selected masses by the same positive factor.

Moves assigned elsewhere leave the restricted quantile unchanged almost everywhere. Removing those unchanged stages therefore gives a local chain with the asserted number of moves.

The support confinement argument used for the upper bound is correct. For any selected recipient level $u$ and donor level $v$, legality gives
$$ u+t\leq v-t. $$
Together with $t>0$, this places both moved outputs between $u$ and $v$. Unchanged outputs also remain in the current support interval. Hence every local chain stays inside its initial support interval.

Embedding the local chains is valid. Initial support intervals of successive rank components are ordered because the initial quantile is nondecreasing. They may share a boundary level, but cannot overlap in their interiors.

Ranks outside the positive-gap components retain their initial quantile values in the target: on every interval where $F$ is identically zero, its derivative is zero almost everywhere. The remaining component endpoints have zero rank mass.

Consequently, confinement to the initial local support interval prevents a local chain from crossing levels in other components or in unchanged intervening ranks. Scaling the selected local masses by $w_i$ gives valid global submeasures. Shared boundary levels are permissible because the move condition imposes no comparison between equal initial levels.

The lower and upper bounds establish
$$ T(\mu_x,\mu_y)=\sum_{i=1}^gT(\mu_x^{(i)},\mu_y^{(i)}), $$
including the stated convention for unreachable instances.

The case $g=0$ is handled correctly. Then $F$ vanishes identically, the quantiles agree almost everywhere, and the distributions are equal. The minimum is zero.

4. Polynomial construction and oracle reduction

The partition-size bound is correct. There are at most $n_x-1$ and $n_y-1$ internal cumulative-mass breakpoints, respectively. Their merged partition therefore has at most
$$ n_x+n_y-1\leq 2\tau-1 $$
positive-length intervals.

On each interval, $F$ is affine. A nonnegative affine function cannot have an isolated interior zero unless it vanishes throughout that interval. Hence every endpoint of a positive-gap component is a merged breakpoint.

The rational-arithmetic claim is justified. The construction uses polynomially many additions, subtractions, multiplications, and divisions on input rationals. Component endpoints are cumulative-mass breakpoints; restriction and normalization consequently produce rational masses of polynomial bit length. There is no expansion into individually represented agents.

The oracle reduction is correct. Reachability within a threshold is monotone in that threshold. Once a component is known to be reachable within $k$ moves, binary search over $\{1,\ldots,k\}$ finds its exact minimum using $O(\log(k+1))$ calls.

Positive-gap components have distinct source and target distributions, so their minima cannot be zero. Binary encoding of $k$ is respected: the number of calls is polynomial in its bit length.

This is a valid conditional reduction. It does not itself provide an algorithm for the strictly positive-gap subclass.

5. One-move criterion and lower bound

Necessity is correct. Lemma 1 identifies the legal move coupling with the quantile coupling. Its displacement therefore satisfies the three stated conditions.

Sufficiency is correct. Selecting the rank mass with displacement $t$ and $-t$ produces submeasures of the source. Condition 3 ensures that recipient and donor supports are strictly separated. Equal means give equal selected masses, and condition 2 makes them positive.

The resulting coupling has the target quantile as its output. Its monotonicity verifies the full order condition, including comparisons with unchanged mass. All resulting levels belong to $X$ because they are target levels.

Polynomial checkability is correct. On the merged partition, displacement is constant on each positive-length interval. Any nonzero displacement fixes the only possible value of $t$, after which all three conditions can be checked directly.

The consequences
$$ T(\mu_x,\mu_y)=g $$
when every component passes, and
$$ T(\mu_x,\mu_y)\geq g+b $$
when $b$ components fail, follow correctly from Theorem 4. Unreachable components are consistent with the extended-value inequality.

6. Exact additive examples

The promise calculation is correct. For the two-point source and singleton target, the displayed formula
$$ f_p(r)= \begin{cases} (1-p)r,&0\leq r\leq p,\\ p(1-r),&p\leq r\leq1 \end{cases} $$
has zero endpoint values and is strictly positive at every interior rank.

The translated blocks are ordered, and each has equal source and target means. Thus the stated global Lorenz-gap formula and its component intervals are correct.

The lower bound of $q$ moves is valid. If some minimum-level mass remains unchanged, the minimum does not increase. Otherwise all minimum-level mass must be selected as recipients, and order preservation makes its common output the new minimum. Comparison with a selected donor gives
$$ m'\leq\frac{m+M}{2}. $$
Since the maximum never exceeds $1$, the asserted induction yields
$$ m_h\leq1-2^{-h}. $$
For $h<q$, this is strictly below the target singleton level $1-2^{-q}$.

The construction attaining $q$ moves is correct. At stage $j<q$, the lower mass $2^{j-q}$ is at most one half, so the required donor mass is available. Both selected groups reach
$$ 1-2^{-(j+1)}. $$
Their combined mass is $2^{j+1-q}$, which gives exactly $\nu_{j+1}$. Any unchanged mass remains at $1$, satisfying the full order condition.

Theorem 4 therefore establishes the claimed sum of local optima.

The encoding claim is correct for fixed $s$. Explicit binary rational representations of $2^{-q_i}$ and the associated levels require bit length proportional to $q_i$. Encoding the displayed threshold adds no larger asymptotic contribution. These examples do not establish a superpolynomial move requirement in the input bit length, and the prover does not claim otherwise.

7. Outstanding requirement and actionable feedback

Major incompleteness relative to USER_TASK: the requested polynomial-time-versus-$\mathsf{NP}$-hardness classification remains unanswered. This is an acknowledged limitation, not a false mathematical claim.

No repair is needed for the structural arguments audited above. To resolve the assigned task, the prover must supply either a polynomial-time decision algorithm with runtime polynomial in $\tau$ and $L$, including binary-encoded $k$, or a valid hardness reduction for exactly the specified mass moves. The decomposition and subclass algorithm do not supply either result.

⟨structured verdict parsed — rendered above⟩