Answer: \(\mathrm{NP}\text{-hard}\), even for an empty initial matching and uniform positive dyadic type masses.
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateChecking neutral stable set membership is coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite male and female type sets \(T_M,T_W\), rational type masses with each side totaling \(1\), complete externality valuation vectors \(\pi_t(a,b)\), and a feasible mass matching \(x\), decide whether there are coalition masses \(q_t\leq\mu_t\), with some \(q_t>0\), and a feasible reassignment \(x'\) that blocks \(x\). Split each type's mass into coalition and outsider submasses; preserve all outsider-to-outsider matches, allow new matches only within the coalition, and require every participating unit to form or sever a match. For each participating type \(t\), compare \(U_t(x)=\sum_{a,b}x_{ab}\pi_t(a,b)\) with \(U_t(x')=\sum_{a,b}x'_{ab}\pi_t(a,b)\); every participating type must weakly gain and at least one type with \(q_t>0\) must strictly gain.
A society has disjoint nonempty male and female type supports \(T_M,T_W\), with positive binary-rational masses \(\mu_t\) totaling \(1\) on each side. It is given by its support list; \(\tau=|T_M|+|T_W|\) is the support size, not the number of possible types. Put \(m=|T_M|\), and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
The input also gives arbitrary signed rational valuations \(\pi_t(a,b)\) for every \(t\in T_M\cup T_W\) and \((a,b)\in T_M\times T_W\), and a rational mass matching \(x\geq0\) with \(\sum_b x_{ab}\leq\mu_a\) and \(\sum_a x_{ab}\leq\mu_b\). Unmatched mass is allowed. Every unit of type \(t\) has utility \(U_t(x)=\sum_{a,b}x_{ab}\pi_t(a,b)\), without transfers.
For unit identities, represent each type by a nonatomic interval of length \(\mu_t\); a one-to-one matching is a measurable measure-preserving bijection between subsets of the male and female intervals. Its type-pair masses must realize \(x\).
A deviation chooses measurable coalition subsets of masses \(0\leq q_t\leq\mu_t\), with \(\sum_tq_t>0\), and a new one-to-one matching realizing \(x'\). Outsider-to-outsider matches remain unchanged; existing matches incident to coalition units may be severed unilaterally, and new matches require both endpoints in the coalition. Almost every coalition unit must lose an existing partner or gain a different partner; merely retaining a match does not count as acting.
The deviation blocks if \(U_t(x')\geq U_t(x)\) for every \(t\) with \(q_t>0\), and \(U_t(x')>U_t(x)\) for at least one such type. Decide whether a realization of \(x\) admits a blocking deviation; coalition subsets and reassigned masses may be real.
Is this continuous blocking-existence problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite individual agents with additive externalities, neutral one-to-one setwise stability membership is coNP-complete, so blocking existence is NP-complete. [Source](https://www.ifaamas.org/Proceedings/aamas2013/docs/p295.pdf).
No result settling this precise continuous problem was located in the literature search.
The continuous blocking-existence problem is \(\mathrm{NP}\)-hard, even when the initial matching is empty and all listed types have the same positive dyadic mass. Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
The proof below uses real coalition masses throughout.
Suppose \(x=0\), and write \(y=x'\) for the new matching.
Every coalition unit is initially unmatched. Therefore, the acting requirement says that almost every coalition unit must acquire a partner. Conversely, every endpoint of a new match must belong to the coalition. Consequently, the coalition masses are exactly
\( q_a=\sum_b y_{ab} \quad\text{and}\quad q_b=\sum_a y_{ab}. \)
Call a type active when its incident mass in \(y\) is positive. Since all initial utilities are zero, a deviation blocks precisely when:
These aggregate conditions are also sufficient at the level of unit identities. For each type, partition measurable subsets of its interval into pieces of the required incident masses. Match corresponding pieces by measure-preserving bijections. All selected units acquire partners, and hence act. There are no existing matches to preserve.
We reduce from the standard \(\mathrm{NP}\)-complete problem \(3\)-SAT. [MIT complexity course materials](https://courses.csail.mit.edu/6.045/spring04/materials.html).
Let the formula have variables \(X_1,\ldots,X_n\) and clauses \(C_1,\ldots,C_k\), with \(n,k\geq1\). We may ensure that
\( N=2n+k+1 \)
is a power of two: append tautological clauses \(X_1\lor\neg X_1\lor X_1\) until this holds. The number of appended clauses is less than the original value of \(2n+k+1\), so this preserves satisfiability and increases the instance size only linearly. Below, \(k\) denotes the number of clauses after padding.
For each variable, introduce male types \(M_i^+,M_i^-\) and female types \(W_i^+,W_i^-\).
For each clause, introduce a male type \(A_j\) and a female type \(B_j\).
Finally, introduce a male trigger type \(H\) and a female trigger type \(K\).
There are \(N\) types on each side. Give every type mass \(1/N\). These are positive dyadic masses and total \(1\) on each side. Set \(x=0\).
Thus
\( m=N,\qquad \tau=2N. \)
The designated type pairs are
\( (M_i^+,W_i^+),\quad (M_i^-,W_i^-),\quad (A_j,B_j),\quad (H,K). \)
For an arbitrary proposed matching \(y\), denote their masses by
\( z_i^+=y_{M_i^+,W_i^+},\qquad z_i^-=y_{M_i^-,W_i^-},\qquad c_j=y_{A_j,B_j},\qquad h=y_{H,K}. \)
Let \(E\) be the total mass on all undesignated type pairs:
\( E=\sum_{(a,b)\text{ undesignated}}y_{ab}. \)
For a literal \(\ell\), define \(z_\ell=z_i^+\) if \(\ell=X_i\), and \(z_\ell=z_i^-\) if \(\ell=\neg X_i\). Write
\( \lambda_j(z)=\sum_{\ell\in\operatorname{Lit}(C_j)}z_\ell, \)
where \(\operatorname{Lit}(C_j)\) is the set of distinct literals in the clause.
Specify valuations by requiring the following utilities for every matching \(y\):
| Type | Utility |
|---|---|
| \(M_i^+\), \(W_i^+\) | \(-z_i^- -E\) |
| \(M_i^-\), \(W_i^-\) | \(-z_i^+ -E\) |
| \(A_j\) | \(h-c_j-E\) |
| \(B_j\) | \(\lambda_j(z)-h-E\) |
| \(H\) | \(\sum_{j=1}^k c_j-(k-\tfrac12)h-E\) |
| \(K\) | \(-E\) |
These are valid additive utilities: each expression is a rational linear combination of the type-pair masses. Its coefficients define the corresponding entries of \(\pi_t(a,b)\).
In particular, every undesignated edge has valuation \(-1\) for every type. All designated-edge coefficients not displayed above are zero.
Suppose the formula has a satisfying assignment. Put \(s=1/N\).
For each variable, assign mass \(s\) to its designated positive edge if the variable is true, and to its designated negative edge if it is false. Assign zero to the other literal edge. Also set
\( c_j=s\quad\text{for every }j,\qquad h=s, \)
and put zero on all undesignated edges.
Every designated edge uses distinct endpoint types, and its mass is at most the endpoint capacity \(s\). Hence this is a feasible matching. Also \(E=0\).
For every active literal type, the opposite literal mass is zero, so its utility is zero.
For each clause,
\( U_{A_j}=h-c_j=0. \)
Because the assignment satisfies the clause, at least one of its literal masses equals \(s\). Therefore
\( U_{B_j}=\lambda_j(z)-s\geq0. \)
Finally,
\( U_K=0,\qquad U_H=ks-(k-\tfrac12)s=\tfrac12s>0. \)
Every active type weakly gains, and the active trigger type \(H\) strictly gains. By Section 1, the matching is realized by a blocking deviation whose coalition units all act.
Suppose a blocking deviation exists, and use its masses \(z_i^\pm,c_j,h,E\).
Assume, for contradiction, that \(E>0\).
Every literal type then has strictly negative utility, because its utility is an expression of the form
\( -z_i^\pm-E<0. \)
Thus no literal type can be active. In particular, all literal-edge masses vanish, and \(\lambda_j(z)=0\) for every clause.
Every female clause type now has utility
\( U_{B_j}=-h-E<0. \)
Hence none is active, and therefore \(c_j=0\) for every clause.
The male trigger utility becomes
\( U_H=-(k-\tfrac12)h-E<0, \)
using \(k\geq1\). Thus \(H\) is inactive, which implies \(h=0\).
All remaining types then also have strictly negative utility:
\( U_{A_j}=-E<0,\qquad U_K=-E<0. \)
We have shown that no type can be active. Section 1 then gives a coalition of zero total mass, contradicting the definition of a deviation. Therefore
\( E=0. \)
If \(z_i^+>0\), then \(M_i^+\) is active. Its required nonnegative utility gives
\( 0\leq U_{M_i^+}=-z_i^-, \)
so \(z_i^-=0\). Likewise, \(z_i^->0\) implies \(z_i^+=0\).
Thus positive literal masses define consistent truth choices.
Suppose \(h=0\). If some \(c_j>0\), then \(A_j\) is active but has utility
\( U_{A_j}=-c_j<0, \)
which is impossible. Hence every \(c_j=0\).
Since \(E=0\), only literal edges can now carry mass. By Section 4.2, every active literal type has utility zero. No active type strictly gains, contradicting blocking.
Consequently,
\( h>0. \)
Whenever \(c_j>0\), the active type \(A_j\) requires
\( 0\leq h-c_j, \)
and hence \(c_j\leq h\). This bound also holds when \(c_j=0\).
The trigger type \(H\) is active because \(h>0\). Its nonnegative utility requires
\( \sum_{j=1}^k c_j\geq(k-\tfrac12)h. \)
If any clause mass were zero, the other \(k-1\) clause masses, each at most \(h\), would give
\( \sum_{j=1}^k c_j\leq(k-1)h<(k-\tfrac12)h, \)
a contradiction. Therefore \(c_j>0\) for every clause.
Since \(c_j>0\), the female clause type \(B_j\) is active. Thus
\( 0\leq U_{B_j}=\lambda_j(z)-h, \)
so \(\lambda_j(z)\geq h>0\).
Each clause therefore contains a literal with positive mass. Assign \(X_i\) true when \(z_i^+>0\), false when \(z_i^->0\), and arbitrarily when both masses are zero. Section 4.2 makes this assignment well-defined. Every clause contains a positive-mass literal that is true under the assignment.
The formula is satisfied.
The reduction satisfies all input requirements: disjoint nonempty supports, positive binary-rational masses, explicitly specified signed rational valuations, and a rational feasible initial matching.
The dense valuation table contains \(\tau m(\tau-m)\) entries. Every coefficient has \(O(\log\tau)\) bits; the only coefficient whose magnitude grows with the formula is \(-(k-\tfrac12)\). The reduction can therefore be constructed in
\( O\!\left(\tau m(\tau-m)\log\tau\right) \)
bit operations, with output length
\( L=O\!\left(\tau m(\tau-m)\log\tau\right). \)
The preceding two directions establish the exact equivalence
\( \text{formula satisfiable} \quad\Longleftrightarrow\quad \text{constructed continuous society admits a blocking deviation}. \)
The soundness argument makes no integrality assumption: it applies to arbitrary real masses. This proves the requested \(\mathrm{NP}\)-hardness classification.
⟨structured verdict parsed — rendered above⟩
The proof is correct. It establishes \(\mathrm{NP}\)-hardness for the specified continuous problem, already with an empty initial matching and uniform positive dyadic masses. I found no major or minor mathematical gaps.
With \(x=0\), almost every coalition unit must acquire a partner to satisfy the acting requirement. Every newly matched endpoint must also belong to the coalition. These two conditions justify the stated equalities between coalition masses and incident matching masses, up to null sets.
Thus a type belongs to the coalition with positive mass exactly when it is active. Since initial utilities are zero, the stated nonnegative-utility and strict-positive-utility conditions correctly express blocking. The strict condition also excludes the zero matching, so the list implicitly enforces positive total coalition mass.
The sufficiency argument is valid for real masses: the capacity constraints permit the required finite partitions of the type intervals, and corresponding pieces have equal lengths and admit measure-preserving bijections. All selected units acquire partners. With an empty initial matching, preservation of outsider matches imposes no additional constraint.
The invoked theorem is that satisfiability of Boolean formulas in conjunctive normal form with three literals per clause is \(\mathrm{NP}\)-complete. The cited [MIT course materials](https://courses.csail.mit.edu/6.045/spring04/materials.html) explicitly identify this theorem.
The assumptions \(n,k\geq1\) exclude only trivial source instances and do not affect hardness. Each appended clause is tautological, so padding preserves satisfiability. The next power of two is less than twice the original positive value of \(2n+k+1\), unless that value is already a power of two. Consequently, the claimed linear padding bound is correct.
Repeated literals in the padding clause cause no problem: the proof explicitly defines \(\operatorname{Lit}(C_j)\) as a set of distinct literals, and satisfaction still guarantees that at least one member is true.
There are exactly \(2n+k+1=N\) distinct types on each side. Hence \(m=N\) and \(\tau=2N\). Because \(N\) is a power of two, the mass \(1/N\) is positive and dyadic, and the masses total one on each side. The initial matching is rational and feasible.
Each displayed utility is a linear function of type-pair masses, so it defines an admissible rational valuation row. Every undesignated pair contributes exactly \(-1\) to every type’s utility. The designated pairs are distinct, and the remaining displayed coefficients are consistent with the utility table.
In particular, these utilities impose no unallowed restriction on valuations: signed valuations and externalities from pairs not incident to the evaluating type are expressly permitted.
The selected designated edges have distinct endpoint types. Giving each selected edge mass \(s=1/N\) therefore respects every capacity constraint.
For an active literal type, the opposite literal edge has zero mass, so its utility is zero. Each clause has a true literal, whose designated edge carries mass \(s\); using distinct literals still gives \(\lambda_j(z)\geq s\). Thus every active clause type has nonnegative utility.
The trigger calculation is correct:
\(ks-(k-\tfrac12)s=\tfrac12s>0\).
Both trigger types are active, and \(K\) has utility zero. Therefore all active types weakly gain and an active type strictly gains. Section 1 supplies the required unit-level deviation, including the acting condition.
Under the assumption \(E>0\), every literal type has strictly negative utility, independently of whether its opposite literal mass is positive. Blocking therefore forces every literal type to be inactive, which forces all designated literal masses and all \(\lambda_j(z)\) to vanish.
Every \(B_j\) then has strictly negative utility, forcing each \(c_j=0\). With these masses zero, \(H\) also has strictly negative utility because \(k-\tfrac12>0\) and \(h\geq0\); its inactivity forces \(h=0\). The remaining \(A_j\) types and \(K\) consequently have utility \(-E<0\).
This exhausts the type list. No type can be active, contradicting a positive-mass deviation. The argument covers endpoints of undesignated edges as well as designated edges: activity was defined using all incident mass. Hence \(E=0\) follows rigorously.
If \(z_i^+>0\), its male endpoint is active and must have nonnegative utility. With \(E=0\), this forces \(z_i^-=0\). The symmetric implication is equally valid. Positive literal masses therefore cannot encode conflicting truth choices.
If \(h=0\), any positive \(c_j\) would activate \(A_j\) with negative utility. Thus all clause masses would vanish. Since undesignated mass has already been excluded, only literal edges could remain. Every active literal type would have utility zero by the consistency argument, leaving no active strict beneficiary. This contradicts blocking and proves \(h>0\).
For a positive clause mass, activity of \(A_j\) gives \(c_j\leq h\); the bound also holds for a zero clause mass. Activity of \(H\) gives
\(\sum_j c_j\geq(k-\tfrac12)h\).
If any clause mass were zero, the remaining masses could sum to at most \((k-1)h\), strictly below the required lower bound because \(h>0\). This calculation is valid also for \(k=1\). Hence every clause mass is positive.
Every \(B_j\) is consequently active, forcing \(\lambda_j(z)\geq h>0\). Since literal masses are nonnegative, each clause contains a positive-mass literal. Section 4.2 ensures that the resulting truth choices are consistent, and arbitrary choices for variables with both masses zero cannot invalidate the identified true literal in any clause. The extracted assignment satisfies the padded formula and therefore the original formula.
The dense table has exactly \(\tau m(\tau-m)\) valuation entries. The coefficient \(-(k-\tfrac12)\) has \(O(\log\tau)\) bits; all other valuation coefficients have constant size. Masses and type identifiers also fit within the stated total output-length bound.
The stated construction bound
\(O(\tau m(\tau-m)\log\tau)\)
is consistent with generating the explicit table. Since padding makes \(\tau\) linear in the source variable-and-clause count, this is a polynomial-time reduction.
Both directions apply to the intended continuous semantics. In particular, the converse never assumes integral, rational, or uniformly sized deviation masses. Restricting the reduction to an empty initial matching is legitimate because these are valid instances of the full problem, and zero initial type-pair masses leave no positive-measure realization-dependent matches.
The conclusion establishes hardness, not membership in \(\mathrm{NP}\); the prover does not claim the latter. No additional clarification is needed to verify the claimed result.
⟨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.