Answer: \(\mathrm{NP}\)-complete, even with equal dyadic masses and \(m=\tau=2^s\).
Theorem 4.16 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet 𝐼 be an sr instance and 𝑘 be an integer. Egal-Dec-SR-SP, the problem of deciding whether 𝐼 admits a stable partition with egalitarian cost at most 𝑘, is NP-complete, regardless of whether 𝐼 is guaranteed to be solvable or unsolvable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a nonatomic society with a finite type set \(T\), rational masses \(\mu_i>0\) summing to \(1\), strict rankings \(r_i\) of partner types, and a rational bound \(K\), decide whether there exist masses \(q_{i,j,k}\ge 0\) such that \(\sum_{j,k}q_{i,j,k}=\mu_i\), \(\sum_{a,k}q_{a,i,k}=\mu_i\), \(\sum_{a,j}q_{a,j,i}=\mu_i\), and \(\sum_k q_{i,j,k}=\sum_\ell q_{j,\ell,i}\) for every \(i,j\in T\). Require \(q_{i,j,k}=0\) whenever \(r_i(j)>r_i(k)\); define \(b_{i,h}(q)=\sum_{j,k:\,r_i(h)<r_i(k)}q_{i,j,k}\), and require \(b_{i,h}(q)=0\) or \(b_{h,i}(q)=0\) for distinct \(i,h\), and \(b_{i,i}(q)=0\). The decision question is whether such a stable assignment has \(\frac12\sum_{i,j,k}q_{i,j,k}(r_i(j)+r_i(k))\le K\).
A nonatomic society is given by its support: the list of \(\tau\) types \(T\) with positive binary-rational masses \(\mu_i\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; the number of partner types is \(m=\tau\ge2\).
Each type has a complete strict ranking \(r_i:T\to\{1,\ldots,m\}\), with smaller ranks preferred and \(r_i(i)=m\). Same-type partnerships involve distinct individuals and are allowed; individuals of the same type are indifferent as partners. The input also contains \(K\in\mathbb Q\); let \(L\) be the total input bit length.
An assignment consists of real masses \(q_{i,j,k}\ge0\), representing type \(i\) individuals with successor type \(j\) and predecessor type \(k\). All indices and sums below range over \(T\).
Require \(\sum_{j,k}q_{i,j,k}=\sum_{a,k}q_{a,i,k}=\sum_{a,j}q_{a,j,i}=\mu_i\) for every \(i\), and \(\sum_kq_{i,j,k}=\sum_\ell q_{j,\ell,i}\) for every \(i,j\).
Require \(q_{i,j,k}=0\) whenever \(r_i(j)>r_i(k)\). Define \(b_{i,h}(q)=\sum_{j,k:\,r_i(h)<r_i(k)}q_{i,j,k}\); stability requires \(b_{i,h}(q)=0\) or \(b_{h,i}(q)=0\) for every distinct \(i,h\), and \(b_{i,i}(q)=0\) for every \(i\).
The decision problem asks whether such a stable assignment satisfies \(\frac12\sum_{i,j,k}q_{i,j,k}(r_i(j)+r_i(k))\le K\).
Is this decision problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite even societies with complete strict preferences, deciding whether a stable partition has egalitarian cost at most a given bound is NP-complete, even under either a solvability or an unsolvability promise ([Glitzner–Manlove](https://arxiv.org/html/2406.00437v4)).
Minimum-cost non-bipartite stable allocation with general edge costs is NP-hard ([Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)); this concerns a different allocation formulation and cost domain. No result settling the exact mass problem above was located.
The decision problem is \(\mathrm{NP}\)-complete, even when \(m=\tau=2^s\) and every mass is \(\mu_i=2^{-s}\). Consequently, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
The essential step is to prove that, for equal masses, allowing arbitrary real assignments does not improve the minimum cost over finite stable partitions.
Write the assignment cost as
\(\displaystyle C(q)=\frac12\sum_{i,j,k}q_{i,j,k}\bigl(r_i(j)+r_i(k)\bigr).\)
A symmetric pair allocation is a matrix \(y\) satisfying
\(\displaystyle y_{i,j}=y_{j,i}\geq0,\qquad \sum_j y_{i,j}=\mu_i.\)
Define
\(\displaystyle D_{i,h}(y)=\sum_{j:\,r_i(h)<r_i(j)}y_{i,j},\qquad F(y)=\sum_{i,j}r_i(j)y_{i,j}.\)
Call \(y\) stable if, for every distinct \(i,h\), either \(D_{i,h}(y)=0\) or \(D_{h,i}(y)=0\). The self condition is automatic: since \(r_i(i)=m\), we always have \(D_{i,i}(y)=b_{i,i}(q)=0\).
Lemma 1. The original formulation and the symmetric formulation have exactly the same attainable costs.
Proof. Given a feasible \(q\), put
\(\displaystyle x_{i,j}=\sum_k q_{i,j,k},\qquad y_{i,j}=\frac{x_{i,j}+x_{j,i}}2.\)
The marginal constraints give row and column sums \(\mu_i\) for \(x\), so \(y\) has the required row sums. Edge consistency gives
\(\displaystyle x_{k,i}=\sum_j q_{i,j,k}.\)
For a fixed \(i,h\), define
\(\displaystyle U_{i,h}=\sum_{j:\,r_i(h)<r_i(j)}x_{i,j},\qquad B_{i,h}=\sum_{k:\,r_i(h)<r_i(k)}x_{k,i}=b_{i,h}(q).\)
Every positive triple satisfies \(r_i(j)\leq r_i(k)\). Thus every triple counted in \(U_{i,h}\) is also counted in \(B_{i,h}\), and
\(\displaystyle 0\leq U_{i,h}\leq B_{i,h},\qquad D_{i,h}(y)=\frac{U_{i,h}+B_{i,h}}2.\)
Consequently,
\(\displaystyle D_{i,h}(y)=0\quad\Longleftrightarrow\quad b_{i,h}(q)=0.\)
This proves preservation of stability. Moreover,
\(\displaystyle C(q)=\frac12\sum_{i,j}r_i(j)x_{i,j}+\frac12\sum_{i,k}r_i(k)x_{k,i}=F(y).\)
Conversely, given a stable symmetric allocation \(y\), set
\(\displaystyle q_{i,j,k}=\begin{cases}y_{i,j},&k=j,\\0,&k\neq j.\end{cases}\)
Its three marginals equal \(\mu_i\), by symmetry and the row sums of \(y\). Edge consistency reads \(y_{i,j}=y_{j,i}\), and the ranking constraint holds because successor and predecessor types coincide. Finally, \(b_{i,h}(q)=D_{i,h}(y)\) and \(C(q)=F(y)\). This proves the lemma. \(\square\)
We will repeatedly use the following consequence.
Support preservation. If \(y\) is stable and another feasible symmetric allocation \(y'\) satisfies
\(\displaystyle y_{i,j}=0\ \Longrightarrow\ y'_{i,j}=0,\)
then \(y'\) is stable. Indeed, each equality \(D_{i,h}(y)=0\) means that every corresponding worse-partner coordinate is zero; those coordinates remain zero in \(y'\).
A finite stable partition is a permutation \(\Pi\) satisfying
\(\displaystyle r_i(\Pi(i))\leq r_i(\Pi^{-1}(i))\)
for every \(i\), with no distinct \(i,h\) satisfying both
\(\displaystyle r_i(h)<r_i(\Pi^{-1}(i)),\qquad r_h(i)<r_h(\Pi^{-1}(h)).\)
For this section, include self ranks in its cost:
\(\displaystyle c^*(\Pi)=\frac12\sum_i\bigl(r_i(\Pi(i))+r_i(\Pi^{-1}(i))\bigr).\)
Lemma 2. Suppose all masses equal \(1/m\). From any stable assignment \(q\), there exists a finite stable partition \(\Pi\) such that
\(\displaystyle c^*(\Pi)\leq mC(q).\)
Conversely, every finite stable partition \(\Pi\) gives a stable assignment of cost \(c^*(\Pi)/m\).
Proof. Apply Lemma 1 and normalize by setting \(z=my\). Then \(z\) is symmetric and stable, every row sums to \(1\), and \(F(z)=mC(q)\).
Form a graph whose positive off-diagonal coordinates are edges and whose positive diagonal coordinates are loops. Count a loop twice in graph degree, although its variable occurs once in its row-sum equation.
Every vertex has a unique worst positive partner, because rankings of types are strict.
For a positive off-diagonal edge \(\{i,j\}\), stability implies that this edge is the worst positive edge at at least one endpoint. Otherwise both endpoints have a positive allocation to a partner worse than each other, giving \(D_{i,j}(z)>0\) and \(D_{j,i}(z)>0\).
Every positive loop is also its vertex’s worst positive edge, since self is ranked last. Therefore every edge is selected as the worst edge by at least one vertex. In each connected component,
\(\displaystyle |E|\leq |V|.\)
If a vertex \(i\) has graph degree \(1\), its only incident edge is an off-diagonal edge \(\{i,j\}\), and the row sum forces \(z_{i,j}=1\). The row sum at \(j\) then excludes every other positive incident coordinate. Hence this component is an isolated pair.
Every other component has minimum graph degree at least \(2\). Thus
\(\displaystyle 2|V|\leq\sum_{i\in V}\deg(i)=2|E|\leq2|V|.\)
All its degrees therefore equal \(2\). Such a connected component is either a single loop or a simple cycle.
A loop has weight \(1\). On a cycle, consecutive edge weights sum to \(1\); consequently, an odd cycle has all weights \(1/2\), while an even cycle has alternating weights \(\theta,1-\theta\).
On an even cycle, the allocation is a convex combination of its two alternating perfect matchings, with coefficients \(\theta\) and \(1-\theta\).
Both matching allocations satisfy the same row sums and use only edges already in the support. They preserve stability by support preservation. Since the cost is linear, at least one has cost no greater than the cycle allocation.
Replace every even cycle by such a matching. The resulting stable allocation \(\widehat z\) satisfies
\(\displaystyle F(\widehat z)\leq F(z),\)
and its components are isolated pairs, single loops, and odd cycles of weight \(1/2\).
At each vertex of an odd cycle, designate its better neighbor. An edge cannot be designated by both endpoints: each endpoint would then prefer the other to its remaining positive partner, contradicting stability.
There are exactly as many designations as cycle edges. Since each edge receives at most one designation, every edge receives exactly one.
Orient each edge from the endpoint designating it. Every vertex has one outgoing and one incoming edge, so the cycle becomes a directed cycle. Its successor is its better neighbor, and its predecessor is its worse neighbor.
Use these directed cycles, transpositions for isolated pairs, and fixed points for loops to define \(\Pi\). The successor-predecessor ranking condition holds. Furthermore, in every component the predecessor is the worst positive partner, so
\(\displaystyle D_{i,h}(\widehat z)>0\quad\Longleftrightarrow\quad r_i(h)<r_i(\Pi^{-1}(i)).\)
Stability of \(\widehat z\) therefore proves stability of \(\Pi\). The component weights give
\(\displaystyle c^*(\Pi)=F(\widehat z)\leq mC(q).\)
For the converse, define
\(\displaystyle q_{i,\Pi(i),\Pi^{-1}(i)}=\frac1m\)
and set every other coordinate to zero. Since \(\Pi\) is a permutation, all three marginals and edge-consistency equations hold. Its ranking and stability conditions are precisely those required for \(q\), and its cost is \(c^*(\Pi)/m\). \(\square\)
We use the following established finite results:
Their cost omits self ranks. Under the solvability promise there are no singleton cycles, so their cost equals \(c^*\). [Source: Glitzner–Manlove](https://arxiv.org/html/2406.00437v4).
Let \((I,k)\) be an instance of this promised hard problem, with an even number \(n\geq2\) of agents.
Choose the smallest power of two \(N\geq n\), and write \(d=N-n\). Since \(n\) and \(N\) are even, \(d\) is even.
Construct the mass instance as follows:
These masses are dyadic, positive, and sum to \(1\). Also \(m=\tau=N<2n\), so the construction has polynomial size.
Suppose \(I\) has a stable partition \(\Pi\) of cost at most \(k\). By the solvability promise, it has no singleton cycles.
Extend \(\Pi\) by adding a transposition for every designated dummy pair. Original successor and predecessor ranks are unchanged. Dummy types have their first choices as predecessors and therefore cannot participate in blocking pairs. Thus the extended partition is stable.
Each dummy contributes \(1\) to the finite cost, so the extended cost is at most \(k+d\). Lemma 2 gives a stable mass assignment of cost at most
\(\displaystyle \frac{k+d}{N}=K.\)
Suppose the constructed mass instance has a stable assignment \(q\) with \(C(q)\leq K\). Convert it to \(y\) using Lemma 1.
Every designated dummy pair \(\{a,b\}\) must satisfy \(y_{a,b}=1/N\). Indeed, if \(y_{a,b}<1/N\), both row sums leave positive mass assigned elsewhere. Since \(a,b\) are mutual first choices, this gives \(D_{a,b}(y)>0\) and \(D_{b,a}(y)>0\), contradicting stability.
Thus every dummy pair is an isolated component of the positive support. Apply the construction in Lemma 2 to the full instance. It preserves these pairs and produces a stable partition \(\Pi'\) with
\(\displaystyle c^*(\Pi')\leq NC(q)\leq k+d.\)
Remove the dummy transpositions. The remaining permutation \(\Pi_I\) is a stable partition of \(I\): comparisons between original types, including comparisons with self, have the same order before and after padding.
Since \(I\) is solvable, \(\Pi_I\) has no singleton cycles. All ranks appearing in its cost are therefore unchanged by padding. The dummy transpositions contribute exactly \(d\), yielding
\(\displaystyle c_I(\Pi_I)=c^*(\Pi')-d\leq k.\)
This proves the reverse implication and establishes \(\mathrm{NP}\)-hardness.
It remains to justify polynomial certificates despite allowing real masses in assignments.
Suppose a yes-instance has a stable symmetric allocation \(y\), and let \(S\) be its positive support, represented by unordered pairs including loops.
Consider the polytope \(P_S\) of all nonnegative symmetric allocations with the required row sums and zero coordinates outside \(S\). It is nonempty and compact: every coordinate lies between \(0\) and \(1\). Every point in \(P_S\) is stable by support preservation.
A linear function on a nonempty compact polytope has an extreme-point minimizer. Choose such a minimizer \(y^*\) of \(F\) on \(P_S\). Then
\(\displaystyle F(y^*)\leq F(y)\leq K.\)
The row-sum matrix has column \(e_i+e_j\) for an off-diagonal coordinate and column \(e_i\) for a loop. Its positive columns at \(y^*\) are linearly independent. Otherwise a nonzero dependence would permit sufficiently small perturbations in both directions, preserving the row sums and nonnegativity, contradicting extremality.
Consequently \(y^*\) has at most \(m\) positive coordinates. Let their number be \(p\). Select \(p\) rows making the corresponding square matrix \(B\) nonsingular.
Let \(D\) be a common denominator of the input masses, chosen as the product of their encoded denominators. Its bit length is \(O(L)\), and the selected right-hand side \(b=D\mu\) is integral with entries at most \(D\). Cramer’s rule gives each positive coordinate as
\(\displaystyle y^*_e=\frac{\det(B_e)}{D\det(B)},\)
where \(B_e\) replaces one column of \(B\) by \(b\). Hadamard’s determinant bound yields
\(\displaystyle |\det(B)|\leq p^{p/2},\qquad |\det(B_e)|\leq Dp^{p/2}.\)
Each coordinate therefore has bit length \(O(L+m\log(m+1))\).
The positive coordinates of \(y^*\) form a polynomial-size rational certificate. Symmetry, row sums, all stability disjunctions, and the cost bound can be checked using exact rational arithmetic in polynomial time. Lemma 1 converts any accepted certificate into a valid original assignment.
Thus the problem belongs to \(\mathrm{NP}\). Together with the reduction, this proves the claimed \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. The argument establishes \(\mathrm{NP}\)-completeness for the exact mass formulation, including the restriction to equal dyadic masses. I found no major or minor mathematical issues.
Lemma 1 is correct.
The three marginal constraints give the stated row and column sums of \(x\). Edge consistency identifies the predecessor marginal at type \(i\) with \(x_{k,i}\). Thus symmetrizing \(x\) produces a nonnegative symmetric matrix with the required row sums.
The critical stability comparison is valid: if a positive triple has a successor worse than \(h\), the ranking constraint forces its predecessor also to be worse than \(h\). Hence
\[
0\leq U_{i,h}\leq B_{i,h}.
\]
Together with the displayed expression for \(D_{i,h}(y)\), this establishes the claimed equivalence of zero conditions. Nonnegativity is essential here and is present.
The cost identity accounts correctly for both successor and predecessor contributions.
In the converse construction, concentrating \(q\) on triples with equal successor and predecessor types satisfies all three marginals. Edge consistency follows from symmetry, and the ranking constraint holds with equality. Stability and cost are preserved exactly.
The self conditions are automatic because self has the largest rank.
Support preservation is also correct. A zero sum of nonnegative worse-partner coordinates forces each coordinate in that sum to vanish. Restricting support therefore preserves every stability disjunction.
Lemma 2 is correct.
Strict rankings ensure that every vertex has a unique worst positive partner.
For a positive off-diagonal edge, failure to be worst at either endpoint would yield positive worse-partner mass at both endpoints, contradicting stability. A positive loop is worst at its vertex because self is last. Consequently, the map assigning each vertex its worst edge covers all edges, justifying the componentwise bound
\[
|E|\leq |V|.
\]
The degree-one argument uses equal normalized row sums correctly. Its unique incident off-diagonal edge must have weight \(1\), exhausting the other endpoint’s row sum and forcing an isolated pair.
Every remaining component has minimum degree at least two. Counting loops twice in graph degree gives the stated degree-sum equality, while counting their variables once in row equations is consistent. The inequalities force every degree to equal two. In this graph, which has no parallel off-diagonal edges, the resulting connected components are precisely single loops or simple cycles.
The weight conclusions follow correctly from the row equations: a loop has weight \(1\); odd-cycle weights are all \(1/2\); even-cycle weights alternate.
The convex-combination assertion is correct for alternating cycle weights. Both alternating matching replacements retain the full row sums and introduce no new support coordinates.
Support preservation applies to the entire allocation, so it also protects stability against types outside the replaced component. Linearity of cost justifies choosing a replacement with no greater cost. Repeating this componentwise preserves the stated inequality.
Each vertex designates exactly one better neighbor. An edge designated by both endpoints would violate stability, since each endpoint retains positive mass on its worse neighbor.
The counting argument therefore gives exactly one designation per edge. Each vertex then has one outgoing and one incoming edge, so the orientations form the asserted directed cycle.
The resulting permutation satisfies the successor-predecessor ranking condition. In every component, its predecessor is exactly the worst positive partner. The displayed equivalence between positive \(D_{i,h}\) and preference over the predecessor is therefore valid, including for loops and transpositions. Stability of the allocation implies stability of the permutation.
The cost equality uses the correct weights for every component.
The converse construction from a permutation satisfies edge consistency as well as the marginals: a successor edge corresponds to the same predecessor edge at its other endpoint. Its stability and cost claims follow directly from the stated partition conditions.
The cited results are accurately stated and applicable. The source defines instances using an even number of agents, complete strict preferences, and self last for stable partitions. Its Theorem 4.16 supplies the claimed hardness under the solvability promise, and Theorem 2.10 excludes all odd cycles in that setting. Its Definition 2.13 uses the same averaging factor as \(c^*\), while omitting self ranks. Thus the absence of singleton cycles makes the two costs coincide. [Glitzner–Manlove, Definitions 2.1 and 2.13, Theorems 2.10 and 4.16](https://arxiv.org/html/2406.00437v4).
There is no unverified transfer from the different Dean–Munshi allocation model.
Both directions of the reduction are correct.
The smallest power of two \(N\geq n\) satisfies \(N<2n\), including when \(n\) already is a power of two. Both numbers are even, so the dummy types can be paired. The masses satisfy positivity, normalization, and dyadic encoding requirements. Preference lists and the threshold have polynomial encoding size.
In the forward direction, original assigned partners are never self, so their numerical ranks remain unchanged. Dummy predecessors are first choices, preventing any blocking pair involving a dummy. Each dummy contributes exactly \(1\), making the total added finite cost \(d\). Lemma 2 supplies the required mass assignment.
In the reverse direction, symmetry and equal row sums justify the forced dummy-pair allocation. If its weight were below \(1/N\), both endpoints would have positive mass elsewhere and would block as mutual first choices.
The rounding construction preserves these isolated pairs. Removing their transpositions leaves a permutation of the original agents. Preference comparisons among original types, including self comparisons, retain their order, so stability survives restriction.
The solvability promise then excludes singleton cycles in the restricted partition. This exclusion is necessary for the numerical cost comparison and is explicitly justified. Every remaining assigned partner has an unchanged original rank, so subtracting precisely \(d\) yields the required source-instance bound.
The case \(d=0\) is covered without modification.
The rational-certificate argument is correct.
The fixed-support polytope is nonempty, closed, and bounded. Support preservation guarantees that every point remains stable. A linear objective therefore has an extreme-point minimizer with cost at most the given feasible allocation’s cost.
The positive-column independence argument is valid: a dependence supported on strictly positive coordinates permits sufficiently small perturbations in both directions, contradicting extremality. Consequently, there are at most \(m\) positive unordered coordinates, and a nonsingular square row submatrix can be selected.
The common denominator has polynomial bit length under the stated input encoding. The scaled right-hand side is integral, with entries at most \(D\).
Cramer’s rule is applied with the correct denominator. The Hadamard bounds are also valid: each column of \(B\) has norm at most \(\sqrt p\), and the replacement column has norm at most \(D\sqrt p\). These bounds give the claimed polynomial coordinate bit lengths.
Encoding coordinate indices and their rational values yields a polynomial-size certificate. All feasibility constraints, stability disjunctions, and the cost inequality admit exact polynomial-time verification. Lemma 1 then guarantees a valid assignment in the original formulation.
The proof establishes the claimed complexity classification. Its essential bridge between arbitrary real equal-mass assignments and finite stable partitions is justified, and the reduction respects the exact rank-cost objective.
No additional clarification or repair is needed for mathematical verification.
⟨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.