Answer: \(\mathrm{P}\)
Theorem 10 — class: hardness
In marriage games, Perfect/Nash-stable- ∃CCAUP(-m) and deciding Pr[NSG′], Pr[PFG′] > 0 are NPC. The same applies to roommates, Representation by In- dividually Rational Lists of Coalitions (RIRLC) (Ballester 2004), additively separable hedonic games (Olsen 2009), B- hedonic games and W-hedonic games (Aziz et al. (2012)).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worker and employer type sets with rational initial masses, optional reserve masses, complete type-level approval or compatibility data, per-unit addition costs, and a budget B, can one choose added masses y and matching masses x so that all selected mass is perfectly matched along acceptable type pairs within budget B? The optimization version minimizes the addition cost.
An instance has finite worker types \(W\), employer types \(E\), initial masses \(a_t\in\mathbb{Q}_{\ge0}\), reserve caps \(r_t\in\mathbb{Q}_{\ge0}\), acceptable pairs \(A\subseteq W imes E\), addition costs \(c_t\in\mathbb{Q}_{\ge0}\), and budget \(B\in\mathbb{Q}_{\ge0}\). Choose \(0\le y_t\le r_t\) and \(x_{we}\ge0\) for \((w,e)\in A\), with \(\sum_e x_{we}=a_w+y_w\) and \(\sum_w x_{we}=a_e+y_e\); thus every initial and added unit is matched acceptably. The optimization version minimizes \(\sum_t c_ty_t\).
Is deciding whether such \(x,y\) exist with \(\sum_t c_ty_t\le B\) in \(\mathrm{P}\), or is it NP-hard?
For discrete marriage games, deciding whether adding a subset of available players can yield a perfect partition is NP-complete, including its bounded-additions variant. This is the discrete hardness anchor.
Assume the finite sets \(W\), \(E\), and \(A\) are represented explicitly, and all rational numbers are encoded in binary. This is the standard encoding under which the stated complexity question is defined.
The budget-feasibility problem is in \(\mathrm{P}\). Moreover, the optimization problem can be solved in polynomial time.
Introduce one variable \(y_t\) for every \(t\in W\cup E\), and one variable \(x_{we}\) for every \((w,e)\in A\). The required conditions are exactly the following linear constraints:
Thus the decision problem is feasibility of a rational linear program.
There are \(N=|A|+|W|+|E|\) variables and \(O(|A|+|W|+|E|)\) constraints. Apart from the input rationals, every coefficient belongs to \(\{-1,0,1\}\). Consequently, the binary encoding length of this linear program is polynomial in the binary encoding length of the instance.
The polynomial-time feasibility theorem for rational linear programming therefore decides whether this system has a real solution in time polynomial in the input length. Equality constraints cause no difficulty, since each equality can be replaced by two inequalities.
There is also no distinction here between real and rational feasibility. Indeed, the feasible region is bounded: each \(y_t\) is bounded by \(r_t\), and for every acceptable pair \((w,e)\),
\(0\leq x_{we}\leq\sum_{e':(w,e')\in A}x_{we'}=a_w+y_w\leq a_w+r_w\).
Hence a nonempty feasible region is a rational polytope and contains a rational extreme point.
The network structure gives a more specialized polynomial-time formulation. Introduce an auxiliary vertex \(q\), and construct the following arcs:
Given a feasible solution, set the corresponding arc flows to \(a_w+y_w\), \(x_{we}\), and \(a_e+y_e\). The worker and employer matching equalities are precisely flow conservation at \(w\) and \(e\). Conservation at \(q\) follows by summing those equalities.
Conversely, any feasible circulation defines \(y_w=f(q,w)-a_w\), \(y_e=f(e,q)-a_e\), and \(x_{we}=f(w,e)\), and these variables satisfy all matching and reserve constraints.
Let \(C_0=\sum_{t\in W\cup E}c_ta_t\). The circulation cost is
\(C_0+\sum_{t\in W\cup E}c_ty_t\).
Therefore, the original instance has a solution of addition cost at most \(B\) if and only if this network has a feasible circulation of cost at most \(C_0+B\). Rational minimum-cost circulation is polynomial-time solvable.
The cited discrete hardness does not transfer to the stated model. The present feasible set contains only linear conservation, capacity, and budget constraints; it contains no indivisible subset-selection, stability, or other discrete partition requirement. The continuous variables therefore yield a rational linear program.
Thus the target problem is in \(\mathrm{P}\). It could also be NP-hard under standard many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The variables correspond exactly to the stated choices:
The bounds \(0\leq y_t\leq r_t\), nonnegativity \(x_{we}\geq 0\), worker equations
\[ \sum_{e:(w,e)\in A}x_{we}-y_w=a_w, \]
and employer equations
\[ \sum_{w:(w,e)\in A}x_{we}-y_e=a_e \]
are algebraically identical to the requirements in the problem. The budget inequality is also reproduced exactly. No integrality or subset-selection constraint appears in the stated model.
There are \( |A|+|W|+|E| \) variables and polynomially many explicitly represented constraints. All structural coefficients are in \( \{-1,0,1\} \), while the remaining coefficients are input rationals. Thus the resulting rational linear program has encoding length polynomial in the original input length.
Invoking polynomial-time rational linear-program feasibility is valid. Replacing equalities with pairs of inequalities preserves feasibility and only increases the formulation size by a constant factor.
The boundedness argument is correct. For every \((w,e)\in A\),
\[ 0\leq x_{we} \leq \sum_{e':(w,e')\in A}x_{we'} =a_w+y_w \leq a_w+r_w. \]
Together with the bounds on \(y_t\), this makes the feasible region bounded. A nonempty rational polytope has a rational extreme point, so real feasibility and rational feasibility coincide. This observation is correct, though rational LP feasibility alone already suffices for the complexity conclusion.
The proposed network correctly represents the constraints:
The upper capacity \(a_w+r_w\) on every acceptable-pair arc is valid because no individual outgoing flow can exceed the total flow entering worker \(w\).
The circulation cost calculation is also correct:
\[ \sum_{w\in W}c_w(a_w+y_w)+ \sum_{e\in E}c_e(a_e+y_e) = C_0+\sum_{t\in W\cup E}c_ty_t. \]
Thus the threshold \(C_0+B\) is exactly equivalent to the original budget threshold. Rational minimum-cost circulation, or directly rational linear programming, yields a polynomial-time optimization algorithm.
The continuous problem is in \( \mathrm{P} \). The cited discrete hardness result does not apply because the present formulation has no indivisible selection requirement. The statement that this problem can be NP-hard under standard polynomial-time many-one reductions only if \( \mathrm{P}=\mathrm{NP} \) is correct.
No substantive gap, false assertion, or omitted hypothesis was found.
⟨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.