Answer: \(\mathrm{NP}\text{-hard}\); the rational welfare-threshold decision problem is \(\mathrm{NP}\text{-complete}\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing the maximum internally stable pair- wise matching in weighted graphs is NP-HARD. The proof can be found in the full version. L-k exchange in unweighted graphs Applying a similar approach as in the previous setting, we obtain a more general tight bound for L-k exchange. The only difference is that for large L, small odd cycles can now be matched directly. So the worst case ratio becomes better but cannot exceed 1 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), reciprocal compatibility between types, strict rankings \(\succ_t\) over compatible partner types, and rational arc weights \(w_{tu}\) consistent with those rankings, choose pair masses \(x_{\{t,u\}}\ge 0\). Let \(d_{tu}=x_{\{t,u\}}\) for \(t\ne u\) and \(d_{tt}=2x_{\{t,t\}}\), and require \(\sum_{u\in T}d_{tu}\le \mu_t\) for every type. Maximize \(\sum_{t<u}(w_{tu}+w_{ut})x_{\{t,u\}}+\sum_{t\in T}2w_{tt}x_{\{t,t\}}\), subject to internal stability: for each compatible pair \(t,u\), define \(A_{t,u}=\sum_{v:\,u\succ_t v}d_{tv}\); require that \(A_{t,u}\) and \(A_{u,t}\) are not both positive. What is the computational complexity of finding a maximum-welfare mass matching satisfying these conditions?
A society is given by its support: a list \(T\) 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. Reciprocal compatibility is specified by a set \(C\) of unordered type pairs, possibly including diagonal pairs; let \(m=|C|\) and let \(L\) be the total input bit length.
Each type \(t\) has a strict ranking \(\succ_t\) over its compatible partner types and nonnegative rational weights \(w_{tu}\), satisfying \(w_{tu}>w_{tv}\Rightarrow u\succ_t v\); equal weights are allowed despite strict rankings.
Choose real pair masses \(x_{\{t,u\}}\ge0\) for compatible pairs, setting all incompatible pair masses to zero. Define \(d_{tu}=x_{\{t,u\}}\) for \(t\ne u\) and \(d_{tt}=2x_{\{t,t\}}\), and require \(\sum_u d_{tu}\le\mu_t\). A diagonal pair matches distinct individuals of the same type.
For each compatible pair, including diagonal pairs, define \(A_{t,u}=\sum_{v:\,u\succ_t v}d_{tv}\). Internal stability requires \(A_{t,u}=0\) or \(A_{u,t}=0\). Unmatched mass does not participate in blocking deviations.
Welfare is \(W(x)=\sum_{\{t,u\}\in C,\,t\ne u}(w_{tu}+w_{ut})x_{\{t,u\}}+\sum_{\{t,t\}\in C}2w_{tt}x_{\{t,t\}}\).
Is finding an internally stable mass matching maximizing \(W(x)\) solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite individual agents with strict preferences and ranking-consistent arc weights, maximum-welfare internally stable pairwise matching is NP-hard. [Liu, Tang and Fang (2014)](https://ojs.aaai.org/index.php/AAAI/article/download/8883/8742). No result settling the exact mass problem above was located in the literature search.
Finding an internally stable mass matching of maximum welfare is \(\mathrm{NP}\text{-hard}\), already when there are no diagonal pairs, all types have the same dyadic mass, and every arc weight belongs to \(\{0,1\}\).
The proof is a direct reduction from Independent Set. It handles arbitrary real pair masses without an integrality assumption.
Let \(G=(V,E)\) be a simple undirected graph with \(n=|V|\ge 1\). Write \(\alpha(G)\) for its maximum independent-set size. The standard Independent Set decision problem asks whether \(\alpha(G)\ge k\) and is \(\mathrm{NP}\text{-complete}\).
Let \(q\) be the smallest power of two satisfying \(q\ge 2n\). Construct two types \(a_v,b_v\) for each \(v\in V\), together with \(q-2n\) isolated types. Give every type mass \(1/q\). Thus all masses are positive dyadic rationals and sum to \(1\).
The compatible pairs are exactly
\[ C=\bigl\{\{a_v,b_v\}:v\in V\bigr\} \;\cup\; \bigl\{\{b_u,b_v\}:\{u,v\}\in E\bigr\}. \]
Here and below, this displayed expression uses the same mathematical notation as the inline formulas.
Specify preferences and weights as follows:
These weights satisfy the required ranking consistency. At each \(b_v\), all weights are equal, so the implication \(w_{b_vt}>w_{b_vs}\Rightarrow t\succ_{b_v}s\) holds vacuously. At each \(a_v\), there is only one compatible partner.
For any feasible matching, welfare is therefore
\(\displaystyle W(x)=\sum_{v\in V}x_{\{a_v,b_v\}}.\)
The private pairs carry welfare; the pairs corresponding to edges of \(G\) carry zero welfare.
Let \(x\) be any internally stable feasible matching, and define
\(\displaystyle S(x)=\{v\in V:x_{\{a_v,b_v\}}>0\}.\)
Claim. The set \(S(x)\) is independent in \(G\).
Suppose instead that \(\{u,v\}\in E\) with \(u,v\in S(x)\). Since \(b_u\) ranks \(b_v\) above \(a_u\), the summation defining \(A_{b_u,b_v}\) includes the mass assigned to \(a_u\). All its terms are nonnegative, so
\(\displaystyle A_{b_u,b_v}\ge d_{b_u,a_u}=x_{\{a_u,b_u\}}>0.\)
Similarly,
\(\displaystyle A_{b_v,b_u}\ge x_{\{a_v,b_v\}}>0.\)
This contradicts internal stability for the compatible pair \(\{b_u,b_v\}\). Thus \(S(x)\) is independent.
The capacity constraint at \(a_v\) gives \(x_{\{a_v,b_v\}}\le 1/q\). Consequently,
\(\displaystyle W(x)=\sum_{v\in S(x)}x_{\{a_v,b_v\}}\le \frac{|S(x)|}{q}\le\frac{\alpha(G)}q.\)
This argument applies to arbitrary real masses. In particular, arbitrarily small positive private-pair masses at adjacent vertices are still forbidden.
Let \(S\subseteq V\) be any independent set. Set
\(\displaystyle x_{\{a_v,b_v\}}=\begin{cases}1/q,&v\in S,\\0,&v\notin S,\end{cases}\)
and set every other pair mass to zero.
Every selected type uses exactly its capacity; every remaining type uses zero capacity. Hence the matching is feasible.
To verify internal stability, consider each kind of compatible pair:
These are all compatible pairs. The matching is therefore internally stable and has welfare \(|S|/q\).
Taking a maximum independent set proves the exact identity
\(\displaystyle \max_{x\text{ internally stable}}W(x)=\frac{\alpha(G)}q.\)
Because \(q<4n\), the constructed instance has support size \(\tau=q<4n\) and compatibility size \(m=n+|E|\). Each mass requires \(O(\log n)\) bits; the weights are \(0\) or \(1\); and all preference lists can be written in polynomial time. Thus the total input length is polynomial in the graph’s encoding length.
For an Independent Set instance \((G,k)\), use welfare threshold \(B=k/q\). The identity above gives
\(\displaystyle \exists x\text{ internally stable with }W(x)\ge B \quad\Longleftrightarrow\quad \alpha(G)\ge k.\)
Hence the welfare-threshold decision problem is \(\mathrm{NP}\text{-hard}\), and exact welfare maximization is \(\mathrm{NP}\text{-hard}\). A polynomial-time optimizer in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
This establishes hardness directly for the mass formulation, complementing the finite-agent result in [Liu, Tang and Fang, Theorem 4](https://ojs.aaai.org/index.php/AAAI/article/download/8883/8742).
For completeness, allow all the features of the original problem, including diagonal pairs, and let \(B\) be a rational threshold.
Suppose a real feasible internally stable matching with welfare at least \(B\) exists. For each compatible pair, select an endpoint whose dissatisfaction sum is zero. For a diagonal pair, select its single endpoint.
Impose the selected equations \(A_{t,u}=0\), together with nonnegativity, the capacity constraints, and \(W(x)\ge B\). These form a rational linear system with \(m\) variables and polynomially many constraints. Its feasible set is nonempty by construction and bounded: every off-diagonal coordinate satisfies \(x_{\{t,u\}}\le\mu_t\le1\), while every diagonal coordinate satisfies \(x_{\{t,t\}}\le\mu_t/2\le1/2\).
A nonempty bounded rational polyhedron has a vertex. Such a vertex has polynomial encoding length here: after clearing denominators, all coefficients have polynomial bit length; a vertex is determined by \(m\) independent active constraints; and Cramer’s rule bounds its numerator and denominator lengths polynomially. Explicitly, if the integer entries have magnitude at most \(2^h\), the relevant determinants have magnitude at most \(m!2^{mh}\).
Thus a polynomial-size rational matching exists whenever a real witness exists. A verifier can check its capacities, welfare, and every stability disjunction using exact rational arithmetic in polynomial time. The case \(m=0\) is immediate.
Therefore the welfare-threshold decision problem is \(\mathrm{NP}\text{-complete}\), and the optimization question is settled as \(\mathrm{NP}\text{-hard}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated mass problem: exact welfare maximization is NP-hard, even with no diagonal pairs, equal dyadic masses, and arc weights in \(\{0,1\}\). The additional claim that the rational welfare-threshold decision problem is NP-complete is also justified.
No major or minor mathematical issues were found.
The reduction starts from Independent Set on an explicitly represented simple undirected graph. Its stated decision version is the standard NP-complete problem. Restricting to \(n\ge 1\) does not affect hardness.
The smallest power of two \(q\ge 2n\) satisfies \(2n\le q<4n\). The construction therefore has exactly \(q\) types, each with positive dyadic mass \(1/q\), and their masses sum to \(1\). Adding isolated types is permitted: the task imposes no requirement that every type have a compatible partner.
The compatible pairs are reciprocal unordered pairs, with no diagonals. Simplicity of the graph ensures the stated count \(m=n+|E|\).
The rankings are strict and satisfy the task’s weight condition. In particular, ranking graph neighbors above the private partner at each \(b_v\) is allowed despite all outgoing weights being zero. The task explicitly permits equal weights with strict rankings.
Each private pair has total arc weight \(1\), and each graph-edge pair has total arc weight \(0\). Thus the displayed welfare formula is correct.
The definition
\[
S(x)=\{v:x_{\{a_v,b_v\}}>0\}
\]
uses positive mass, without assuming integrality or a minimum positive allocation.
For adjacent vertices \(u,v\in S(x)\), the ranking at \(b_u\) places \(a_u\) below \(b_v\). Hence the summation defining \(A_{b_u,b_v}\) contains \(d_{b_u,a_u}\). Since this pair is off-diagonal,
\[
d_{b_u,a_u}=x_{\{a_u,b_u\}}>0.
\]
All other summands are nonnegative. The same argument applies at \(b_v\).
Both dissatisfaction sums are consequently positive, contradicting precisely the stability disjunction required for \(\{b_u,b_v\}\). Therefore \(S(x)\) is independent.
The capacity bound at \(a_v\) gives \(x_{\{a_v,b_v\}}\le 1/q\). Summing over the independent support proves
\[
W(x)\le |S(x)|/q\le\alpha(G)/q.
\]
This establishes the upper bound for every feasible internally stable real allocation, including allocations with arbitrarily small positive coordinates.
The proposed allocation from an independent set assigns \(1/q\) to its private pairs and zero elsewhere. Each participating type has exactly one incident positive pair and uses its full capacity; all other types use zero capacity. Feasibility follows.
The stability check exhausts all compatible pairs:
This check also covers compatible pairs assigned zero mass, as the task requires. It uses the specified exclusion of unmatched mass from blocking deviations.
The allocation has welfare \(|S|/q\). Together with the upper bound, taking a maximum independent set establishes the claimed exact optimum identity.
The support size, compatibility count, mass encodings, weights, and preference lists all have polynomial size in the graph’s encoding length. The threshold \(B=k/q\) also has polynomial encoding length.
The optimum identity gives both directions of the stated threshold equivalence. Thus the reduction proves NP-hardness of the threshold decision problem and of exact welfare maximization. Its polynomial bounds explicitly cover the task’s parameters \(m,\tau,L\).
The citation to [Liu, Tang and Fang, Theorem 4](https://ojs.aaai.org/index.php/AAAI/article/download/8883/8742) accurately identifies their finite weighted pairwise-matching hardness statement. It is contextual; the mass reduction does not depend on transferring that theorem.
For any real witness, stability guarantees an endpoint with zero dissatisfaction for each off-diagonal pair. For a diagonal pair, the two dissatisfaction expressions coincide, so stability requires that single expression to be zero. The proposed selection therefore exists in every case.
After fixing these selections, the imposed equalities, capacities, nonnegativity constraints, and welfare threshold form a nonempty rational polyhedron. Every point satisfying the selected equations satisfies the original stability disjunctions.
The coordinate bounds are correct: an off-diagonal coordinate is bounded by either endpoint’s capacity, and a diagonal coordinate is bounded by half its type’s capacity. Hence the polyhedron is bounded.
The invoked vertex statement applies to a nonempty bounded polyhedron, including one of lower dimension. For \(m>0\), a vertex is determined by \(m\) independent active constraints, as stated.
Clearing denominators produces integer coefficients of polynomial bit length in the complete decision input, including the rational threshold. The determinant bound \(m!2^{mh}\) yields polynomial numerator and denominator lengths through Cramer’s rule. Thus the real witness can be replaced by a polynomial-size rational witness.
Exact rational verification of capacities, welfare, and all stability disjunctions takes polynomial time. The separately mentioned case \(m=0\) has only the empty allocation and is immediate.
Consequently, NP membership and NP-hardness together justify NP-completeness of the rational threshold problem.
None is required. The construction, stability arguments, encoding bounds, and rational-certificate argument are sufficient as written.
⟨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.