Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 12 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an instance of \gGASP\ whose underlying graph is a path, a star, or has connected components whose size is bounded by $3$, it is {\em NP}-complete to determine whether it has a core stable feasible assignment.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a path \(H\) of \(\tau\) cohort types, activities \(A\), rational type masses \(\mu_t\) summing to \(1\), and rational piecewise-linear utilities \(u_t(a,s)\) over activities and group mass \(s\), decide whether there is a core-stable assignment. Represent the assignment by masses \(x_{t,a}\geq 0\) with \(\sum_a x_{t,a}=\mu_t\); require each non-void activity’s users to occupy one connected interval of types. An assignment must be individually rational, and no activity \(a\) may admit a blocking coalition that selects mass from a connected interval, includes all current users of \(a\), and has every selected agent strictly prefer \(a\) at the coalition’s total mass to their current alternative.
The society is given by its support: an ordered list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Its graph is the path in this order. There are \(m\) non-void activities \(A^*\) and a void activity \(\varnothing\).
Each type has a divisible, atomless population and utilities \(u_t(a,s)\) for \(a\in A^*\), \(s\in[0,1]\), given explicitly as continuous piecewise-linear functions with binary-rational breakpoints and coefficients; utilities may have either sign. Void utility is always zero. Preferences compare utilities, with ties allowed. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
An assignment consists of real masses \(x_{t,b}\geq0\), for \(b\in A^*\cup\{\varnothing\}\), satisfying \(\sum_bx_{t,b}=\mu_t\). Put \(s_a=\sum_tx_{t,a}\). For each used non-void activity, \(\{t:x_{t,a}>0\}\) must be an interval; each activity has only one group. Void users have no connectivity restriction.
Write \(v_{t,a}=u_t(a,s_a)\) and \(v_{t,\varnothing}=0\). Individual rationality requires \(v_{t,a}\geq0\) whenever \(x_{t,a}>0\).
A blocking coalition for \(a\in A^*\) selects real masses \(0\leq y_{t,b}\leq x_{t,b}\), with \(y_{t,a}=x_{t,a}\) for every type, total mass \(q=\sum_{t,b}y_{t,b}>0\), and interval support \(\{t:\sum_by_{t,b}>0\}\). It blocks exactly when \(u_t(a,q)>v_{t,b}\) for every \((t,b)\) with \(y_{t,b}>0\). No connectivity condition is imposed on the groups left behind. An assignment is core stable if it is individually rational and admits no such coalition.
Is deciding whether a core-stable assignment exists in this model solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite indivisible agents, core-stable assignment existence is NP-complete on paths; the discrete path problem is also in XP parameterized by the number of non-void activities ([source](https://arxiv.org/pdf/1712.02712)). No result settling this exact continuous model was located.
The problem is \(\mathrm{NP}\)-hard, even when all type masses are equal dyadic rationals and every utility function has at most ten affine pieces.
The key is to construct utility peaks that force every core-stable assignment to allocate each type wholly to one activity or to void. This makes a discrete hardness reduction valid despite the availability of fractional coalitions.
Consider an auxiliary finite instance on a path with \(N\geq4\) vertices. Each vertex represents one indivisible player. Void utility is zero. For each player \(t\), activity \(a\), and group size \(k\in\{1,2,3\}\), an approved alternative has positive integer utility \(R_t(a,k)\). Every unlisted alternative has utility \(-1\).
Assignments and blocking coalitions satisfy exactly the connectivity and incumbent-inclusion rules in the question, interpreted for indivisible players.
Define the approval set
\(P(a,k)=\{t:R_t(a,k)>0\}.\)
Assume the following property:
Component bound. Every connected component of \(P(a,k)\) has at most \(k\) vertices.
Replace every player by an atomless type of mass \(1/N\). Let \(K_{t,a}\) be the set of approved sizes for player \(t\) and activity \(a\), and define
\(u_t(a,s)=\max\bigl(\{-1\}\cup\{R_t(a,k)-4N(R_t(a,k)+1)|s-k/N|:k\in K_{t,a}\}\bigr).\)
Each approved alternative produces a triangular peak of height \(R_t(a,k)\) at \(s=k/N\). Its nonconstant part lies between \((k-1/4)/N\) and \((k+1/4)/N\). These intervals are disjoint for distinct integer sizes.
Lemma. Under the component bound:
Let \(a\) be used in an individually rational continuous assignment, and write \(z=Ns_a\).
Every participating type has nonnegative utility at \(s_a\). Consequently, there is a unique integer \(k\in\{1,2,3\}\) such that
\(k-\tfrac14<z<k+\tfrac14,\)
and every participating type belongs to \(P(a,k)\).
The support of \(a\) is an interval, so it lies within one component of \(P(a,k)\). By the component bound, it contains at most \(k\) types. Since each type has mass \(1/N\), this also gives \(z\leq k\).
It cannot contain fewer than \(k\) types: that would imply \(z\leq k-1\), contradicting \(z>k-1/4\). Thus its support contains exactly \(k\) types and is an entire component of \(P(a,k)\).
For every participating type \(t\), the other \(k-1\) types contribute at most \((k-1)/N\). Hence
\(x_{t,a}\geq s_a-\frac{k-1}{N}>\frac{3}{4N}.\)
Two distinct used activities therefore cannot share a type: their combined allocation from that type would exceed \(1/N\). Each participating type allocates mass only to its unique non-void activity and to void.
Suppose now that \(s_a<k/N\). Form a coalition consisting of the full populations of its \(k\) supporting types. This coalition includes every incumbent and has interval support and total mass \(k/N\).
For an incumbent of type \(t\), utility increases strictly because, on the relevant interval below the peak,
\(u_t(a,s_a)=R_t(a,k)-4N(R_t(a,k)+1)(k/N-s_a)<R_t(a,k).\)
Every selected void user also improves strictly, since \(R_t(a,k)>0\). The coalition blocks.
Thus core stability requires \(s_a=k/N\). Its \(k\) supporting types must each contribute their full mass \(1/N\). This proves the first assertion.
A continuous core-stable assignment is whole-type by the first assertion. Interpret it as a finite assignment. Utilities agree at integer group sizes. Any finite blocking coalition would become a continuous blocking coalition by selecting the full masses of its members. Therefore the finite assignment is core stable.
Conversely, replace a finite core-stable assignment by its whole-type continuous assignment. Suppose a continuous coalition blocks activity \(a\), has total mass \(q\), and has interval support \(S\).
Current utilities are nonnegative. Every selected type must therefore have \(u_t(a,q)>0\). For a unique \(k\in\{1,2,3\}\), we have
\(k-\tfrac14<Nq<k+\tfrac14,\qquad S\subseteq P(a,k).\)
The component bound gives \(|S|\leq k\). The mass bound \(q\leq |S|/N\), together with \(Nq>k-1/4\), gives \(|S|\geq k\). Thus \(|S|=k\).
For every \(t\in S\),
\(R_t(a,k)\geq u_t(a,q)>v_t,\)
where \(v_t\) is that type’s current utility. Moreover, the incumbent-inclusion requirement ensures that \(S\) contains every finite incumbent of \(a\).
Consequently, the \(k\) finite players in \(S\) form a blocking coalition, contradicting finite core stability. The continuous assignment is therefore core stable. This proves the lemma.
We reduce from Rainbow Matching on properly edge-colored paths: given a path \(G\), a proper edge coloring \(\phi:E(G)\to C\), and an integer \(h\), decide whether there is a matching of at least \(h\) edges with distinct colors. This problem is \(\mathrm{NP}\)-complete by Corollary 2 of [Le and Pfender, *Complexity Results for Rainbow Matchings*](https://arxiv.org/pdf/1312.7253).
Write \(n=|V(G)|\) and \(r=|C|\), taking \(C\) to contain exactly the used colors. We restrict to \(1\leq h\leq r\); the excluded cases are trivial.
Construct an auxiliary finite path from the following blocks:
Place a dummy player between every two consecutive blocks. Dummies approve no non-void alternative.
There are three activities per color: \(c,a_c,b_c\).
A graph vertex approves \((c,3)\), with utility \(10\), precisely when it is incident to an edge of color \(c\). An edge player approves only its own color at size \(3\), also with utility \(10\). Every collector approves every color activity at size \(1\), with utility \(10\).
The three-player preferences below use the path gadget from the finite reduction in [Igarashi et al., Appendix, proof of Theorem 13](https://arxiv.org/pdf/1712.02712), with explicit numerical utilities:
| Player | Approved alternatives and utilities |
|---|---|
| \(c_1\) | \(R(b_c,2)=5,\ R(a_c,1)=4,\ R(c,3)=3,\ R(c,2)=2,\ R(c,1)=1\) |
| \(c_2\) | \(R(c,3)=5,\ R(c,2)=4,\ R(a_c,2)=3,\ R(b_c,2)=2,\ R(b_c,1)=1\) |
| \(c_3\) | \(R(c,3)=3,\ R(a_c,2)=2,\ R(a_c,1)=1\) |
All unlisted alternatives have utility \(-1\). Each activity may have only one group.
Claim. In every finite core-stable assignment, each color activity \(c\) is used outside its three-player gadget.
Suppose otherwise. Separating dummies prevent individually rational groups or blocking coalitions from crossing between blocks. The gadget’s possible nonempty individually rational groups are therefore:
| Activity | Possible groups |
|---|---|
| \(a_c\) | \(\{c_1\},\ \{c_3\},\ \{c_2,c_3\}\) |
| \(b_c\) | \(\{c_2\},\ \{c_1,c_2\}\) |
| \(c\) | \(\{c_1\},\ \{c_1,c_2\},\ \{c_1,c_2,c_3\}\) |
We check every case.
If its group is \(\{c_1\}\) or \(\{c_1,c_2\}\), the entire gadget blocks by expanding \(c\) to size \(3\):
This coalition includes all color incumbents.
If the color group already contains all three players, \(a_c\) is unused. Player \(c_1\) blocks alone with \(a_c\), improving from \(3\) to \(4\).
If \(a_c\) has group \(\{c_2,c_3\}\), player \(c_1\) must be void. Then \(\{c_1,c_2\}\) blocks with \(c\): their utilities increase from \(0,3\) to \(2,4\).
If \(b_c\) has group \(\{c_1,c_2\}\), player \(c_3\) is either void or alone at \(a_c\). Then \(\{c_2,c_3\}\) blocks with \(a_c\), improving their utilities from \(2\) and at most \(1\) to \(3,2\). This coalition includes any incumbent of \(a_c\).
The remaining possibilities use only singleton groups. If \(c_1\) is alone at \(a_c\), then \(\{c_1,c_2\}\) blocks with \(b_c\): player \(c_1\) improves from \(4\) to \(5\), and player \(c_2\) improves from at most \(1\) to \(2\). Any incumbent of \(b_c\) is included.
Otherwise \(c_1\) is void and blocks alone with the unused activity \(c\).
Every possibility admits a blocking coalition. This proves the claim.
By the preceding claim, all \(r\) color activities must be used outside their gadgets.
Outside the gadgets, a color activity can be assigned only:
To justify the second statement, proper edge coloring ensures that the graph players approving \((c,3)\) form disjoint three-player components, one for each edge of color \(c\). An individually rational connected group of size \(3\) must be exactly one such component.
At most \(r-h\) colors can be assigned to collectors. Hence at least \(h\) colors are assigned to graph triples.
These triples are disjoint because players are indivisible. Their corresponding edges therefore form a matching. Their colors are distinct because each color activity has only one group. Thus they give a rainbow matching of size at least \(h\).
Take a rainbow matching of exactly \(h\) edges, discarding excess edges if necessary.
Assign each selected edge and its two endpoints to its color activity. Assign the remaining \(r-h\) colors bijectively to the collectors. In every gadget, assign \(c_2,c_3\) to \(a_c\), and assign \(c_1\) to void. Assign all remaining players to void.
This assignment is feasible and individually rational. We verify all activity targets:
Thus the finite assignment is core stable.
We have proved that the auxiliary finite instance admits a core-stable assignment exactly when the source instance has a rainbow matching of size at least \(h\).
For every activity and approved size, approval components have the required size bound:
All other approval sets are empty. Thus every component has at most its specified group size.
Append additional dummy players so that the total number \(N\) is a power of two and at least \(4\). Padding creates no approved alternative and changes neither the finite equivalence nor the component bound.
Now apply the transfer lemma. Give every type mass \(\mu_t=1/N\), and use the triangular utility functions from Section 1.
These masses are positive dyadic rationals summing to one. Every type, including every dummy type, belongs to the support, so the support size is exactly \(\tau=N\). The social graph is the path in the constructed order.
The transfer lemma proves that this continuous instance admits a core-stable assignment exactly when the source rainbow-matching instance is a yes-instance.
The construction has
\(m=3r,\qquad \tau=N=O(n+r).\)
Each utility function contains at most three triangular peaks. Its explicit piecewise-linear representation has at most ten affine pieces. Its breakpoints are among
\(0,\ 1,\ \frac{k-1/4}{N},\ \frac{k}{N},\ \frac{k+1/4}{N},\qquad k\in\{1,2,3\}.\)
All breakpoints are dyadic. The slopes are \(0\) or \(\pm4N(R+1)\), with \(1\leq R\leq10\), and the intercepts are integers. Consequently, every coefficient and breakpoint requires \(O(\log\tau)\) bits.
The total output length is \(L=O(m\tau\log\tau)\), and the explicit utility tables can be generated in \(O(m\tau\log\tau)\) bit operations. Hence this is a polynomial-time many-one reduction.
Therefore core-stable assignment existence in the stated continuous model is \(\mathrm{NP}\)-hard. A decision algorithm polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The reduction establishes \(\mathrm{NP}\)-hardness for the exact continuous model in USER_TASK. I found no major or minor issues requiring repair.
1. Source problem and cited results
Corollary 2 of Le and Pfender states that deciding whether a properly edge-colored path has a rainbow matching of at least a specified size is \(\mathrm{NP}\)-complete. This is exactly the source problem used by the prover. Restricting to \(1\leq h\leq r\), with \(r\) counting used colors, excludes only trivial threshold cases. [Le and Pfender, Corollary 2](https://arxiv.org/pdf/1312.7253).
The numerical gadget preferences reproduce the preference orders in the cited appendix. However, the prover also supplies its own complete blocking-coalition analysis, so its correctness does not depend on importing an unstated gadget lemma. [Igarashi et al., appendix proof of Theorem 13](https://arxiv.org/pdf/1712.02712).
2. Utility construction
The triangular utility formula is continuous and piecewise linear. A peak reaches the baseline value \(-1\) at distance \(1/(4N)\) from its center. Hence the regions where distinct peaks exceed the baseline are disjoint.
Nonnegative utility requires the strictly narrower condition
\[
\left|s-\frac{k}{N}\right|
\leq \frac{R_t(a,k)}{4N(R_t(a,k)+1)}
<\frac{1}{4N}.
\]
Thus the prover correctly uses strict quarter-width inequalities even though individual rationality permits utility zero.
At an approved integer size, the utility equals the specified positive integer. At an unapproved integer size, it equals \(-1\). Consequently, the continuous construction preserves all finite utilities relevant to assignments and finite coalitions.
3. Whole-type assertion
Every inference in the first part of the transfer lemma is valid:
The last observation correctly leaves each participating type split only between its unique non-void activity and void.
If that activity has total mass below \(k/N\), selecting the full populations of its supporting types is an admissible coalition. It includes every incumbent, retains interval support, and has positive total mass. Incumbents strictly improve to their peak utilities; any selected void users strictly improve from zero. Therefore stability forces total mass \(k/N\), which forces every supporting type to contribute its entire population.
No integrality assumption has been imposed on the continuous assignment: whole-type allocation is derived from stability.
4. Equivalence under fractional coalitions
The forward implication is correct. Whole-type assignments preserve finite utilities, feasibility, and individual rationality. Any finite blocking coalition translates directly into an admissible continuous blocking coalition.
The reverse implication also addresses arbitrary fractional coalitions. In the continuous replacement of an individually rational finite assignment, every selected type has one current utility, which is nonnegative. Strict improvement therefore requires positive target utility.
The common target size places the coalition support inside one approval component for a unique \(k\). The component bound gives \(|S|\leq k\), while the coalition mass bound and the quarter-width lower bound give \(|S|\geq k\). Thus \(|S|=k\).
For each selected type, its peak utility is at least its utility at the fractional coalition size and strictly exceeds its current utility. Incumbent inclusion ensures that all finite incumbents belong to \(S\). Therefore \(S\) is a finite blocking coalition.
This verifies the crucial point: partial participation creates no additional blocking coalition against the whole-type replacement of a finite stable assignment.
5. Gadget case analysis
The listed individually rational groups are exhaustive. Dummies cannot participate in an individually rational group or a blocking coalition because they receive utility \(-1\) at every non-void alternative and zero currently.
All gadget cases check out:
The cases cover all possibilities, and every exhibited coalition satisfies incumbent inclusion and interval support.
6. Finite reduction
Proper edge coloring gives the claimed disjoint three-player approval components for each color in the subdivided graph. Consecutive original edges cannot share a color; the intervening edge player therefore separates the components of distinct edges of the same color.
The gadget claim forces every color activity outside its gadget. Outside, its only individually rational possibilities are a collector singleton or one of the graph triples. At most \(r-h\) colors use collectors, so at least \(h\) use graph triples. Indivisibility makes those triples disjoint, yielding a matching; the single-group rule makes their colors distinct.
The converse assignment is feasible and individually rational. Its stability verification covers every activity:
Thus both finite reduction directions are established.
7. Component bounds, padding, and encoding
Every approval component listed in Section 5 has size at most its approved group size. Dummies separate blocks, and appended padding dummies introduce no approvals or blocking possibilities.
Padding to a power of two preserves polynomial size and makes all masses and breakpoints dyadic. Every type has positive mass, including dummies, and the masses sum to one.
With at most three separated peaks, there are at most six sloping pieces and four baseline pieces, giving the asserted maximum of ten affine pieces. The breakpoint, slope, and intercept claims are correct, including the stated coefficient bit lengths.
The bounds \(m=3r\), \(\tau=O(n+r)\), and \(L=O(m\tau\log\tau)\) verify a polynomial-size, polynomial-time reduction.
Actionable feedback: No mathematical clarification or repair is needed. The established conclusion is \(\mathrm{NP}\)-hardness; the output does not claim or require membership of the continuous problem in \(\mathrm{NP}\).
⟨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.