Answer: \(\mathrm{NP}\)-complete
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-complete to decide whether a-GASP admits a perfect assignment, even when all activities in A∗are simple and all agents have increasing preferences. sketch. We provide a reduction from EXACT COVER BY 3-SETS (X3C). Recall that an instance of X3C is a pair ⟨X, Y⟩, where X = {1, . . ., 3q} and Y = {Y1, . . . , Yp} is a collection of 3-element subsets of X; it is a “yes”-instance if X can be covered by exactly q sets from Y, and a “no”-instance otherwise. Given an instance ⟨X, Y⟩of X3C, we construct an instance of a-GASP as follows.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given simple activities \(A\), complete preference types \(T\) with rational masses \(\mu_t\ge0\) satisfying \(\sum_t\mu_t=1\), an allowed-pair relation \(E\subseteq T\times A\), and rational thresholds \(\ell_{t,a}\ge0\) for allowed pairs, decide whether there exist assignment masses \(x_{t,a}\ge0\) and activity masses \(z_a=\sum_t x_{t,a}\) such that \(\sum_a x_{t,a}=\mu_t\) for every type and \(x_{t,a}>0\Rightarrow ((t,a)\in E\land z_a\ge\ell_{t,a})\).
A society is given by its support: a list \(T\) of \(\tau\) complete preference 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.
There are \(m\) non-void activities \(A\), an explicitly listed relation \(E\subseteq T\times A\), and binary rational thresholds \(\ell_{t,a}\ge0\) for allowed pairs. At a positive group mass \(s\in(0,1]\), type \(t\) approves activity \(a\) exactly when \((t,a)\in E\) and \(s\ge\ell_{t,a}\). Each type is indifferent among approved alternatives, strictly prefers them to the void activity, and strictly prefers the void activity to all disapproved alternatives.
Activities are simple: each supports at most one group, and no two activities have identical approval profiles across all types and positive group masses. A type's mass may be split among activities.
A perfect individually rational assignment consists of real masses \(x_{t,a}\ge0\) satisfying \(\sum_{a\in A}x_{t,a}=\mu_t\) for every \(t\), with \(z_a=\sum_{t\in T}x_{t,a}\), and \(x_{t,a}>0\Rightarrow((t,a)\in E\land z_a\ge\ell_{t,a})\). Thus all mass must participate in non-void activities. Let \(L\) be the total binary input length.
Is deciding whether such a perfect individually rational assignment exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite indivisible agents, existence of a perfect individually rational assignment is \(\mathrm{NP}\)-complete even with simple activities and increasing approval preferences ([published result](https://www.lamsade.dauphine.fr/~lang/papers/DEKLSW18.pdf)). No result settling this exact distribution-over-types version was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when every allowed pair has the same positive threshold.
The reduction below handles both divisible masses and the requirement that the support list contain distinct preference types.
We use Exact Cover by 3-Sets: given a universe \(U\) with \(|U|=3q\), where \(q\ge 1\), and a family \(\mathcal S\) of three-element subsets, decide whether some subfamily partitions \(U\). This is the standard \(\mathrm{NP}\)-complete source problem also used in [Theorem 1 of the cited paper](https://www.lamsade.dauphine.fr/~lang/papers/DEKLSW18.pdf).
Delete duplicate sets; this does not change the existence of an exact cover. If the family is empty, output a fixed infeasible society consisting of one type of mass \(1\), one activity, and no allowed pairs. Henceforth assume the sets are distinct and the family is nonempty.
For \(u,v\in U\), define \(u\sim v\) when they belong to exactly the same sets of \(\mathcal S\). Let \(\mathcal C\) be the resulting equivalence classes.
Create one type \(t_C\) for each \(C\in\mathcal C\), with mass
\(\displaystyle \mu_{t_C}=\frac{|C|}{3q}.\)
These masses are positive and sum to \(1\).
Create one activity \(a_S\) for each \(S\in\mathcal S\). Define
\(\displaystyle (t_C,a_S)\in E \quad\Longleftrightarrow\quad C\subseteq S,\)
and give every allowed pair threshold
\(\displaystyle \ell_{t_C,a_S}=\frac1q.\)
Specify the complete preferences by placing approved alternatives above the void activity and disapproved alternatives below it, with indifference within each of those two classes.
By the definition of \(\sim\), every equivalence class \(C\) is either entirely contained in \(S\) or disjoint from \(S\). Consequently, every activity has exactly the following total mass of types that allow it:
\(\displaystyle \sum_{C:\,C\subseteq S}\mu_{t_C}=\frac{|S|}{3q}=\frac1q.\)
Distinct equivalence classes have different incidence patterns across \(\mathcal S\). At positive group mass \(1/q\), their approval patterns therefore differ. Thus the constructed types are distinct, and the support size is \(\tau=|\mathcal C|\le 3q\).
Distinct sets also yield distinct activity profiles. Indeed, for \(S\ne R\), choose an element \(u\) belonging to exactly one of them. Its equivalence class is contained in that set and disjoint from the other. At group mass \(1/q\), its type approves exactly one of \(a_S,a_R\). Hence no two activities have identical approval profiles. Each activity supports only the single group represented by its column of assignment masses.
The equivalence classes can be computed by comparing incidence vectors. There are at most \(3q\) types, and each mass and threshold has binary encoding length \(O(\log q)\). The construction is therefore polynomial in the explicit exact-cover input length.
Suppose \(\mathcal S'\subseteq\mathcal S\) partitions \(U\).
Each equivalence class \(C\) lies entirely in exactly one member \(S\in\mathcal S'\): membership is constant throughout \(C\), and the selected sets partition the universe.
Assign all mass of \(t_C\) to that activity \(a_S\). Every type is fully assigned. Each selected activity receives mass
\(\displaystyle z_{a_S}=\sum_{C:\,C\subseteq S}\mu_{t_C}=\frac1q.\)
Every positive assignment uses an allowed pair and meets its threshold. This is a perfect individually rational assignment.
Conversely, suppose a perfect individually rational assignment exists.
If \(a_S\) is used, then \(z_{a_S}>0\), so some type assigns positive mass to it. Individual rationality implies
\(\displaystyle z_{a_S}\ge\frac1q.\)
Only types with \(C\subseteq S\) can contribute to \(a_S\). Also, nonnegativity and the row-sum constraint imply \(x_{t_C,a_S}\le\mu_{t_C}\). Therefore
\(\displaystyle z_{a_S}=\sum_{C:\,C\subseteq S}x_{t_C,a_S}\le\sum_{C:\,C\subseteq S}\mu_{t_C}=\frac1q.\)
Thus every used activity has mass exactly \(1/q\).
Moreover, equality forces every allowed type to contribute its entire mass to that activity. Explicitly,
\(\displaystyle \sum_{C:\,C\subseteq S}\bigl(\mu_{t_C}-x_{t_C,a_S}\bigr)=0.\)
Each summand is nonnegative, so each equals zero. Hence
\(\displaystyle x_{t_C,a_S}=\mu_{t_C}\qquad\text{for every }C\subseteq S.\)
This is the step that rules out a fractional escape from the reduction.
Two used activities cannot correspond to intersecting sets: an element in their intersection would belong to a type whose entire positive mass must go to both activities, contradicting its row-sum constraint.
Finally, the sets corresponding to used activities cover \(U\). For every equivalence class \(C\), its positive mass is fully assigned, so it contributes positively to some used activity \(a_S\), necessarily with \(C\subseteq S\).
The used sets therefore partition \(U\). Since each has three elements, they form an exact cover of size \(q\). This proves the reduction and establishes \(\mathrm{NP}\)-hardness.
Real assignment variables do not prevent membership in \(\mathrm{NP}\).
A certificate specifies a subset \(D\subseteq E\) of pairs permitted to carry mass. Verify feasibility of the rational linear system consisting of:
All pairs outside \(D\) receive zero mass.
If a perfect assignment exists, choosing its positive support as \(D\) makes this system feasible. Conversely, every feasible solution satisfies individual rationality: each positive pair belongs to \(D\), and its activity mass meets the corresponding threshold.
The certificate has polynomial length. The system has at most \(|E|\) variables and \(\tau+|E|\) substantive constraints, with rational coefficients of polynomial encoding length. The standard polynomial-time theorem for rational linear-programming feasibility therefore supplies a polynomial-time verifier.
Together with the reduction, this proves \(\mathrm{NP}\)-completeness. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. It establishes \(\mathrm{NP}\)-completeness for the stated distribution-over-types model, including divisible masses, distinct support types, and distinct activity approval profiles. I found no major or minor mathematical issues.
The source problem is stated correctly: Exact Cover by 3-Sets asks whether a family of three-element subsets partitions a universe of size \(3q\). The attribution to Theorem 1 of the cited paper is accurate; that theorem uses this source problem. Its additional restriction on intersections is unnecessary for the present reduction. [Cited paper, Theorem 1](https://www.lamsade.dauphine.fr/~lang/papers/DEKLSW18.pdf)
Deleting duplicate sets preserves exact-cover existence: two identical nonempty sets cannot both occur in a partition, and one representative suffices.
The empty-family branch is valid. With \(q\ge1\), the source universe is nonempty and has no exact cover. The proposed output society is infeasible because its only type has positive mass and no allowed pair. Its support and activity restrictions hold.
Equivalence classes. Equality of incidence patterns is an equivalence relation. For any resulting class \(C\) and any set \(S\), membership in \(S\) is constant throughout \(C\). Thus \(C\subseteq S\) or \(C\cap S=\varnothing\), as claimed.
Masses. Every class is nonempty, so \(\mu_{t_C}=|C|/(3q)>0\). Since the classes partition \(U\), these masses sum to \(1\).
Thresholds and preferences. The common threshold \(1/q\) belongs to \((0,1]\), including when \(q=1\). The specified ranking of approved alternatives, void, and disapproved alternatives defines complete preferences consistent with the task. Indifference among disapproved alternatives is permitted.
Eligible mass per activity. The classes contained in \(S\) partition its three elements. Consequently,
\[
\sum_{C:\,C\subseteq S}\mu_{t_C}=\frac1q.
\]
This identity is correct and is the critical capacity bound in the reverse implication.
Distinct support types. Different classes have different incidence patterns. At the admissible positive mass \(1/q\), an activity witnessing this difference is approved by one type and disapproved by the other. Therefore their complete preference types differ.
Distinct activity profiles. Different sets have an element in their symmetric difference. Its class distinguishes the corresponding activities at mass \(1/q\). Thus activity profiles remain distinct after elements are merged into types.
One group per activity. The construction uses one activity for each set, and the assignment model represents its sole group by one column. It introduces no activity copies or additional groups.
Polynomial encoding. Incidence vectors and their equivalence classes can be computed in polynomial time from the explicit source input. There are at most \(3q\) types and \(|\mathcal S|\) activities. The explicit allowed-pair relation has at most \(3q|\mathcal S|\) entries, and all constructed rational numbers have polynomial binary encoding length. The reduction therefore has polynomial running time and output length.
If selected sets partition \(U\), every class is contained in exactly one selected set. Assigning its entire mass there is therefore well-defined and satisfies every row sum.
Each selected activity receives all classes contained in its set, giving mass exactly \(1/q\). Every positive assignment is allowed and meets its threshold. Unselected activities receive zero mass and impose no individual-rationality obligations.
The forward implication is fully justified.
For a used activity, its positive column sum entails a positive contribution from at least one type. Individual rationality then gives \(z_{a_S}\ge1/q\).
Disallowed pairs cannot carry positive mass. Nonnegativity and the row-sum equations give \(x_{t_C,a_S}\le\mu_{t_C}\). Summing these bounds over eligible classes yields \(z_{a_S}\le1/q\). Therefore every used activity has mass exactly \(1/q\).
The subsequent saturation argument is valid: the finitely many nonnegative deficits \(\mu_{t_C}-x_{t_C,a_S}\) sum to zero, so every deficit is zero. Thus every eligible type sends its entire mass to each used activity for which it is eligible. This explicitly excludes fractional splitting as an escape from the reduction.
If two used sets intersect, the class containing an intersection element is eligible for both. Saturation would assign its full positive mass to both columns, contradicting its row sum. Hence used sets are pairwise disjoint.
Every class has positive mass and must contribute to some activity. That activity is used and its set contains the class. Thus used sets cover \(U\). Together with disjointness, this gives an exact cover, necessarily containing \(q\) sets.
Elements belonging to no source set cause no hidden exception: their class has no allowed activity and prevents a perfect assignment, consistently with the absence of an exact cover.
The certificate \(D\subseteq E\) has polynomial length.
Both directions of the certificate characterization are correct:
Allowing zero variables inside \(D\) causes no soundness problem. Threshold constraints attached to such pairs can restrict feasibility, but every accepted solution still satisfies the original requirements.
The invoked theorem is applicable: feasibility of a finite system of non-strict linear inequalities with binary rational coefficients is decidable in time polynomial in its total encoding length. This is the standard polynomial-time linear-programming feasibility result. [Polynomial-time feasibility theorem](https://www.sciencedirect.com/science/article/pii/0196677480900024)
Here all coefficients are rational, the dimensions and encoding length are polynomial, and equalities are admissible through their routine inequality representation. No strict positivity constraints require special handling.
Therefore the proposed certificate has a deterministic polynomial-time verifier, establishing membership in \(\mathrm{NP}\).
No repair or additional clarification is needed. The reduction establishes hardness for the exact continuous model, and the certificate argument establishes \(\mathrm{NP}\)-membership. The conclusion about a polynomial-time algorithm implying \(\mathrm{P}=\mathrm{NP}\) follows.
⟨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.