Answer: —
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of deciding whether a given college $c \in C$ can beneficially manipulate \studentproposing DAA via misrepresenting its preferences is solvable in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of colleges \(C\), a finite support \(T\) of applicant types, rational masses \(\mu_t>0\) summing to \(1\), and rational capacity shares \(\kappa_c\), each type \(t\) has a complete ranking of colleges and a priority position at each college. Colleges have true complete rankings of types. Run student-proposing mass DA, in which unheld mass proposes to its next-ranked college and each college holds its highest-ranked applicant mass up to its capacity, splitting type mass at a cutoff if needed. For a target college \(c^\star\), compare its truthful allocation with the allocation produced when it reports an arbitrary complete ranking of types and all other reports stay fixed. Determine whether some report gives \(c^\star\) a strictly beneficial bundle under its true responsive preferences: after padding both bundles with vacant seats to capacity, there is a mass-preserving coupling under which every new type is weakly preferred to its paired truthful type, with strict improvement on positive mass.
Let \(C\) be a nonempty set of \(m\) colleges. A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types. Each college has a fixed positive binary-rational capacity \(\kappa_c\), with no restriction on their sum. Let \(L\) be the total input bit length.
Each type has a strict complete ranking of colleges, and each college has a strict complete true ranking of types; its priority positions are those induced by this ranking. All colleges are preferable to being unmatched, and all types are preferable to a vacant seat. Mass within a type is indistinguishable and divisible.
Run student-proposing mass DA in synchronous rounds: initially all mass proposes to its favorite college; subsequently each rejected portion proposes to its next untried college. Each college retains its highest-ranked mass among its previous holdings and new proposals up to capacity, splitting mass within the cutoff type when necessary. Portions exhausting their lists remain unmatched; stop when no further proposals occur.
A designated college \(c^\star\) may report any strict complete ranking of \(T\), uniformly for all mass of each type; capacities and all other rankings remain fixed. Compare its resulting bundle with its truthful bundle, padding each to \(\kappa_{c^\star}\) with vacant seats. A manipulation is beneficial precisely when a mass-preserving coupling pairs every new occupant with a weakly worse truthful occupant under the true ranking, and strictly better pairs carry positive mass.
Is deciding whether \(c^\star\) has a beneficial manipulation under student-proposing mass DA solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite individual students, deciding beneficial manipulation by one college through a complete ranking report, with strict rankings, fixed capacities, and responsive dominance, is polynomial-time solvable ([Aziz, Seedig, and von Wedel](https://cgi.cse.unsw.edu.au/~haziz/damanip.pdf)). No result settling the exact mass decision problem above was identified in the literature search.
The original decision problem remains unresolved here. I prove a new structural result: in a family with two colleges, the masses attainable through beneficial reports are exactly certain subset sums, despite divisibility of mass.
Consequently, requiring a beneficial manipulation to achieve a specified positive improvement is $\mathrm{NP}$-complete, even with two colleges and dyadic input masses. However, deciding whether *any* beneficial manipulation exists is polynomial-time solvable on this family. Thus the hardness result does not settle the original question.
I also give a self-contained justification of the polynomial verification result from the notes, including the precise stable-allocation comparison needed for that argument.
Order the types according to the designated college’s true ranking:
$$ t_1\succ t_2\succ\cdots\succ t_\tau. $$
Treat a vacancy as rank $\tau+1$. Let $x_i$ and $y_i$ denote the new and truthful masses at rank $i$, including vacancies, so that both vectors sum to $\kappa_{c^\star}$.
Lemma 1. The new bundle is beneficial exactly when
$$ \sum_{i=1}^{k}x_i\geq\sum_{i=1}^{k}y_i \qquad \text{for every }1\leq k\leq\tau, $$
with strict inequality for at least one $k$.
Proof. A weakly improving coupling is a nonnegative matrix $\gamma$ with row sums $x_i$, column sums $y_j$, and $\gamma_{ij}=0$ for $i>j$. Therefore
$$ \sum_{i=1}^{k}x_i-\sum_{j=1}^{k}y_j = \sum_{i\leq k<j}\gamma_{ij}\geq0. $$
Every positive entry with $i<j$ contributes to some strict prefix inequality.
Conversely, arrange each bundle in increasing rank order along an interval of length $\kappa_{c^\star}$, giving rank $i$ an interval of length $x_i$ or $y_i$. Couple equal interval coordinates. The prefix inequalities imply that the new rank is at most the truthful rank, except at interval boundaries. If the inequality at $k$ is strict, the interval
$$ \left( \sum_{i=1}^{k}y_i,\, \sum_{i=1}^{k}x_i \right) $$
has positive length and pairs new ranks at most $k$ with truthful ranks greater than $k$. This is the required beneficial coupling. $\square$
Fix all reported rankings. Write $P_{tc}$ for cumulative proposed mass, $H_{tc}$ for current holdings, and $R_{tc}=P_{tc}-H_{tc}$ for cumulative rejected mass.
Lemma 2. At every round boundary, a college holds its highest-ranked mass among all cumulative proposals, up to capacity.
Proof. For a priority prefix, suppose cumulative proposals before the round have mass $p$, and new proposals have mass $a$. If the previous holdings contain $\min(\kappa_c,p)$ from this prefix, the updated holdings contain
$$ \min\!\left(\kappa_c,\min(\kappa_c,p)+a\right) = \min(\kappa_c,p+a). $$
Induction gives the assertion for every prefix. Differences between consecutive prefix totals determine each type’s holdings. $\square$
In particular,
$$ R_{tc} = \min\!\left( P_{tc}, \max\!\left( 0,\, P_{tc}+\sum_{s\succ_c t}P_{sc}-\kappa_c \right) \right). $$
Thus positive rejection of $t$ implies that $c$ holds its entire capacity in types ranked at least as highly as $t$.
For completeness, the specified synchronous procedure terminates. Choose a common denominator $D_0$ for all input masses and capacities. Every quantity remains a multiple of $1/D_0$. Each portion proposes to each college at most once, so total proposed mass is at most $m$. Every nonempty round proposes at least $1/D_0$ mass. Hence there are at most $mD_0$ nonempty rounds. This bound establishes termination, not polynomial running time.
A feasible allocation $z$ satisfies
$$ z_{tc}\geq0,\qquad \sum_c z_{tc}\leq\mu_t,\qquad \sum_t z_{tc}\leq\kappa_c. $$
For the fixed reported rankings, call $z$ stable if, for every $(t,c)$, at least one of the following equalities holds:
$$ \sum_{d\succeq_t c}z_{td}=\mu_t, \qquad \sum_{s\succeq_c t}z_{sc}=\kappa_c. $$
Failure of both equalities means that some mass of $t$ wants a better assignment at $c$, while $c$ has a vacancy or holds worse-ranked mass.
Write type $t$’s college ranking as
$$ c_1\succ_t\cdots\succ_t c_m. $$
At termination, cumulative proposals and rejections satisfy
$$ P_{t c_1}=\mu_t,\qquad P_{t c_{k+1}}=R_{t c_k}. $$
Since $H=P-R$, telescoping gives
$$ \sum_{j=1}^{k}H_{t c_j} = \mu_t-R_{t c_k}. $$
If this prefix is smaller than $\mu_t$, then $R_{t c_k}>0$; Lemma 2 fills $c_k$ with types ranked at least as highly as $t$. Thus the final DA allocation is stable.
Lemma 3. For every stable allocation $z$, at every round boundary,
$$ R_{t c_k} \leq \mu_t-\sum_{j=1}^{k}z_{t c_j}. $$
Proof. Induct on rounds. Before proposals, all rejections are zero and the asserted right-hand sides are nonnegative.
At the next round boundary, the induction hypothesis implies
$$ P_{t c_k} \leq \mu_t-\sum_{j<k}z_{t c_j}. $$
For the first choice this follows from $P_{t c_1}=\mu_t$. For later choices, cumulative proposals equal the preceding choice’s cumulative rejections through the previous round.
Suppose the rejection bound fails at $(t,c)$. Combining that failure with the proposal bound gives
$$ H_{tc}=P_{tc}-R_{tc}<z_{tc}. $$
The failed bound also implies $R_{tc}>0$. Lemma 2 consequently gives
$$ \sum_{s\succ_c t}P_{sc}+H_{tc}\geq\kappa_c. $$
Hence
$$ \sum_{s\succ_c t}P_{sc}+z_{tc}>\kappa_c. $$
Feasibility of $z$ implies that some $s\succ_c t$ satisfies $P_{sc}>z_{sc}$. The proposal bound for this $s$ yields
$$ \sum_{d\succeq_s c}z_{sd} \leq \mu_s-P_{sc}+z_{sc} < \mu_s. $$
Moreover, $z_{tc}>H_{tc}\geq0$, and $t$ is below $s$ at $c$. Therefore
$$ \sum_{u\succeq_c s}z_{uc} \leq \kappa_c-z_{tc} < \kappa_c. $$
Both stability equalities fail for $(s,c)$, a contradiction. $\square$
At termination, Lemma 3 gives
$$ \sum_{j=1}^{k}H_{t c_j} \geq \sum_{j=1}^{k}z_{t c_j} $$
for every stable $z$, every type, and every college-preference prefix.
I use the following established result. For strict preferences, positive vertex quotas, and nonnegative edge bounds, a row-optimal stable allocation can be computed with polynomially many arithmetic operations. The row comparison is
$$ x\succeq_i y \quad\Longleftrightarrow\quad x_{ik}<y_{ik} \ \Longrightarrow\ x_{ij}=0 \text{ for every }j\prec_i k. $$
Stable allocations have equal totals in each row. The applicable results are Lemma 8, Theorem 10, Theorem 2, and Corollary 4 of [Baïou–Balinski’s corrected stable-allocation paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302); no nondegeneracy hypothesis is needed.
Here is the lexicographic consequence explicitly. Suppose $x\succeq_i y$ and their row vectors differ. If the first differing coordinate, read from best to worst, had $x_{ik}<y_{ik}$, equality of row totals would require a later coordinate with $x_{ij}>y_{ij}$. But then $x_{ij}>0$ at a college worse than $k$, contradicting the displayed comparison. Thus $x$ is lexicographically better than $y$.
Apply the algorithm with row vertices $T$, column vertices $C$, row quotas $\mu_t$, column quotas $\kappa_c$, and edge bounds $\mu_t$. All hypotheses hold. The edge bounds add no restriction beyond row feasibility. A saturated edge already saturates its row prefix, so the algorithm’s stability condition agrees with Section 3.1.
Let $Y$ be its row-optimal output and $H$ the synchronous DA outcome. Both are stable. Lemma 3 says that $H$ dominates $Y$ in every row prefix. If a row differed, its first differing coordinate would favor $H$. Row optimality and the preceding lexicographic argument give the opposite conclusion. Therefore $Y=H$.
The algorithms use additions, subtractions, comparisons, and minima. Their quantities remain on the common-denominator grid, with polynomial bit length: the product of the input denominators has bit length at most their combined encoding length. Thus a fixed report is evaluable in polynomial time in $m,\tau,L$.
Corollary 4. The original manipulation problem belongs to $\mathrm{NP}$.
Proof. A certificate is a permutation of the $\tau$ support types. Evaluate its outcome and the truthful outcome in polynomial time, then apply Lemma 1. $\square$
Enumeration also gives an exact $\tau!\,\mathrm{poly}(m,\tau,L)$ algorithm.
Let $a_1,\ldots,a_n,b$ be positive integers, and put
$$ w=\sum_{i=1}^{n}a_i. $$
Choose a power of two $D>w+2b$, and define
$$ f=D-w-2b>0. $$
There are two colleges, $A=c^\star$ and $B$, with capacities
$$ \kappa_A=\frac{w}{D}, \qquad \kappa_B=\frac{b+f}{D}. $$
The support consists of $n+3$ types:
| Type | Mass | College preferences |
|---|---:|---|
| $x_i$, for $1\leq i\leq n$ | $a_i/D$ | $A\succ B$ |
| $u$ | $b/D$ | $A\succ B$ |
| $s$ | $b/D$ | $B\succ A$ |
| $d$ | $f/D$ | $B\succ A$ |
All masses are positive dyadic rationals and sum to one. True rankings are
$$ A:\quad s\succ x_1\succ\cdots\succ x_n\succ u\succ d, $$
$$ B:\quad d\succ x_1\succ\cdots\succ x_n\succ s\succ u. $$
Type $d$ is permanently held at $B$: it proposes there initially, ranks first, and its mass is smaller than $B$’s capacity. It reserves $f/D$ capacity, leaving effective capacity $b/D$ for the other types.
Truthful DA assigns all $x_i$ mass to $A$, assigns all $s$ and $d$ mass to $B$, and leaves $u$ unmatched. Indeed, $A$ initially retains precisely the $x_i$ types, while $B$ retains $s,d$ and rejects the subsequent proposals of $u$.
For the proof below, multiply all masses and capacities by $D$. This preserves every DA choice because additions and minima commute with positive scaling.
Theorem 5. Every beneficial report in the family above has, for some nonempty subset $J\subseteq\{1,\ldots,n\}$ with
$$ S=\sum_{i\in J}a_i\leq b, $$
the final bundle
$$ H_{x_i A} = \begin{cases} 0,&i\in J,\\ a_i/D,&i\notin J, \end{cases} \qquad H_{sA}=\frac{S}{D}, \qquad H_{uA}=H_{dA}=0. $$
Conversely, every such subset is attained by a beneficial strict complete report.
Work in scaled units. College $A$ is full after the first round, since it receives total mass $w+b$ against capacity $w$. It remains full thereafter: each update chooses from previous holdings of mass $w$ together with new proposals.
Type $d$ never proposes to $A$. Let final masses at $A$ be $h_i$ of $x_i$, $z$ of $s$, and $v$ of $u$. Then
$$ \sum_i h_i+z+v=w. $$
The true prefix $\{s,x_1,\ldots,x_n\}$ has truthful mass $w$. Lemma 1 therefore forces $v=0$ in any beneficial outcome.
Such an outcome also has $z>0$. Otherwise, $\sum_i h_i=w=\sum_i a_i$ and $h_i\leq a_i$ force $h_i=a_i$ for every $i$, giving the truthful bundle.
All $b$ units of $u$ proposed to $A$ initially. Since none is held finally, Lemma 2 implies that every final occupant is reported above $u$. In particular, $s$ is reported above $u$.
Define
$$ U=\{i:x_i\text{ is reported above }u\}, \qquad M=\sum_{i\in U}a_i, \qquad S=w-M. $$
Every $x_i$ outside $U$ has final holding zero. Since $z\leq b$,
$$ w=\sum_{i\in U}h_i+z\leq M+b, $$
so $S\leq b$.
Also $S>0$. If $S=0$, all $x_i$ types are reported above $u$. The first round retains all of them and rejects all $u$. At $B$, rejected $u$ cannot displace $s$. No $s$ reaches $A$, contradicting $z>0$.
Now $M=w-S<w$ and $S\leq b$. In the first round, $A$ therefore retains every type in $U$ in full, followed by exactly $S$ units of $u$. It rejects every $x_i$ outside $U$ in full.
Those rejected $x_i$ have total mass $S$. Their proposals to $B$ displace exactly $S$ units of $s$, since all $x_i$ rank above $s$ there. Proposals of $u$ are rejected and have no effect.
The $S$ units of $s$ then propose to $A$. Every type in $U$, and also $s$, is reported above $u$. Their combined mass is exactly
$$ M+S=w. $$
Hence $A$ retains precisely those types and rejects its remaining $u$. Subsequent $u$ proposals are rejected at $B$. This proves the asserted final bundle, with $J$ the complement of $U$.
Let $J$ be nonempty and satisfy $S=\sum_{i\in J}a_i\leq b$. Report
$$ s \succ \{x_i:i\notin J\} \succ u \succ \{x_i:i\in J\} \succ d, $$
using any strict order inside the displayed groups.
Initially, $A$ retains all unselected $x_i$ and $S$ units of $u$, rejecting the selected $x_i$ in full. Their proposals displace $S$ units of $s$ at $B$. That mass of $s$ reaches $A$ and replaces the held $u$.
The resulting bundle retains every unselected type and replaces all selected mass by the truly best type $s$. Couple each retained type to itself and the $S/D$ units of $s$ to the removed selected types. Every pair weakly improves, and the latter pairs strictly improve with positive mass. $\square$
Thus divisibility does not permit fractional selection in a beneficial outcome of this family: every replaced $x_i$ is replaced in full.
Consider the following strengthened decision problem:
Given the original instance and a positive rational threshold $\eta$, is there a beneficial report that assigns at least $\eta$ mass of the designated college’s truly first-ranked type?
Theorem 6. This prescribed-improvement problem is $\mathrm{NP}$-complete, even with two colleges and dyadic masses and capacities.
Proof. Membership in $\mathrm{NP}$ follows from Section 3, with one additional rational comparison.
For hardness, use positive binary-encoded $\mathrm{SUBSET\ SUM}$: given positive integers $a_1,\ldots,a_n,b$, decide whether some subset sums to $b$. This standard problem is $\mathrm{NP}$-complete; see [Karp, “Reducibility among Combinatorial Problems”](https://doi.org/10.1007/978-1-4684-2001-2_9).
Construct the family of Section 4 and set
$$ \eta=\frac{b}{D}. $$
Theorem 5 shows that a beneficial report attains at least $\eta$ mass of the first-ranked type $s$ exactly when some nonempty subset satisfies
$$ b\leq\sum_{i\in J}a_i\leq b, $$
which is precisely the subset-sum condition.
The reduction has polynomial encoding length. Choose $D$ as the smallest power of two strictly exceeding $w+2b$. Then $D$, $f$, every rational numerator and denominator, and all rankings have polynomial encoding length in the source input. The support size is $n+3$, and there are exactly two colleges. $\square$
A corresponding optimization consequence is immediate. Define
$$ V= \max\{H_{sA}: \text{the reported outcome weakly dominates the truthful bundle}\}. $$
The truthful report makes this set nonempty. Theorem 5 gives
$$ V = \frac{1}{D} \max\left( \{0\} \cup \left\{ \sum_{i\in J}a_i: \varnothing\neq J\subseteq\{1,\ldots,n\}, \ \sum_{i\in J}a_i\leq b \right\} \right). $$
Therefore computing $V$ exactly is $\mathrm{NP}$-hard, already on this two-college family.
For the original existence question, Theorem 5 yields the much simpler criterion
$$ \text{a beneficial report exists} \quad\Longleftrightarrow\quad \min_i a_i\leq b. $$
Indeed, every positive subset sum at most $b$ contains an individual summand at most $b$; conversely, that individual type supplies a beneficial singleton manipulation.
For example, with $a_1=a_2=2$ and $b=3$, no subset sums to $3$, but replacing either one of the two types produces a beneficial manipulation.
Thus the construction separates *finding any improvement* from *achieving a prescribed improvement*. Its optimization hardness cannot be transferred to the original decision problem without an additional argument.
The exact task remains to classify the existence of any beneficial uniform type report. The proved results establish polynomial verification and expose discrete subset choices within divisible DA, but they supply neither a polynomial search algorithm for general instances nor a hardness reduction for the original existence question.
⟨structured verdict parsed — rendered above⟩
The output establishes valid partial results, but it does not resolve USER_TASK. I found no false central step in the structural characterization or the reduction. The decisive limitation is explicit: the hardness result concerns a stronger threshold problem, while the original existence question remains open.
Including vacancies makes both bundle vectors have total mass $\kappa_{c^\star}$. The coupling matrix has the correct orientation: $\gamma_{ij}$ pairs a new occupant of rank $i$ with a truthful occupant of rank $j$, and weak improvement requires $i\leq j$.
The displayed prefix identity follows from the row and column sums and the absence of entries with $i>j$. A strictly improving pair crosses at least one prefix boundary, so positive mass of strictly improving pairs implies a strict prefix inequality.
Conversely, the interval construction produces a mass-preserving coupling. Prefix dominance ensures the new rank is no worse at almost every coordinate. A strict prefix inequality provides a positive-length interval of strictly improved pairs.
Vacancies, zero coordinates, and bundles with identical masses are handled correctly. There is no gap here.
For any college priority prefix, its retained mass after an update is the minimum of capacity and the mass from that prefix available in previous holdings and new proposals. The induction therefore establishes that current holdings equal the highest-priority mass from cumulative proposals.
The rejection formula correctly covers all three possibilities: no rejection, partial rejection at the cutoff, and complete rejection below the cutoff. In particular, positive rejection of a type implies that the college is full with types ranked at least as highly as that type.
The termination argument is valid for rational inputs. Additions, subtractions, and capacity cutoffs preserve the common-denominator grid. Total cumulative proposed mass is at most $m$, and a nonempty round proposes at least $1/D_0$ mass. Thus the bound $mD_0$ follows.
The prover correctly distinguishes finite termination from polynomial running time: $D_0$ can be exponentially large in its bit length.
The stated stability condition matches the divisible model. Failure of the type-prefix equality means positive mass is unmatched or assigned below the college; failure of the college-prefix equality means positive capacity is vacant or occupied by lower-ranked types. Together these permit a blocking transfer.
At termination, the cumulative proposal identities and telescoping calculation are valid. Positive rejection at a college supplies the college-side stability equality through Lemma 2.
The induction in Lemma 3 also checks out:
This contradicts stability of $z$. The resulting dominance of DA over every stable allocation in every type-preference prefix is established.
I checked the [corrected Baïou–Balinski paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302). Its row comparison agrees with the displayed definition. Lemma 8 gives equal row totals across stable allocations; Theorem 2 bounds the inductive algorithm; Theorem 10 establishes the optimal stable allocations; and Corollary 4 bounds the row-optimal algorithm. These results do not require nondegeneracy.
The application satisfies the hypotheses: both vertex quotas are positive, preferences are strict, and edge bounds are nonnegative. Setting each edge bound to $\mu_t$ adds no feasibility restriction. An edge at that bound already satisfies its row-prefix equality, so the two stability definitions agree.
The lexicographic consequence is valid. If the first differing coordinate favored $y$, equal row totals would require a later positive excess in $x$, contradicting the stated row comparison.
Consequently, row optimality of $Y$ and prefix dominance of $H$ force $Y=H$. The rational-arithmetic argument supports polynomial bit complexity for these algorithms: their allocation quantities are bounded by the input quotas and remain on the common-denominator grid.
Thus polynomial evaluation of a fixed report, membership of the original problem in $\mathrm{NP}$, and the exhaustive $\tau!\,\mathrm{poly}(m,\tau,L)$ algorithm are valid partial results. They do not establish polynomial-time search over reports.
On the intended nonempty source list, $w>0$, so both capacities are positive. The choice $D>w+2b$ gives $f>0$, and total mass is
$$ \frac{w+2b+f}{D}=1. $$
All masses and capacities are dyadic rationals. Rankings are strict and complete.
Type $d$ remains entirely at $B$, leaving effective capacity $b/D$. The truthful outcome is correctly described: $A$ holds all $x_i$, $B$ holds $s$ and $d$, and $u$ is unmatched.
Scaling by $D$ preserves the update operations and hence the DA outcome.
The necessity argument establishes each claimed restriction:
With $0<S\leq b$, the subsequent round calculations are exact: $A$ initially holds all types above $u$ and $S$ units of $u$; the rejected types displace exactly $S$ units of $s$ at $B$; those units then replace the held $u$ at $A$. No further proposal changes that bundle.
The sufficiency report is strict and complete after ordering within the groups. Its stated execution and beneficial coupling are valid.
Therefore the claimed whole-type subset selection is established despite divisibility.
The strengthened threshold problem has polynomial verification by Section 3. The reduction uses the standard positive, binary-encoded subset-sum problem.
Setting $\eta=b/D$, Theorem 5 imposes both
$$ \sum_{i\in J}a_i\geq b \qquad\text{and}\qquad \sum_{i\in J}a_i\leq b. $$
Hence a successful threshold report exists exactly when a subset sums to $b$. Because $b>0$, any such subset is nonempty.
The construction has polynomial encoding length, including the rankings and the power-of-two denominator. Cases such as $b>w$ correctly produce no successful threshold report.
The optimization formula also follows: a weakly dominating bundle either equals the truthful bundle or is beneficial, by Lemma 1. Thus Theorem 5 covers every positive objective value, while the truthful report supplies value zero.
These establish hardness of the threshold and exact optimization problems.
The family gives
$$ \text{a beneficial report exists} \quad\Longleftrightarrow\quad \min_i a_i\leq b. $$
This is a polynomial-time criterion. The example $a_1=a_2=2$, $b=3$ correctly demonstrates why the subset-sum reduction does not classify the original question: beneficial manipulation exists even though the required exact subset sum does not.
Minimum additional work required: supply either a polynomial-time algorithm for beneficial-report existence on general inputs, or a hardness reduction whose success condition is existence of any beneficial report. This requires a substantive new argument, not clarification of the current proof. The prover acknowledges that limitation accurately.
⟨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.