Answer: \(\mathrm{NP}\text{-complete}\)
Proposition 5 — class: hardness
Given \(m\) alternatives, rational masses \(\mu_t\) for \(\tau\) complete preference types, and rational piecewise-linear utilities \(u_t(S,q)\) that increase with community share \(q\), decide whether there is an assignment \(x_{t,S}\geq 0\), with \(\sum_S x_{t,S}=\mu_t\) and \(q_S=\sum_t x_{t,S}\), such that no positive-mass coalition can profit by moving together to any alternative.
Let \(M\) be a set of \(m\geq2\) alternatives. A society is given by its support: a list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has utilities \(u_t(S,q)\in\mathbb R\), defined for every \(S\in M\) and \(q\in[0,1]\), continuous and strictly increasing in \(q\), and piecewise linear with explicitly listed binary-rational breakpoints and values. Utilities induce complete preferences; equality means indifference, with no tie-breaking. Let \(L\) be the total input bit length.
An assignment consists of real masses \(x_{t,S}\geq0\) satisfying \(\sum_{S\in M}x_{t,S}=\mu_t\); write \(q_S=\sum_t x_{t,S}\). Each alternative has one community, possibly empty; there is no outside option, and type masses are divisible.
A blocking move to \(R\in M\) selects real masses \(0\leq y_{t,S}\leq x_{t,S}\) for \(S\neq R\), with \(\delta=\sum_t\sum_{S\neq R}y_{t,S}>0\), such that \(u_t(R,q_R+\delta)>u_t(S,q_S)\) whenever \(y_{t,S}>0\). Movers join the existing community at \(R\); everyone else stays, and incumbent consent is unnecessary. An assignment is stable if it has no blocking move.
Is deciding whether a stable assignment exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite agents with strict preferences increasing in community size, stable-assignment existence is NP-complete when the number of alternatives is unrestricted; checking a given assignment is polynomial-time, and two alternatives always admit a polynomial-time computable stable assignment. [Source](https://pure.rug.nl/ws/files/202200570/2021_Book_AlgorithmicDecisionTheory.pdf)
No result settling the exact divisible-mass, piecewise-linear-utility problem above was located in the literature search.
Deciding whether a stable assignment exists is \(\mathrm{NP}\)-complete.
The decisive observation is that strict increase in community size forces every stable assignment to place each type’s entire mass at one alternative. Fractional blocking moves from such assignments can then be enlarged to moves of entire types.
Call an assignment pure if, for every type \(t\), there is an alternative \(a(t)\) with \(x_{t,a(t)}=\mu_t\).
Lemma 1. Every stable assignment is pure.
Proof. Suppose type \(t\) has positive mass at two distinct alternatives \(S\) and \(R\). Interchanging their names if necessary, assume
\(u_t(R,q_R)\geq u_t(S,q_S).\)
Choose \(0<\varepsilon\leq x_{t,S}\), and move mass \(\varepsilon\) of this type from \(S\) to \(R\). This is feasible, and strict increase gives
\(u_t(R,q_R+\varepsilon)>u_t(R,q_R)\geq u_t(S,q_S).\)
Thus the move blocks the assignment. Consequently, a stable assignment cannot split any type. \(\square\)
This argument also handles indifference: equality between the two current utilities still produces a strictly improving move.
Fix a pure assignment \(a\), and write
\(q_S=\sum_{t:a(t)=S}\mu_t,\qquad v_t=u_t(a(t),q_{a(t)}).\)
Lemma 2. There is a blocking move to \(R\) if and only if there is a nonempty set \(C\subseteq\{t:a(t)\neq R\}\) such that
\(u_t\left(R,q_R+\sum_{j\in C}\mu_j\right)>v_t\qquad\text{for every }t\in C.\)
Proof. Such a set directly supplies a blocking move: move every member type’s entire mass to \(R\).
Conversely, suppose a fractional blocking move to \(R\) has total mass \(\delta>0\). Let \(C\) consist of the types contributing positive mass. Because the assignment is pure, each contributing type moves from its unique assigned alternative. Put
\(D=\sum_{t\in C}\mu_t.\)
Then \(D\geq\delta\) and \(q_R+D\leq1\). For every \(t\in C\), monotonicity and the blocking condition imply
\(u_t(R,q_R+D)\geq u_t(R,q_R+\delta)>v_t.\)
Hence moving the entire mass of every type in \(C\) also blocks. \(\square\)
A certificate specifies one alternative \(a(t)\) for each type. Its length is \(O(\tau\log m)\). Lemma 1 ensures that every yes-instance has such a certificate.
To verify it, compute the community masses and current utilities. For each destination \(R\), apply the following elimination procedure:
\(u_t(R,q_R+W(C))\leq v_t.\)
If the final set is nonempty, every remaining type strictly benefits when all remaining types move. Lemma 2 therefore gives a blocking move.
If the final set is empty, no blocking set exists. Indeed, suppose \(K\) were a blocking set. Initially \(K\subseteq C\). Whenever \(K\subseteq C\), every \(t\in K\) satisfies
\(u_t(R,q_R+W(C))\geq u_t(R,q_R+W(K))>v_t.\)
Thus no member of \(K\) is removed, so \(K\) survives every iteration. This contradicts an empty final set.
There are at most \(\tau\) removal rounds per destination, giving \(O(m\tau^2)\) utility evaluations. Community masses, evaluation points, and evaluated utilities are rational numbers of polynomial bit length: sums and evaluations of explicitly represented rational piecewise-linear functions require only polynomially many rational arithmetic operations. All comparisons, including equality, are exact.
Therefore verification takes polynomial time in \(m,\tau,L\), and the existence problem belongs to \(\mathrm{NP}\).
We use the finite-agent hardness result stated in the question: stable-assignment existence for unrestricted alternatives and strict preferences increasing in community size is \(\mathrm{NP}\)-complete. This is Proposition 5 of Abramowitz, Elkind, Grossi, Shapiro, and Talmon, *Democratic Forking: Choosing Sides with Social Choice*. [Source, printed p. 354](https://pure.rug.nl/ws/files/202200570/2021_Book_AlgorithmicDecisionTheory.pdf#page=364).
The source permits deviations involving several destinations. Under increasing preferences, existence of such a deviation is equivalent to existence of a deviation to one destination: select all movers entering any one destination, and keep everyone else fixed. Their destination community is at least as large as in the original deviation, since its outgoing movers now stay. Thus every selected mover still strictly improves. This also matches the observation used in Proposition 4 of the source.
Let a source instance have \(n\) agents, alternatives \(M_0\), and \(m_0=|M_0|\). Agent \(i\) has an explicitly listed strict order over outcomes \((S,k)\), where \(S\in M_0\) and \(1\leq k\leq n\). Choose integer ranks
\(r_i(S,k)\in\{1,\ldots,m_0n\},\)
with larger ranks representing preferred outcomes. Increasing preferences imply
\(r_i(S,k+1)>r_i(S,k).\)
The construction below uses only dyadic rational masses and breakpoints, so it also satisfies the stricter interpretation of “binary-rational.”
Let \(N\) be the smallest power of two strictly greater than \(n\). Then \(n<N\leq2n\).
Create:
The masses are positive and sum to one.
For each original type \(i\) and alternative \(S\in M_0\), define its utility by linear interpolation through the points
\(u_i(S,0)=r_i(S,1)-1,\)
\(u_i(S,k/N)=r_i(S,k)\qquad(1\leq k\leq n),\)
\(u_i(S,1)=r_i(S,n)+1.\)
Every successive listed value strictly increases. Thus each function is continuous, piecewise linear, and strictly increasing throughout its domain.
For original types at the additional alternative, set
\(u_i(D,q)=-2+q.\)
For the additional type, set
\(u_d(D,q)=2+q,\qquad u_d(S,q)=q\quad(S\in M_0).\)
All these functions also satisfy the required continuity and strict increase.
If distinct utility functions are required for distinct listed types, add the constant \(i(m_0n+5)\) to every utility of original type \(i\). This makes the functions distinct without changing any comparison for that type or any argument below.
There are \(O(m_0n^2)\) listed interpolation points, each with polynomial bit length. The construction therefore has polynomial size and is computable in polynomial time.
In every stable assignment, type \(d\) must be entirely at \(D\). Otherwise, some positive mass of this type receives utility at most \(1\) at an original alternative and can strictly improve by moving to \(D\), where utility is at least \(2\).
Every original type must be entirely outside \(D\). Before any optional additive shift, its utility at \(D\) is at most \(-1\), whereas its utility at every original alternative is at least \(0\). Any positive mass assigned to \(D\) can therefore strictly improve by leaving it. Additive shifts preserve these inequalities.
Together with Lemma 1, this shows that every stable assignment consists of the additional type at \(D\) and one original alternative for each original type.
Let \(a:\{1,\ldots,n\}\to M_0\) be a finite-agent assignment. Construct the corresponding pure mass assignment and place type \(d\) at \(D\).
If alternative \(S\) has \(k_S\) original agents, its mass is \(k_S/N\). An original type assigned there consequently receives utility \(r_i(S,k_S)\), up to its irrelevant additive constant.
Consider a nonempty coalition \(C\) of original agents outside destination \(R\in M_0\). Moving their entire corresponding types produces destination mass
\((k_R+|C|)/N.\)
Every participating type strictly improves exactly when
\(r_i(R,k_R+|C|)>r_i(a(i),k_{a(i)})\qquad(i\in C),\)
which is precisely the finite-agent blocking condition.
No original type can benefit by moving to \(D\), and type \(d\), already at \(D\), cannot benefit by moving to an original alternative. Therefore Lemma 2 shows that the constructed mass assignment is stable exactly when the finite-agent assignment is stable.
Conversely, every stable mass assignment has the forced form proved above and hence determines a finite-agent assignment. A finite blocking coalition would give a blocking move of entire types, so this finite assignment must be stable.
We have therefore proved the equivalence:
\(\text{The finite instance has a stable assignment}\iff\text{the constructed divisible-mass instance has a stable assignment}.\)
This establishes \(\mathrm{NP}\)-hardness.
The problem is \(\mathrm{NP}\)-complete, even with dyadic rational masses and breakpoints. In particular, it has no polynomial-time algorithm in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task: stable-assignment existence is \(\mathrm{NP}\)-complete for the specified divisible-mass model. I found no major or minor mathematical issues.
Lemma 1 is valid.
If a type has positive mass at two alternatives, their current utilities are comparable. The alternatives can therefore be named so that \(u_t(R,q_R)\geq u_t(S,q_S)\). Moving any positive \(\varepsilon\leq x_{t,S}\) to \(R\) strictly improves every participating unit of this type.
The move respects the utility domain: \(q_R+\varepsilon\leq q_R+x_{t,S}\leq1\), because the source and destination are distinct. Its total mass is positive, and all unselected masses remain fixed, as required.
The argument also covers equal current utilities. Consequently, each type occupies at most one alternative in a stable assignment. Its positive mass and assignment constraint then imply that its entire mass occupies that alternative.
Both directions of Lemma 2 are correct.
A nonempty qualifying set of types gives a feasible whole-type move with positive total mass because every type has positive mass.
Conversely, for a fractional blocking move from a pure assignment, every contributing type has a unique source outside \(R\). Its contributed mass is at most its full mass, so \(D\geq\delta\). Since all contributing types are outside \(R\), \(q_R+D\leq1\). Increasing the destination mass from \(q_R+\delta\) to \(q_R+D\) preserves every contributing type’s strict improvement.
The source utilities remain those of the original assignment, exactly as prescribed by the blocking definition. Enlarging the move therefore introduces no missing source-side condition.
The certificate is sufficient: Lemma 1 guarantees that every instance admitting a stable assignment admits one represented by an alternative choice for each type.
The elimination procedure is sound:
This reasoning permits unequal type masses and handles equality correctly: a type whose destination utility equals its current utility cannot participate at that tested mass.
Each removal round deletes at least one type. Including the terminal check changes only a constant in the stated \(O(m\tau^2)\) evaluation bound. Empty candidate sets cause no difficulty.
The arithmetic claim also holds for the operations actually used. Community masses and candidate masses are sums of input rationals. Evaluating a listed linear segment at such a point uses rational interpolation with polynomial bit length. Locating the segment and comparing utilities exactly both take polynomial time in the explicit input size. The argument establishes membership in \(\mathrm{NP}\).
The cited theorem matches the required source problem. The source defines strict total orders over alternative–community-size outcomes, with strict preference for larger communities at a fixed alternative. Its stability condition requires improvement by all agents who change alternatives, without incumbent consent. Proposition 5 establishes \(\mathrm{NP}\)-completeness for unrestricted alternatives; Proposition 4 explicitly reduces instability witnesses to a single destination. [Source, Sections 2–3 and Propositions 4–5](https://pure.rug.nl/ws/files/202200570/2021_Book_AlgorithmicDecisionTheory.pdf#page=364).
The prover’s explanation of the single-destination reduction is correct: retaining only movers entering one destination leaves that destination at least as large as in the original deviation. Every retained mover therefore still improves.
The explicit rank representation used in the construction preserves the source orders and their strict increase with community size. No incompatible source hypothesis is introduced.
The mass construction is valid. For positive \(n\), the smallest power of two strictly greater than \(n\) satisfies \(n<N\leq2n\), including when \(n\) itself is a power of two. All original masses and the additional mass are positive dyadic rationals, and their sum is one.
The interpolation points have strictly increasing coordinates:
\(0<1/N<\cdots<n/N<1\).
Their values strictly increase on every successive segment. Thus the constructed utilities are continuous and strictly increasing throughout \([0,1]\), including both endpoint segments.
All listed coordinates are dyadic and all listed values are integers. The additional utility functions also satisfy the input requirements. The stated number of interpolation points and their bit lengths are polynomial in the explicit source instance size.
The optional additive shifts preserve all comparisons within a type. They also suffice to distinguish original types if that is required. This optional step does not affect the reduction.
Both forced-location arguments are valid even before invoking purity.
Any positive additional-type mass outside \(D\) receives utility at most \(1\), while moving it to \(D\) yields utility at least \(2\). Such an assignment is blocked.
Any positive original-type mass at \(D\) receives utility at most \(-1\), while moving it to an original alternative yields utility at least \(0\). The destination remains in \([0,1]\), and any optional type-specific shift affects both sides equally.
Together with Lemma 1, these arguments establish precisely the claimed form of every stable constructed assignment.
The correspondence evaluates utilities only at listed interpolation points.
An occupied original alternative has community size \(k_S\geq1\), so its assigned types receive the specified rank value. For a nonempty moving coalition, \(1\leq k_R+|C|\leq n\), including when the destination was initially empty. Hence the destination utility is also exactly the specified rank value.
Whole-type moves consequently reproduce the finite-agent strict comparisons exactly. Original types cannot improve by entering \(D\), and the additional type cannot improve by leaving it. Lemma 2 excludes additional fractional blocking moves.
Both implications of the claimed existence equivalence follow. The reduction proves \(\mathrm{NP}\)-hardness, and the verification argument proves membership in \(\mathrm{NP}\). 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.