Answer: \(\mathrm{NP}\)-complete, even for every fixed \(\ell\ge 2\), equal dyadic masses, and at most three approved partners per type per layer.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor each ℓ≥2, All-Layers Weak Stability is NP-hard for symmetric bipartite approvals and NP-hard for (asymmetric) bipartite approvals even if agents from one side approve the same agents in both layers. Both results hold even if each agent approves at most three agents in each layer.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a bipartite support \(\mathcal T=R\mathbin{\dot\cup}S\), rational masses \(\mu_t>0\) summing to \(1\), and mutually approved type-pair sets \(E_i\subseteq R\times S\) for each layer \(i\in[\ell]\), does there exist a mass matching \(x_{tu}\ge0\) with incident mass at each type at most \(\mu_t\), such that for every \((t,u)\in E_i\) and every layer \(i\), \(h_t^{(i)}h_u^{(i)}=0\), where \(h_t^{(i)}=\mu_t-\sum_{u:(t,u)\in E_i}x_{tu}\) (and symmetrically for \(u\))?
A society is given by its support \(\mathcal T=R\mathbin{\dot\cup}S\): a list of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types; partner alternatives are types, so \(m=\tau\). Let \(L\) be the total input bit length.
There are \(\ell\ge2\) layers, each given explicitly by a mutually approved pair set \(E_i\subseteq R\times S\). Within a layer, approved partners are tied and strictly preferred to disapproved partners, which are tied with being unmatched; empty approval sets are allowed.
A mass matching is a single array \(x\in\mathbb R_{\ge0}^{R\times S}\), shared across all layers, with \(\sum_{u\in S}x_{tu}\le\mu_t\) for every \(t\in R\) and \(\sum_{t\in R}x_{tu}\le\mu_u\) for every \(u\in S\). Disapproved pairs may receive mass, and mass may remain unmatched.
Define unhappy masses by \(h_t^{(i)}=\mu_t-\sum_{u:(t,u)\in E_i}x_{tu}\) and \(h_u^{(i)}=\mu_u-\sum_{t:(t,u)\in E_i}x_{tu}\). Call the matching all-layers weakly stable if \(h_t^{(i)}h_u^{(i)}=0\) for every layer \(i\) and every \((t,u)\in E_i\).
Is deciding whether an all-layers weakly stable mass matching exists solvable in polynomial time in \(m,\tau,\ell,L\), or is it NP-hard?
For discrete agents, all-layers weak stability is NP-hard for every fixed \(\ell\ge2\), even with symmetric bipartite approvals and at most three approved partners per agent per layer ([source](https://arxiv.org/pdf/2205.07550)).
No complexity classification for exactly this mass feasibility problem was located in the literature search.
The problem is \(\mathrm{NP}\)-complete, even for every fixed \(\ell\ge 2\), with equal masses and at most three approved partners per type per layer.
The key fact is that, for equal masses, fractional feasibility implies discrete feasibility. Splitting mass therefore does not evade the cited hardness result.
For a bipartite vertex set \(R\mathbin{\dot\cup}S\), define the fractional matching polytope
\(P=\left\{y\in\mathbb R_{\ge 0}^{R\times S}:\sum_{u\in S}y_{tu}\le 1\ \text{for every }t\in R,\ \sum_{t\in R}y_{tu}\le 1\ \text{for every }u\in S\right\}.\)
Lemma. Suppose every type has the same mass \(c>0\). An all-layers weakly stable mass matching exists if and only if a discrete matching exists in which every approved edge, in every layer, has an endpoint matched to an approved partner in that layer.
Proof. A discrete matching with the stated property immediately gives a stable mass matching by assigning mass \(c\) to each matched pair.
For the converse, let \(x\) be a stable mass matching and put \(y=x/c\). Then \(y\in P\).
We first justify that every point of \(P\) is a convex combination of incidence matrices of discrete matchings. The polytope is bounded, so it suffices to show that every extreme point is integral.
Suppose \(y\in P\) has a fractional coordinate. Form the bipartite graph consisting of edges with \(0<y_{tu}<1\).
Thus a fractional point cannot be extreme. Every extreme point is consequently a \(0\)-\(1\) incidence matrix of a matching. By the finite-dimensional polytope decomposition theorem, we may write
\(y=\sum_{k=1}^{q}\lambda_k\chi^{M_k},\qquad \lambda_k>0,\qquad \sum_{k=1}^{q}\lambda_k=1,\)
where each \(M_k\) is a discrete matching.
For a vertex \(v\) and layer \(i\), define its normalized unhappy mass at \(z\in P\) by
\(d_v^{(i)}(z)=1-\sum_{e\in E_i:\,v\in e}z_e.\)
Capacity feasibility implies \(d_v^{(i)}(z)\ge 0\). Moreover,
\(d_v^{(i)}(y)=\sum_{k=1}^{q}\lambda_k d_v^{(i)}(\chi^{M_k}).\)
Consequently, if \(d_v^{(i)}(y)=0\), then \(d_v^{(i)}(\chi^{M_k})=0\) for every \(k\): all summands are nonnegative and every coefficient is positive.
Now fix any layer \(i\) and edge \((t,u)\in E_i\). Stability of \(x\), together with \(h_v^{(i)}(x)=c\,d_v^{(i)}(y)\), implies that one endpoint has normalized unhappy mass zero. That same endpoint has unhappy mass zero in every \(M_k\). In a discrete matching, this means that it is matched to an approved partner in layer \(i\).
This holds simultaneously for every layer and approved edge. Therefore every \(M_k\) has the required discrete stability property. \(\square\)
Theorem 1 of Bentert, Boehmer, Heeger, and Koana establishes \(\mathrm{NP}\)-hardness of discrete all-layers weak stability for two layers, with symmetric bipartite approvals and at most three approved partners per agent per layer. Their preferences tie disapproved partners with being unmatched, exactly as here. [Source: Theorem 1 and the preference definitions](https://arxiv.org/pdf/2205.07550).
Take an instance of this discrete problem with \(n\) agents. Choose a bipartition \(R\mathbin{\dot\cup}S\) of the union of its approval graphs.
If its matching model allows pairs within one side, deleting those pairs preserves every agent’s happiness in every layer: bipartiteness makes such pairs disapproved in all layers. Thus restricting matchings to \(R\times S\) does not change existence.
Construct the mass instance as follows:
The padding makes the masses dyadic, so the construction works even under the more restrictive interpretation that “binary rational” means a terminating binary fraction. The masses are positive and sum to \(1\).
If the discrete instance has a stable matching, leave dummy types unmatched and assign mass \(1/N\) to every matched pair. Each approved edge has a happy endpoint, so the resulting mass matching is stable.
Conversely, suppose the constructed mass instance has a stable matching. By the lemma, its padded discrete instance has a stable matching. Delete all pairs incident to dummy types. These pairs are disapproved in every layer, so their deletion preserves the happiness of every original agent. The remaining matching solves the original discrete instance.
The construction has \(N<2n\) types and mass encodings of length \(O(\log n)\) per type. Its total encoding length is polynomial in the source input length. In particular, it respects \(m=\tau=N\); it introduces no implicitly represented partner alternatives.
This proves \(\mathrm{NP}\)-hardness for \(\ell=2\). For any fixed \(\ell>2\), add \(\ell-2\) empty layers. They impose no stability conditions, so feasibility is unchanged. Approval degrees remain at most three.
We now consider the full problem, allowing unequal positive rational masses and an explicitly given number of layers.
For each layer \(i\), guess a set \(H_i\subseteq R\mathbin{\dot\cup}S\) of types required to have zero unhappy mass. This certificate contains \(\tau\ell\) bits.
First verify that \(H_i\) covers every approved edge:
\((t,u)\in E_i\ \Longrightarrow\ t\in H_i\ \text{or}\ u\in H_i.\)
Next test feasibility of the following rational linear program:
There are at most \(\tau^2\) variables and polynomially many constraints. Coefficients are \(0\) or \(1\), and the right-hand sides are input rationals. Hence the encoding length is polynomial in \(\tau,\ell,L\), and rational linear-programming feasibility can be decided in polynomial time.
The verifier is sound: an accepted feasible point has nonnegative unhappy masses, and every approved edge has an endpoint whose unhappy mass is zero.
It is also complete: given any stable mass matching, take \(H_i=\{v:h_v^{(i)}=0\}\). Nonnegativity and the stability products imply that these sets cover all approved edges, and the given matching satisfies the linear program.
Thus the problem belongs to \(\mathrm{NP}\).
The equal-mass rounding lemma transfers discrete hardness to the exact mass feasibility problem. Combined with the verifier above, this proves \(\mathrm{NP}\)-completeness for every fixed \(\ell\ge 2\), and also when \(\ell\) is part of the input. A polynomial-time algorithm in \(m,\tau,\ell,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The prover establishes \(\mathrm{NP}\)-completeness of the stated mass feasibility problem, including for every fixed \(\ell\ge 2\), equal dyadic masses, and at most three approved partners per type per layer. I found no major or minor mathematical issues requiring repair.
Normalization and feasibility. With common mass \(c>0\), setting \(y=x/c\) correctly converts each capacity bound into a bound of \(1\). Thus \(y\in P\). The argument allows coordinates on disapproved pairs, as the task requires.
Boundedness. Nonnegativity and the capacity bounds imply \(0\le y_{tu}\le 1\) for every coordinate. The set \(P\) is a nonempty, bounded polyhedron in a finite-dimensional space, so the cited decomposition theorem applies once its extreme points are shown to be integral.
Cycle perturbation. The graph of strictly fractional coordinates is bipartite, so every cycle has even length. Alternating perturbations around a cycle preserve all vertex sums. Since the cycle has finitely many coordinates, all strictly between \(0\) and \(1\), a sufficiently small positive perturbation preserves feasibility in both directions. The resulting distinct feasible points have midpoint \(y\), excluding extremality.
Tree perturbation. If the fractional-coordinate graph has no cycle, any component containing an edge is a finite tree with two leaves. At each chosen leaf, the fractional edge is its only positive incident coordinate: another fractional coordinate would contradict its leaf status, and a coordinate equal to \(1\) would violate capacity alongside the positive fractional edge. Therefore both endpoints have strictly positive capacity slack.
Alternating perturbations along the path preserve internal vertex sums. A sufficiently small perturbation preserves coordinate nonnegativity and the endpoint capacity bounds in both directions. This again excludes extremality.
These two cases exhaust the possibilities for a graph containing a fractional coordinate. Consequently, every extreme point is integral. Integral feasible points are precisely incidence matrices of discrete matchings.
Convex decomposition. The representation
\[
y=\sum_{k=1}^{q}\lambda_k\chi^{M_k}
\]
with strictly positive coefficients summing to \(1\) is justified; any zero coefficients may be omitted.
Preservation of zero unhappy mass. Each function \(d_v^{(i)}\) is affine and nonnegative throughout \(P\). Consequently, its value at the convex combination is the corresponding convex combination of its values. If that value is zero, positivity of the coefficients and nonnegativity of the summands force its value to be zero in every constituent matching.
Simultaneous stability. For each approved edge in each layer, stability supplies an endpoint with zero normalized unhappy mass. The decomposition argument preserves that endpoint’s zero value in every \(M_k\). Although the endpoint may depend on the edge and layer, every constituent matching satisfies all these conditions simultaneously. There is no invalid interchange of quantifiers.
For an incidence matrix, zero normalized unhappy mass means that the vertex is matched to an approved partner in that layer. Thus every \(M_k\) has the lemma’s required property. The reverse implication, assigning mass \(c\) to discrete matched pairs, also satisfies capacities and stability.
Assessment: the rounding lemma is correct and fully justified.
External theorem. The cited Theorem 1 establishes the required discrete hardness for symmetric bipartite approvals with approval degree at most three per agent per layer. Its definitions make unmatched agents indifferent to disapproved partners, define bipartiteness using the union of the layer graphs, and permit partial matchings. These hypotheses match the reduction. [Bentert, Boehmer, Heeger, and Koana, Section 2 and Theorem 1](https://arxiv.org/pdf/2205.07550).
Discrete stability condition. Under these preferences, a pair blocks weakly exactly when its endpoints mutually approve each other and both are unhappy. Thus the lemma’s approved-edge condition is precisely the source problem’s all-layers weak stability condition.
Common bipartition. The source restriction guarantees that the union approval graph is bipartite. Its bipartition can be found in polynomial time. Pairs within one side are disapproved in every layer, so deleting such matched pairs preserves every agent’s happiness and weak stability.
Padding and masses. For a source instance with \(n\ge 1\) agents,
\[
N=2^{\lceil\log_2 n\rceil}
\]
satisfies \(n\le N<2n\). Adding \(N-n\) dummy types and assigning every type mass \(1/N\) produces positive masses summing to \(1\). These masses have terminating binary expansions and encoding length \(O(\log n)\).
Forward implication. A source matching restricted to cross-partition pairs yields a feasible mass matching by assigning \(1/N\) to each matched pair. Dummy types remain unmatched. Every original approved edge retains a happy endpoint, and dummy types introduce no approved edges.
Reverse implication. The rounding lemma produces a stable discrete matching on the padded instance. Every pair incident to a dummy is disapproved in every layer. Deleting these pairs therefore preserves the happiness of every original agent and leaves a source solution.
Encoding and restrictions. The construction has polynomial size, explicitly represents all types, respects \(m=\tau=N\), and preserves the approval-degree bound.
Additional layers. For any fixed \(\ell>2\), empty added layers impose no stability constraints. Their addition preserves feasibility and the degree bound.
Assessment: the reduction correctly establishes all claimed hardness restrictions.
Certificate size. The sets \(H_i\) require \(\tau\ell\) bits, polynomial in the parameters and the explicit input representation.
Linear feasibility test. The proposed system has at most \(\tau^2\) variables and at most polynomially many constraints. Its coefficients and rational right-hand sides have polynomial encoding length. The standard theorem that rational linear-programming feasibility is decidable in polynomial time applies to this explicitly represented system.
Soundness. Capacity feasibility ensures all unhappy masses are nonnegative. The equalities force zero unhappy mass for every selected vertex. Since each \(H_i\) covers every approved edge, every required stability product is zero.
Completeness. Given any stable mass matching, selecting exactly the vertices with zero unhappy mass in each layer covers every approved edge and makes the linear system feasible. This remains valid if the original matching has irrational coordinates: the verifier decides feasibility of the rational system and does not require that matching as its certificate.
Empty approval sets and empty layers cause no difficulty. An incorrectly selected positive-mass vertex with no approved partners simply makes the corresponding equality infeasible.
Assessment: membership in \(\mathrm{NP}\) is established for arbitrary rational masses and an explicitly represented number of layers.
The output resolves the assigned continuous problem. The rounding lemma supplies the necessary bridge from discrete hardness, the reduction preserves the task’s representation and restrictions, and the certificate verifier proves membership in \(\mathrm{NP}\). No additional clarification is needed.
⟨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.