Answer: \(\mathrm{P}\): every valid instance admits a feasible \(1\)-stable mass allocation.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any constant α > 1, distinguishing whether a given market has a 1-stable matching or has no α-stable matching is NP-complete. We prove the NP-completeness by reducing from the sub- set sum problem (Garey and Johnson 1979), though details are omitted due to space limitations. Furthermore, to obtain an approximately stable matching, the amount of approximation does not fall 1 1−s, where s in- dicates the largest wage size among the given contracts, i.e., s = maxx∈X s(x).
statement extracted from the paper’s text layer; consult the paper for the exact wording
For fixed \(\alpha>1\), given hospitals \(H\), a finite support \(T\) of doctor types with rational masses \(\mu_t\) summing to \(1\), and each type’s ranked contract options with rational per-capita budget uses \(\sigma_t(x)\) and hospital utilities \(u_t(x)\), distinguish whether a feasible mass allocation has no \(1\)-blocking deviation or whether every feasible mass allocation has an \(\alpha\)-blocking deviation. An allocation assigns masses \(y_{t,a}\) to each type’s options \(a\), with \(\sum_a y_{t,a}=\mu_t\) and each hospital’s total budget use at most \(1\); a blocking deviation reallocates eligible masses to contracts at one hospital, within its budget, and blocks when its utility exceeds \(\alpha\) times that hospital’s current utility.
A society is given by its support: the list of the \(\tau\) doctor types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) hospitals, each with budget \(1\). Each type \(t\) has an explicitly listed finite contract set \(X_t\) and a strict ranking \(\succ_t\) over \(A_t=X_t\cup\{\varnothing\}\), where \(\varnothing\) means unmatched. Multiple contracts with one hospital are allowed.
Each contract \(x\in X_t\) specifies its hospital \(h(x)\), nonnegative rational per-capita budget use \(\sigma_t(x)\), and nonnegative rational hospital utility \(u_t(x)\); budget uses need not be at most \(1\).
A feasible allocation has real masses \(y_{t,a}\geq0\), satisfies \(\sum_{a\in A_t}y_{t,a}=\mu_t\), assigns no mass to contracts below \(\varnothing\), and satisfies \(\sum_{t,x:h(x)=h}\sigma_t(x)y_{t,x}\leq1\) for every hospital. Write \(U_h(y)=\sum_{t,x:h(x)=h}u_t(x)y_{t,x}\).
A deviation at hospital \(h\) chooses real masses \(z_{t,a,x}\geq0\) from current option \(a\in A_t\) to contract \(x\in X_t\) with \(h(x)=h\), subject to \(\sum_{x:h(x)=h}z_{t,a,x}\leq y_{t,a}\). Positive mass is allowed only when \(x=a\) or \(x\succ_t a\).
These masses form the hospital's entire replacement roster: current masses may be retained or dismissed, and each mass is used at most once. Require \(\sum_{t,a,x:h(x)=h}\sigma_t(x)z_{t,a,x}\leq1\). For \(\beta\geq1\), the deviation is \(\beta\)-blocking exactly when \(\sum_{t,a,x:h(x)=h}u_t(x)z_{t,a,x}>\beta U_h(y)\); an allocation is \(\beta\)-stable if no such deviation exists.
Let \(K=\sum_t|X_t|\) and let \(L\) be the total binary input length; state running times in \(m,\tau,K,L\).
For each fixed rational \(\alpha>1\), is the promise problem of distinguishing existence of a feasible \(1\)-stable mass allocation from nonexistence of any feasible \(\alpha\)-stable mass allocation in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
The corresponding discrete promise problem is \(\mathrm{NP}\)-complete for every fixed \(\alpha>1\). [Kawase and Iwasaki](https://arxiv.org/pdf/1711.07359)
No result settling this exact mass promise problem was located in the literature search.
The promise problem is in \(\mathrm{P}\). In fact, every valid instance admits a feasible \(1\)-stable mass allocation. Consequently, the promised case of nonexistence of any feasible \(\alpha\)-stable allocation never occurs.
We prove this by subdividing each type into finitely many small doctors, establishing a bound against fractional deviations, and passing to a limit. The finite proposal rule uses the utility-density idea in [Kawase and Iwasaki, Algorithm 2](https://arxiv.org/pdf/1711.07359); the fractional bound and limiting argument are proved below.
Let \(\mathcal{Y}\) be the set of feasible mass allocations. For a hospital \(h\), define
\[ D_h(y)=\max_z\sum_{t,a,x:h(x)=h}u_t(x)z_{t,a,x}, \]
where \(z\) satisfies precisely the deviation constraints in the question.
This maximum exists: the feasible deviation set is nonempty, closed, and bounded, since each variable satisfies \(0\leq z_{t,a,x}\leq y_{t,a}\leq\mu_t\).
Retaining the hospital’s current roster is an admissible deviation. Specifically, set \(z_{t,x,x}=y_{t,x}\) for its current contracts and set all other variables to zero. Hence
\[ D_h(y)\geq U_h(y). \]
Thus \(y\) is \(1\)-stable exactly when \(D_h(y)=U_h(y)\) for every hospital.
We now prove continuity, including at allocations with zero coordinates. Let \(M_h\) be the largest per-capita utility of a contract at \(h\), taking \(M_h=0\) if no such contract exists. For feasible allocations \(y,y'\), take an optimal deviation \(z\) at \(y\). For each source option \((t,a)\) with \(y_{t,a}>0\), define
\[ z'_{t,a,x} = z_{t,a,x}\min\!\left\{1,\frac{y'_{t,a}}{y_{t,a}}\right\}. \]
If \(y_{t,a}=0\), set the corresponding variables to zero.
The source constraints hold at \(y'\). All allowed transitions remain allowed, and the budget use weakly decreases because all budget coefficients are nonnegative. The utility loss from source \((t,a)\) is at most \(M_h(y_{t,a}-y'_{t,a})_+\), where \(r_+=\max\{r,0\}\). Therefore
\[ D_h(y')\geq D_h(y)-M_h\sum_{t,a}(y_{t,a}-y'_{t,a})_+. \]
Interchanging \(y\) and \(y'\) gives
\[ |D_h(y)-D_h(y')| \leq M_h\sum_{t,a}|y_{t,a}-y'_{t,a}|. \]
In particular, \(D_h\) is continuous.
Consider a finite sequence of distinct items. Item \(i\) has cost \(c_i\geq0\) and value \(v_i\geq0\), with \(c_i\leq s<1\).
Fix a total priority order: zero-cost items come first; positive-cost items are ordered by decreasing \(v_i/c_i\), with ties broken consistently.
Process the items sequentially. Add each arriving item to the retained set, then repeatedly discard its lowest-priority item until the retained cost is at most \(1\). Discarded items are never restored. Write \(R\) for the final retained set.
Let \(F\) be the unrestricted fractional-knapsack optimum over all items that arrived:
\[ F=\max\left\{\sum_i v_iq_i: 0\leq q_i\leq1,\ \sum_i c_iq_i\leq1\right\}. \]
Lemma. The final retained value satisfies
\[ \sum_{i\in R}v_i\geq(1-s)F. \]
Proof. If the total cost of all items is at most \(1\), no discard occurs. All values are nonnegative, so retaining everything attains \(F\).
Otherwise, order all items by the fixed priority. Let \(P\) be the longest initial segment whose total cost is at most \(1\), and put
\[ C=\sum_{i\in P}c_i,\qquad V=\sum_{i\in P}v_i. \]
Every item in \(P\) remains retained. Indeed, suppose an item \(j\in P\) were discarded. At that moment, every other retained item precedes \(j\) in the fixed priority order. Their total cost together with \(c_j\) is therefore at most the cost of the final ordered prefix ending at \(j\), which is at most \(1\). This contradicts the condition for discarding \(j\).
Let \(b\) be the item immediately following \(P\). It has positive cost, and
\[ C+c_b>1,\qquad c_b\leq s. \]
Consequently, \(C>1-s>0\). Set \(\rho=v_b/c_b\).
All zero-cost items belong to \(P\). For items in \(P\), \(v_i-\rho c_i\geq0\); for items outside \(P\), \(v_i\leq\rho c_i\). Thus every feasible fractional vector \(q\) satisfies
\[ \sum_i v_iq_i \leq \rho\sum_i c_iq_i+\sum_{i\in P}(v_i-\rho c_i)q_i \leq \rho+V-\rho C. \]
Also \(V\geq\rho C\). Therefore
\[ F\leq V+\rho(1-C)\leq\frac{V}{C}\leq\frac{V}{1-s}. \]
Since \(P\subseteq R\) and values are nonnegative, the claimed inequality follows. \(\square\)
Define
\[ B=\max_{t,x\in X_t}\mu_t\sigma_t(x), \]
taking \(B=0\) if there are no contracts.
For each positive integer \(n>B\), replace type \(t\) by \(n\) distinct doctors, each representing mass
\[ \delta_t=\frac{\mu_t}{n}. \]
Each doctor has the type’s strict ranking and contract options. Its copy of contract \(x\) has cost \(\delta_t\sigma_t(x)\) and value \(\delta_tu_t(x)\). Every copied contract therefore has cost at most
\[ s_n=\frac{B}{n}<1. \]
Run the following finite procedure.
Only unmatched doctors propose. A discarded contract is never restored. Hence each doctor is held by at most one hospital throughout the procedure. Zero-cost contracts are never discarded: whenever the budget is exceeded, some positive-cost contract is present and has lower priority.
Each copied contract is proposed at most once, so the procedure terminates after at most \(nK\) proposals. Its terminal matching is feasible.
Aggregate the terminal matching into a mass allocation \(y^{(n)}\), giving each doctor its represented mass \(\delta_t\). This allocation is feasible for the original instance.
Two facts about a terminal doctor will be used:
The second fact follows from proposal order. A doctor ending unmatched has exhausted all acceptable contracts.
Fix a hospital \(h\). Let \(F_h^{(n)}\) be the fractional-knapsack optimum over all copied contracts proposed to \(h\). This relaxation has an individual bound \(q_{d,x}\leq1\) for each copied contract, but imposes no additional constraint preventing several contracts of the same doctor from being selected.
We show that this relaxation bounds every deviation allowed in the question:
\[ D_h(y^{(n)})\leq F_h^{(n)}. \]
Take any feasible mass deviation \(z\). Let \(r_{t,a}\) be the number of type-\(t\) doctors whose terminal option is \(a\). Then
\[ y^{(n)}_{t,a}=r_{t,a}\delta_t. \]
If \(r_{t,a}=0\), the deviation’s source constraint forces all \(z_{t,a,x}\) to be zero. Otherwise, for every doctor \(d\) in this group and every allowed destination \(x\) at \(h\), set
\[ q_{d,x}=\frac{z_{t,a,x}}{r_{t,a}\delta_t}. \]
These copied contracts were all proposed: either \(x=a\), or \(x\) is strictly preferred to the terminal option. Moreover,
\[ \sum_x q_{d,x} = \frac{\sum_xz_{t,a,x}}{r_{t,a}\delta_t} \leq1. \]
In particular, each \(q_{d,x}\leq1\). Summing over the doctors in each group shows that this fractional selection has exactly the deviation’s budget use and utility:
\[ \sum_{d,x}\delta_t\sigma_t(x)q_{d,x} = \sum_{t,a,x}\sigma_t(x)z_{t,a,x}\leq1, \]
\[ \sum_{d,x}\delta_tu_t(x)q_{d,x} = \sum_{t,a,x}u_t(x)z_{t,a,x}. \]
It is therefore feasible for the relaxed knapsack problem.
Applying the lemma to \(h\)’s proposal history, its terminal retained value is exactly \(U_h(y^{(n)})\), so
\[ D_h(y^{(n)}) \leq F_h^{(n)} \leq \frac{U_h(y^{(n)})}{1-B/n}. \]
This argument accommodates multiple contracts between one type and one hospital: the knapsack problem is a relaxation, and every actual deviation embeds into it.
The feasible allocation set \(\mathcal{Y}\) is a nonempty compact subset of \(\mathbb{R}^{K+\tau}\):
Consequently, the sequence \(y^{(n)}\), over integers \(n>B\), has a convergent subsequence:
\[ y^{(n_j)}\longrightarrow y^*\in\mathcal{Y}. \]
For every hospital, the bound just proved gives
\[ D_h(y^{(n_j)}) \leq\frac{U_h(y^{(n_j)})}{1-B/n_j}. \]
By Section 1, \(D_h\) is continuous; \(U_h\) is linear and hence continuous. Also \(B/n_j\longrightarrow0\). Taking limits yields
\[ D_h(y^*)\leq U_h(y^*). \]
Retention always gives the reverse inequality. Thus
\[ D_h(y^*)=U_h(y^*)\qquad\text{for every hospital }h. \]
This proves that \(y^*\) is feasible and \(1\)-stable. The task permits real allocation masses, so no rationality assertion about this limit is needed.
For every fixed rational \(\alpha>1\), every valid instance is a YES instance: its \(1\)-stable allocation is also \(\alpha\)-stable.
The decision algorithm therefore returns YES on every valid input. Its running time is \(O(1)\) after input delivery, or \(O(L)\) if reading the entire input is counted; in particular, it is polynomial in \(m,\tau,K,L\). The finite subdivisions above establish existence and are not performed by this decision algorithm.
Because the promised NO set is empty, ordinary promise-preserving reductions cannot establish the proposed hardness from a decision problem having NO instances.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned promise problem. It establishes that every valid instance admits a feasible \(1\)-stable mass allocation. Thus the promised NO case is empty, and the constant YES algorithm is valid.
No major or minor mathematical issues were found. The existence proof is nonconstructive, but the task asks for a decision algorithm, not an algorithm producing an allocation.
The deviation feasible set is nonempty because the zero deviation is feasible. It is closed and bounded in a finite-dimensional space: each variable is nonnegative and bounded by its source mass. Therefore the stated maximum exists.
Retaining precisely the current contracts at hospital \(h\) satisfies the source, transition, and budget constraints. Consequently, \(D_h(y)\geq U_h(y)\). Because blocking requires a strict utility improvement, the equivalence between \(1\)-stability and equality at every hospital is correct.
The scaling construction respects every deviation constraint:
The claimed utility-loss bound follows from the source constraint and the definition of \(M_h\). Interchanging the allocations gives the displayed Lipschitz bound. This also covers hospitals without contracts and allocations with zero coordinates.
The lemma is valid for the specified sequential rule.
If total arriving cost is at most \(1\), every intermediate retained cost is also at most \(1\), so no discard occurs.
Otherwise, the longest feasible ordered prefix \(P\) exists, and its next item has positive cost. The argument that every item of \(P\) survives is sound: immediately before an item is discarded, all other retained items precede it in priority. Their combined cost cannot exceed the cost of the full ordered prefix ending at that item, which is at most \(1\).
The inequalities \(C+c_b>1\) and \(c_b\leq s\) correctly imply \(C>1-s>0\), justifying division by \(C\).
The fractional-knapsack bound correctly handles zero-cost items, density ties, and zero values. In particular, all zero-cost items lie in \(P\), and the signs of the residual terms justify replacing their fractional coefficients by \(1\). The subsequent inequalities follow from \(V\geq\rho C\), \(C\leq1\), and nonnegativity.
When \(s=0\), all costs are zero, so the first case applies. No exceptional division is needed.
The subdivision preserves each type’s total mass, and every copied contract has cost at most \(B/n<1\). This remains valid when original per-capita budget uses exceed \(1\).
Here “acceptable” has its usual meaning of strictly preferred to unmatched, consistent with the task’s feasibility restriction.
Only unmatched doctors propose, so no doctor is simultaneously held at multiple hospitals. Budget enforcement gives feasible hospital rosters. The priority rule ensures that zero-cost contracts are never discarded.
Each copied contract is proposed at most once, giving the stated bound of \(nK\) proposals. At termination, each doctor has proposed every acceptable contract preferred to its terminal option; an unmatched terminal doctor has exhausted all acceptable contracts.
Aggregation therefore produces a feasible original mass allocation.
The embedding of an arbitrary mass deviation into the proposed-contract knapsack relaxation is correct.
For a source group containing no terminal doctors, its available mass is zero and all corresponding deviation variables vanish. Otherwise, the denominator \(r_{t,a}\delta_t\) is positive.
Every copied destination used by the embedding was proposed: it is either the terminal assigned contract or a contract strictly preferred to the terminal option. Since terminal options are acceptable or unmatched, such destinations are acceptable.
The source constraint gives \(\sum_x q_{d,x}\leq1\), hence each individual knapsack bound is satisfied. Summing over the source group cancels the normalization exactly, preserving both budget use and utility.
Allowing multiple contracts from the same doctor in the knapsack relaxation does not invalidate the upper bound. The embedded deviation satisfies even the stronger per-doctor constraint.
Applying the selection lemma to each hospital’s actual proposal history therefore establishes the claimed bound on \(D_h(y^{(n)})\).
The feasible allocation set is nonempty, closed, and bounded in the stated finite-dimensional space, hence compact. Its constraints include the prohibition on mass below unmatched.
A convergent subsequence remains feasible, and its subdivision indices tend to infinity. Continuity of \(D_h\), linearity of \(U_h\), and \(B/n_j\to0\) justify the limiting inequality.
Together with the retention inequality, this establishes equality for every hospital. The limit is therefore exactly \(1\)-stable. Real masses are explicitly permitted, so no rationality or finite representation claim is needed.
With nonnegative hospital utilities and \(\alpha>1\), a \(1\)-stable allocation is also \(\alpha\)-stable. Thus every valid input satisfies the YES condition, and none satisfies the promised NO condition.
Returning YES takes constant time if input reading is excluded, or \(O(L)\) when reading is counted. The potentially large subdivisions are used only for existence and do not affect this decision running time.
The statement concerning ordinary promise-preserving hardness reductions is also correct.
None is required. The write-up supplies the necessary hypotheses, deviation coverage, edge cases, and limiting justification.
⟨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.