Answer: —
Theorem 4.1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAdd Capacity To Match Pair can be solved in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_w\), finite firms \(F\), capacities \(q_f\), worker-type and firm-type preferences, target type-firm pair \((w^\star,f^\star)\), target mass \(0<\delta\le\mu_{w^\star}\), and budget \(\ell\), decide whether there exist \(\Delta_f\ge0\) and a mass matching \(x\) that is stable under capacities \(q_f+\Delta_f\), satisfies \(\sum_f\Delta_f\le\ell\), and assigns at least \(\delta\) mass of type \(w^\star\) to \(f^\star\).
An instance has finite worker types \(A\) with rational masses \(\mu_a\), finite firms \(F\), rational capacities \(q_f\), and strict preferences of every type over \(F\cup\{\emptyset\}\) and of every firm over \(A\cup\{\emptyset\}\). A matching flow is a nonnegative matrix \(\pi\) with \(\sum_f\pi_{a,f}\le\mu_a\) and \(\sum_a\pi_{a,f}\le q_f+\delta_f\); residual type mass is unmatched.
A type--firm pair \((a,f)\) blocks \(\pi\) if some \(\varepsilon>0\) mass of \(a\) is unmatched or assigned below \(f\), and \(f\) can take \(\varepsilon\) mass of \(a\) by using vacant capacity that it prefers to leave empty or by replacing \(\varepsilon\) mass of types ranked below \(a\). A flow is stable if no such pair blocks it.
Is the continuous Budgeted Add Capacity to Match Pair problem NP-hard, or solvable in polynomial time?
For finite individual workers and integer capacities, the corresponding problem with a global seat-addition budget and per-firm addition budgets is NP-hard.
If only the global budget is imposed in that finite setting, the corresponding pair-matching problem is solvable in polynomial time.
The stated problem does not yet determine a unique decision problem, and the nearest discrete results do not by themselves settle the natural continuous version.
In particular, the statement does not specify:
The distinction in item 3 is substantive. Consider one type \(a\) of mass \(1\), one mutually acceptable firm \(f\) with \(q_f=0\), and both global and individual budgets equal to \(1/2\). The flow
\[ \delta_f=\pi_{a,f}=\frac12 \]
is stable: \(f\) is saturated and employs no type ranked below \(a\). Thus \((a,f)\) is matched with positive mass, but the entire type cannot be matched to \(f\).
I therefore analyze the following standard completion.
The input additionally contains:
We ask whether there are additions and a stable flow satisfying
\[ 0\leq\delta_f\leq b_f,\qquad \sum_f\delta_f\leq B,\qquad \pi_{a^\star,f^\star}>0. \]
Let
\[ L_f=\sum_{a\in A}\pi_{a,f} \]
be the load of firm \(f\), and regard residual mass as assignment to \(\emptyset\):
\[ \pi_{a,\emptyset}=\mu_a-\sum_{f\in F}\pi_{a,f}. \]
For a type-firm pair define
\[ W_{a,f} = \sum_{\substack{g\in F\cup\{\emptyset\}\\ f\succ_a g}} \pi_{a,g} \]
and
\[ D_{a,f} = \sum_{\substack{b\in A\\ a\succ_f b}} \pi_{b,f}. \]
Thus \(W_{a,f}\) is the amount of type \(a\) that would prefer \(f\), while \(D_{a,f}\) is the amount currently employed at \(f\) that \(f\) ranks below \(a\).
At capacities \(c_f=q_f+\delta_f\), the pair \((a,f)\) blocks \(\pi\) if and only if
\[ W_{a,f}>0 \]
and at least one of the following holds:
\[ D_{a,f}>0, \]
or
\[ a\succ_f\emptyset \quad\text{and}\quad L_f<c_f. \]
If \(W_{a,f}>0\), some positive amount of type \(a\) is assigned below \(f\). If \(D_{a,f}>0\), choose
\[ 0<\varepsilon\leq\min\{W_{a,f},D_{a,f}\}. \]
Firm \(f\) can replace \(\varepsilon\) mass ranked below \(a\). Alternatively, if \(f\) has acceptable vacant capacity, choose
\[ 0<\varepsilon \leq \min\{W_{a,f},c_f-L_f\}. \]
In either case \((a,f)\) blocks.
Conversely, any blocking deviation needs positive type-\(a\) mass that prefers \(f\), giving \(W_{a,f}>0\). The firm must obtain room either by replacing positive mass ranked below \(a\), giving \(D_{a,f}>0\), or by using acceptable vacant capacity. These are exactly the stated alternatives. \(\square\)
Consequently, stability is equivalent, for every \((a,f)\), to the disjunction
\[ W_{a,f}=0 \]
or
\[ D_{a,f}=0 \quad\text{and}\quad \bigl(\emptyset\succ_f a\ \text{or}\ L_f=q_f+\delta_f\bigr). \]
Suppose \((\pi,\delta)\) is feasible and stable. Define
\[ \widehat{\delta}_f = \max\{0,L_f-q_f\}. \]
Then \((\pi,\widehat{\delta})\) is feasible and stable, and
\[ 0\leq\widehat{\delta}_f\leq\delta_f \]
for every firm.
Feasibility of the original solution gives
\[ L_f\leq q_f+\delta_f. \]
Hence \(L_f-q_f\leq\delta_f\), so \(\widehat{\delta}_f\leq\delta_f\). Moreover,
\[ q_f+\widehat{\delta}_f=\max\{q_f,L_f\}\geq L_f, \]
so \(\pi\) remains capacity-feasible. All budget constraints remain satisfied because additions only decrease.
Suppose a pair blocked after replacing \(\delta\) by \(\widehat{\delta}\). Its worker-side condition and the set of replaceable lower-ranked masses are unchanged. If the block uses vacant capacity, then
\[ L_f<q_f+\widehat{\delta}_f\leq q_f+\delta_f, \]
so the same vacancy existed before the reduction. Therefore the pair would also have blocked the original solution, contradicting stability. \(\square\)
The additions can be eliminated from the formulation. A flow \(\pi\) is realizable within the budgets if and only if
\[ L_f\leq q_f+b_f \]
for every \(f\),
\[ \sum_f\max\{0,L_f-q_f\}\leq B, \]
and, for every \((a,f)\),
\[ W_{a,f}=0 \]
or
\[ D_{a,f}=0 \quad\text{and}\quad \bigl(\emptyset\succ_f a\ \text{or}\ L_f\geq q_f\bigr). \]
Thus capacity addition is exactly controlled overfilling relative to the original capacities.
Under the standard rational formalization above, the continuous problem belongs to \(\mathrm{NP}\). More explicitly, it can be solved by at most \(2^{|A||F|}\) rational linear programs.
For every pair \((a,f)\), guess which side of the stability disjunction is used.
All these are linear constraints.
Introduce variables \(y_f\) and impose
\[ y_f\geq0,\qquad y_f\geq L_f-q_f,\qquad y_f\leq b_f,\qquad \sum_f y_f\leq B. \]
Together with \(L_f\leq q_f+b_f\), these constraints are feasible exactly when the total canonical addition is at most \(B\).
For the guessed branch vector, maximize \(\pi_{a^\star,f^\star}\) subject to these constraints and the matching-flow constraints. This is a rational linear program. The branch is successful precisely when its optimum is positive.
There are \(2^{|A||F|}\) branch vectors. Moreover, if one branch has a point with positive target flow, maximizing the target coordinate yields a positive rational basic feasible solution whose encoding length is polynomially bounded in the input length. The branch vector together with this rational solution is therefore an \(\mathrm{NP}\) certificate. \(\square\)
This result also shows that allowing arbitrary real rather than rational solutions does not enlarge the set of yes-instances under this formalization.
The known discrete result proves that the budgeted integer-capacity problem is \(\mathrm{NP}\)-hard, while the global-budget-only version is polynomial-time solvable [Gokhale–Narang–Singla–Vaish](https://arxiv.org/abs/2402.04645). Its hardness reduction represents an addable man by a firm with capacity \(0\) and individual addition budget \(1\). Hence adding one integer seat is a binary activation.
That argument is invalid for divisible capacities.
For any \(m\), take mutually isolated pairs \((a_i,f_i)\), where:
Set
\[ \delta_{f_i}=\pi_{a_i,f_i}=\frac1m \]
for every \(i\). Every \(f_i\) is saturated and holds no type ranked below \(a_i\), so the flow is stable. Thus all \(m\) zero-capacity firms are simultaneously active with positive flow under global budget \(1\). With integer additions, at most one of them could be activated.
Therefore the binary selection correspondence used by the discrete reduction is lost. This does not prove polynomial-time solvability, but it rules out the immediate hardness transfer.
For fixed capacities, the underlying divisible problem is the classical stable-allocation problem, which has a strongly polynomial algorithm [Baïou–Balinski](https://doi.org/10.1287/moor.27.3.485.310). The unresolved issue is whether the special disjunctive system in Corollary 3 retains enough stable-allocation structure for polynomial optimization, or can encode an \(\mathrm{NP}\)-hard selection problem despite divisibility.
No rigorous classification as either \(\mathrm{NP}\)-hard or polynomial-time solvable follows from the premises given.
What is proved here is:
A complete classification requires either a polynomial algorithm exploiting the nested prefix structure of \(W_{a,f}\) and \(D_{a,f}\), or a new hardness construction robust to arbitrarily small positive capacity additions.
⟨structured verdict parsed — rendered above⟩
The output establishes several correct structural facts for one chosen formalization, but it does not answer the target question of whether the continuous problem is polynomial-time solvable or NP-hard. Its own characterization as “partial” is accurate.
The substantive progress is:
None of these results classifies the continuous problem.
The missing global budget, per-firm budgets, designated pair, and precise meaning of “matching the pair” are genuine omissions from USER_TASK. The example distinguishing positive flow from full matching is correct: with mass \(1\), capacity addition \(1/2\), and flow \(1/2\), the remaining mass cannot block because the firm is saturated and employs no type below \(a\).
However, the proposed “standard completion” does not resolve the output’s own item 4. It never states whether assignments below \(\emptyset\) are forbidden. As written, its matching-flow constraints permit them. This does not visibly invalidate Lemmas 1–2 or Proposition 4, but it means the claimed completed decision problem remains formally incomplete.
The formalization also should state that \(B\) and all \(b_f\) are nonnegative and how rational data are encoded.
The forward implication is correct:
The reverse implication is also correct relative to the blocking definition in USER_TASK: any permitted block must use either lower-ranked incumbent mass or acceptable vacant capacity.
The resulting stability disjunction is the correct negation of the blocking conditions, using capacity feasibility \(L_f\leq q_f+\delta_f\) and strict preferences between \(a\) and \(\emptyset\).
The canonical addition
\[ \widehat{\delta}_f=\max\{0,L_f-q_f\} \]
is capacity-feasible and coordinatewise no larger than \(\delta_f\). Reducing capacity cannot create new replacement opportunities, and any vacancy remaining after the reduction was already present before it. The stability argument is correct.
The budget elimination is correct:
The phrase “a flow is realizable” should explicitly retain all matching-flow constraints and the selected convention concerning unacceptable assignments.
The branch enumeration correctly linearizes the stability disjunction. The auxiliary constraints on \(y_f\) correctly represent values at least as large as \(\max\{0,L_f-q_f\}\); since the objective does not reward larger \(y_f\), their existence is equivalent to the canonical global-budget inequality.
Maximizing \(\pi_{a^\star,f^\star}\) is a valid way to decide the strict positive-flow condition without putting a strict inequality into the linear program.
The \(\mathrm{NP}\)-membership argument is sound in substance: a nonempty rational-polyhedral branch with positive optimal target coordinate has a polynomial-bit rational certificate. It should explicitly specify binary encoding of the rational input, but that is a routine representational clarification.
The claim that allowing real feasible solutions creates no additional yes-instances follows from the same rational-polyhedral argument.
The cited discrete paper does use capacity-\(0\), individual-budget-\(1\) firms to encode addable agents, so the description of that reduction is accurate [Capacity Modification in the Stable Matching Problem](https://arxiv.org/html/2402.04645v3).
The isolated-pair calculation is correct: assigning \(1/m\) to each of \(m\) mutually isolated acceptable pairs saturates every modified firm and consumes total budget \(1\). Thus positive fractional capacity does not behave as a binary activation.
This establishes only that the cited reduction’s binary correspondence is unavailable verbatim. It does not rule out all adaptations of that reduction or prove anything about the ultimate hardness of the continuous problem. The prover correctly acknowledges that limitation.
The Baïou–Balinski paper does state a strongly polynomial algorithm for the stable-allocation problem. However, the output does not precisely state that theorem’s model and hypotheses or formally identify the present fixed-capacity model with it. This is an ancillary contextual claim rather than a step supporting Proposition 4 or the final partial conclusion. The cited DOI also points to the originally printed version for which a corrected erratum exists.
The conclusion accurately summarizes the partial results. It expressly leaves the central complexity classification unresolved. Therefore it does not fulfill the target, even though its claimed partial progress is largely correct.
For the existing partial results to be fully verifiable as statements about a single decision problem, the prover must specify:
These clarifications would not resolve the main missing classification. A polynomial-time algorithm or a valid continuous hardness reduction remains necessary.
⟨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.