Answer: \(\mathrm{NP}\)-complete
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCESM and CESR are NP-complete even for complete and strict preferences.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type sets \(I\) and \(J\), rational masses \(p_i\) and \(q_j\) summing to \(1\) on each side, and strict rankings of opposite-side types, decide whether there is a coupling \(x_{ij}\geq 0\) with row sums \(p_i\) and column sums \(q_j\) such that, on the positive cells \((i,j)\), neither side’s directed envy graph has a cycle. In the \(I\)-side graph, an arc from \((i,j)\) to \((i',j')\) means \(j'\succ_i j\); in the \(J\)-side graph, it means \(i'\succ_j i\).
The input consists of disjoint, nonempty finite type sets \(I,J\), positive binary rational masses \(p_i,q_j\) with \(\sum_{i\in I}p_i=\sum_{j\in J}q_j=1\), and a complete strict ranking of opposite-side types for every type. All opposite-side types are acceptable.
A society is given by its support: the list of types with positive mass and their binary rational masses. Let \(\tau=|I|+|J|\) be the total support size, not the number of possible preference types; let \(m=\max\{|I|,|J|\}\) and let \(L\) be the total input bit length. State running times in \(m,\tau,L\).
A coupling is a real matrix \(x\in\mathbb{R}_{\geq0}^{I\times J}\) satisfying \(\sum_{j\in J}x_{ij}=p_i\) and \(\sum_{i\in I}x_{ij}=q_j\); mass may be split among partners.
Both directed envy graphs have vertex set \(S(x)=\{(i,j):x_{ij}>0\}\). For distinct vertices \((i,j),(i',j')\), the first graph has an arc from the former to the latter exactly when \(j'\succ_i j\); the second has that arc exactly when \(i'\succ_j i\). Vertices sharing a type are included in these comparisons.
A coupling is coalitionally exchange-stable when both graphs are acyclic.
Is deciding whether a coalitionally exchange-stable coupling exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite societies with equally many agents on each side, existence of a coalitionally exchange-stable matching is NP-complete even with complete strict preferences; such a matching necessarily matches everyone. [Chen, Chmurovic, Jogl, and Sorge](https://arxiv.org/pdf/2105.05725v2).
No result settling the exact coupling problem defined above was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when \(|I|=|J|=m\) and every mass equals \(1/m\).
The key fact is that acyclicity is preserved when support vertices are deleted. For equal masses, every coupling has a perfect matching inside its support, so allowing mass splitting does not change existence.
For any set \(T\subseteq I\times J\), define its two envy graphs by the comparisons in the question.
Lemma 1. If both envy graphs on \(T\) are acyclic, then both envy graphs on every subset \(T'\subseteq T\) are acyclic.
Proof. Whether an arc exists between two vertices depends only on those vertices and the input preferences. Consequently, each graph on \(T'\) is the induced subgraph of the corresponding graph on \(T\). A directed cycle in an induced subgraph would also be a directed cycle in the original graph. This applies equally to vertices sharing a type. \(\square\)
In particular, if \(x\) is stable and \(y\) is any coupling with \(S(y)\subseteq S(x)\), then \(y\) is stable.
Lemma 2. Suppose \(|I|=|J|=n\) and \(p_i=q_j=1/n\) for all types. Every coupling \(x\) has a perfect matching contained in \(S(x)\).
Proof. Form the undirected bipartite graph \(H\) with parts \(I,J\) and edge set \(S(x)\). For \(A\subseteq I\), write \(N_H(A)\) for its neighborhood. Since positive entries from rows in \(A\) can occur only in columns in \(N_H(A)\),
\(\displaystyle \frac{|A|}{n} =\sum_{i\in A}\sum_{j\in N_H(A)}x_{ij} \leq \sum_{j\in N_H(A)}\sum_{i\in I}x_{ij} =\frac{|N_H(A)|}{n}.\)
Thus \(|N_H(A)|\geq |A|\) for every \(A\subseteq I\). Hall’s marriage theorem states that this condition is sufficient for a finite bipartite graph to have a matching covering \(I\). Because \(|I|=|J|\), that matching is perfect. \(\square\)
Corollary. For equal masses, a stable coupling exists if and only if a coalitionally exchange-stable perfect matching exists with the same preferences.
Proof. Let \(x\) be a stable coupling. By Lemma 2, choose a perfect matching \(M\subseteq S(x)\). Give each edge of \(M\) mass \(1/n\), obtaining a coupling \(y\). Lemma 1 proves that both envy graphs of \(y\) are acyclic.
To identify these graphs with matching envy, write the matching as a bijection \(\pi:I\to J\). The map \(i\mapsto(i,\pi(i))\) identifies the first support graph with the graph on first-side agents whose arcs satisfy \(\pi(i')\succ_i\pi(i)\). Likewise, \(j\mapsto(\pi^{-1}(j),j)\) identifies the second support graph with the second-side matching envy graph.
In a perfect bipartite matching, envy arcs cannot cross between sides: the partner of an agent on the other side lies on the evaluating agent’s own side and is unacceptable. Hence an exchange-blocking coalition is precisely a directed cycle in one of these two graphs. Their acyclicity proves that \(M\) is coalitionally exchange-stable.
Conversely, assigning mass \(1/n\) to each edge of a coalitionally exchange-stable perfect matching gives a coupling with these same two acyclic graphs. \(\square\)
Theorem 2 of Chen, Chmurovic, Jogl, and Sorge establishes that deciding existence of a coalitionally exchange-stable marriage matching is \(\mathrm{NP}\)-complete for complete strict preferences. Their marriage instances have equally sized sides. [Source: Theorem 2 and the definitions in Section 2](https://arxiv.org/pdf/2105.05725v2).
Take such an instance with \(n\) agents on each side. Create one distinct type for each agent, retain all preference lists, and assign every type mass \(1/n\). This satisfies every premise of the coupling problem: both supports are nonempty and disjoint, masses are positive binary rationals summing to one on each side, and preferences are complete and strict.
The source matching problem requires no additional perfectness restriction. If a matching were imperfect, equal side sizes would leave an unmatched agent on each side. These two agents would each prefer the other’s unmatched “partner”—the other agent itself—to remaining unmatched, forming an exchange-blocking pair. Thus every stable source matching is perfect.
The corollary therefore proves both directions of the reduction.
For the resulting coupling instance, \(m=n\) and \(\tau=2n\). Under ordinary binary index encoding, its length is \(L=O(m\tau\log(m+1))\); constructing it takes \(O(m\tau\log(m+1))\) bit operations by copying the rankings and writing the masses. No enumeration of possible preference types occurs.
This proves \(\mathrm{NP}\)-hardness.
Real-valued couplings do not obstruct membership in \(\mathrm{NP}\). We prove a stronger certificate property.
Lemma 3. If a stable coupling exists, then a stable rational coupling exists with at most \(\tau-1\) positive entries, each of binary encoding length \(O(L)\).
Proof. Start with any stable coupling \(x\). Regard its support as an undirected bipartite graph on \(I\cup J\).
If this graph contains a cycle, that cycle has even length. Partition its edges into alternating sets \(E_-\) and \(E_+\), and let \(\delta=\min_{e\in E_-}x_e>0\). Subtract \(\delta\) on \(E_-\) and add \(\delta\) on \(E_+\).
Each cycle vertex has one incident edge of each sign, so all row and column sums remain unchanged. Entries remain nonnegative; at least one becomes zero. Every increased entry was already positive, so the support strictly decreases. Stability is preserved by Lemma 1.
Repeating this operation finitely many times produces a coupling \(y\) whose undirected support is a forest. A forest on \(\tau\) vertices has at most \(\tau-1\) edges.
It remains to bound the entries’ encoding lengths. Write the input masses as \(p_i=a_i/b_i\) and \(q_j=c_j/d_j\), with positive integer denominators, and define \(D=(\prod_{i\in I}b_i)(\prod_{j\in J}d_j)\). The binary length of \(D\) is \(O(L)\), and all scaled marginals \(Dp_i,Dq_j\) are integers.
Consider the edge weights \(Dy_e\) on the support forest. In any component containing an edge, a leaf’s unique incident edge has weight equal to that leaf’s residual marginal. Initially these residual marginals are integers. Remove the leaf and its edge, subtracting that integer weight from the neighbor’s residual marginal. The remaining residual marginals are still integers.
Successive leaf removal exhausts the forest, proving that every \(Dy_e\) is an integer. Since \(0<y_e\leq 1\), every positive entry has the form \(k_e/D\), where \(1\leq k_e\leq D\). Both numerator and denominator have \(O(L)\) bits. \(\square\)
A certificate lists at most \(\tau-1\) type pairs and their positive integer numerators \(k_e\), using the common denominator \(D\) computed from the input. Its length is \(O(\tau L)\).
A verifier checks that the pairs are distinct, checks positivity and all scaled marginal equations, and constructs both envy graphs on the listed pairs. It checks every ordered pair of distinct support vertices, including pairs sharing a type, and tests both graphs for directed cycles.
There are \(O(m\tau)\) ranking entries and \(O(\tau^2)\) possible envy arcs. Using elementary binary arithmetic, a conservative verification bound is \(O((m\tau+\tau^2)L^2)\) bit operations. Lemma 3 supplies an accepted certificate for every yes-instance; an accepted certificate directly defines a stable coupling. Therefore the problem belongs to \(\mathrm{NP}\).
The exact coupling problem is \(\mathrm{NP}\)-complete. In particular, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). The hardness already holds for uniform masses, where support restriction and Hall’s theorem rigorously eliminate the apparent advantage of splitting mass.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the exact coupling problem is \(\mathrm{NP}\)-complete, with hardness already holding for equal side sizes and uniform masses. The argument resolves the assigned task. I found no major or minor mathematical issues.
Lemma 1 correctly observes that envy arcs depend only on the two support vertices and the fixed rankings. Restricting the support therefore produces induced subgraphs of both envy graphs. Any directed cycle in a restricted graph would remain a cycle in the original graph.
This reasoning also covers vertices sharing a type, as required by the task. The subsequent application explicitly requires the smaller-support matrix to remain a coupling, so it does not confuse support restriction with preservation of marginals.
In Lemma 2, the marginal equations give the stated equality for every subset \(A\subseteq I\). Nonnegativity justifies the inequality obtained by including all rows incident to its neighborhood. Consequently, Hall’s condition holds.
The prover states the relevant form of Hall’s theorem and checks its hypotheses: the support graph is finite and bipartite, and every first-side subset has at least as many neighbors. Equal side sizes turn a matching covering \(I\) into a perfect matching. The empty subset and the case \(n=1\) introduce no exceptions.
Assigning mass \(1/n\) to the extracted perfect-matching edges satisfies every marginal equation. Its support is contained in the original stable support, so Lemma 1 applies.
Both displayed identifications of support vertices with matched agents are bijections and preserve the respective envy-arc conditions. For a perfect bipartite matching, an agent cannot envy an agent on the opposite side: that agent’s partner belongs to the evaluating agent’s own side and is unacceptable. Thus every exchange-blocking cycle lies entirely within one side.
The paper defines exchange-blocking coalitions through cyclic envy sequences, exactly as needed for this identification. The reverse implication uses the same graph correspondence and is valid. See [Section 2 of the cited paper](https://arxiv.org/pdf/2105.05725v2).
Theorem 2 of the cited version states that Coalitional Exchange-Stable Marriage is \(\mathrm{NP}\)-complete even for complete and strict preferences. Its bipartite profiles have equally sized sides. These are precisely the source-instance properties invoked by the prover. See [Theorem 2 and Section 2](https://arxiv.org/pdf/2105.05725v2).
The argument excluding imperfect stable source matchings is also correct under the paper’s convention that an unmatched agent is their own partner and prefers every acceptable agent to remaining unmatched. An imperfect matching on equally sized sides leaves an unmatched agent on each side; completeness makes those two agents an exchange-blocking pair.
Creating one distinct type per agent preserves all rankings and satisfies the task’s support-based input definition. The rational mass \(1/n\) has a binary numerator–denominator encoding of length \(O(\log(n+1))\). The corollary establishes both directions of the reduction.
The claimed construction bound \(O(m\tau\log(m+1))\) is valid under the stated binary index encoding. It uses the actual listed support and does not enumerate possible preference types.
Every undirected support cycle is even because the graph is bipartite. The alternating adjustment preserves each marginal, maintains nonnegativity, removes at least one positive entry, and introduces no support edge. Stability consequently persists.
Since the support is finite and strictly decreases at every adjustment, the procedure terminates with a forest. Its bound of at most \(\tau-1\) edges is valid, including disconnected forests.
The denominator product \(D\) has \(O(L)\) bits because the input already contains all its factors. Scaling makes every marginal integral. The leaf-removal argument correctly propagates integral residual marginals and establishes that every scaled forest-edge weight is integral. Existing feasibility justifies identifying each leaf-edge weight with its residual marginal.
Each coupling entry is at most the total mass \(1\), so the bound \(1\leq k_e\leq D\) follows. Hence all certificate weights have \(O(L)\)-bit representations. The argument does not require the initial real coupling to be explicitly computable.
The listed checks establish that the certificate defines a coupling and that both of its envy graphs are acyclic. Testing every ordered pair includes the shared-type comparisons required by the problem.
The certificate length \(O(\tau L)\) and the conservative verification bound \(O((m\tau+\tau^2)L^2)\) are polynomial in the requested parameters. Computing scaled marginals, summing certificate weights, constructing ranking comparisons, and testing graph acyclicity fit within that bound.
Thus the write-up establishes membership in \(\mathrm{NP}\) for arbitrary input rational masses and \(\mathrm{NP}\)-hardness for uniform masses. No additional clarification or repair 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.