Answer: \(\mathrm{NP}\)-complete
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-complete to decide whether there exists an FF allocation in a CSA instance, even either under group- oriented preferences or with no trivial group upper quota.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite project set \(P\) partitioned into groups \(P_1,\ldots,P_q\), integer quotas \((\ell_j,u_j)\), a scale \(N\), and a listed support \(T\) of strict rankings with rational masses \(\mu_t>0\) summing to \(1\), does there exist a selection \(y\in\{0,1\}^{P}\) and assignment masses \(x_{tr}\geq 0\) such that \(\sum_{r\in P}x_{tr}=\mu_t\), \(\sum_{t\in T}x_{tr}=y_r/N\), \(\sum_{r\in P}y_r=N\), and \(\ell_j\leq\sum_{r\in P_j}y_r\leq u_j\) for every \(j\), with \(x_{tr}>0\) implying \(r\succ_t p\) for every unselected project \(p\) (that is, every \(p\) with \(y_p=0\))?
Let \(P\) be a set of \(m\) projects partitioned into \(q\geq1\) nonempty groups \(P_1,\ldots,P_q\). The input includes a binary-encoded integer \(1\leq N\leq m\) and integer quotas \(0\leq\ell_j\leq u_j\leq|P_j|\), with \(\sum_j\ell_j\leq N\leq\sum_j u_j\).
A society is given by its support: a list \(T\) of \(\tau\) distinct strict rankings \(\succ_t\) over all projects, each with positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total binary input length; state running times in \(m,\tau,q,N,L\).
A selection and mass assignment consist of \(y\in\{0,1\}^{P}\) and nonnegative real numbers \(x_{tr}\), satisfying \(\sum_{r\in P}x_{tr}=\mu_t\) for every \(t\), \(\sum_{t\in T}x_{tr}=y_r/N\) for every \(r\), \(\sum_{r\in P}y_r=N\), and \(\ell_j\leq\sum_{r\in P_j}y_r\leq u_j\) for every \(j\).
The assignment is frustration-free if \(x_{tr}>0\) implies \(r\succ_t p\) for every project \(p\) with \(y_p=0\). The decision problem asks whether such a frustration-free selection and assignment exist.
Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For a finite list of agents, each assigned one distinct project, frustration-free existence under these partition quotas is \(\mathrm{NP}\)-complete, even when rankings place each group in a contiguous block, or when every \(u_j<|P_j|\); imposing both restrictions yields a polynomial-time algorithm. [Verified discrete results](https://www.ijcai.org/proceedings/2021/0006.pdf).
No published result settling this exact mass formulation was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. Hardness already holds when every scaled mass \(N\mu_t\) is a positive integer.
The crucial observation is that, for a fixed selection, fractional assignments with integer scaled masses can be converted into discrete assignments by flow integrality.
Fix a set \(S\subseteq P\) with \(|S|=N\), satisfying all partition quotas. For each type \(t\), define its eligible projects by
\[ A_t(S)=\{r\in S:\ r\succ_t p\text{ for every }p\in P\setminus S\}. \]
If \(S=P\), the condition is vacuous, so \(A_t(S)=P\). Otherwise, \(A_t(S)\) consists precisely of the projects preceding the highest-ranked unselected project in ranking \(t\).
Construct a directed network with source \(s\), one vertex for each type, one vertex for each selected project, and sink \(v\). Its arcs and capacities are:
Claim. A frustration-free mass assignment with selected set \(S\) exists exactly when this network admits a flow of value \(1\).
Indeed, an assignment gives such a flow by placing \(x_{tr}\) on each eligible type–project arc. Unselected projects receive zero mass because their prescribed column sums are zero.
Conversely, the capacities leaving the source sum to \(1\), as do the capacities entering the sink. A flow of value \(1\) therefore saturates every source–type and project–sink arc. Flow conservation gives the required row and column sums, and the definition of the type–project arcs ensures frustration-freeness.
A certificate specifies only \(S\). The verifier checks its cardinality and quotas, then checks the flow condition above.
Write \(\mu_t=a_t/b_t\), with positive binary integers \(a_t,b_t\), and set
\[ D=N\prod_{t\in T}b_t. \]
Multiplying all capacities by \(D\) produces integer capacities. The target flow value becomes \(D\), and project–sink capacities become \(D/N\). Since the denominator encodings and the encoding of \(N\) are part of the input, \(D\) has \(\mathcal O(L)\) bits. Every scaled capacity is at most \(D\).
The network has at most \(m+\tau+2\) vertices and \(m\tau+m+\tau\) arcs. Eligibility can be computed in \(\mathcal O(m\tau)\) ranking-entry operations by scanning each ranking until its first unselected project.
Using schoolbook integer arithmetic and Edmonds–Karp, a conservative bound for verification is
\[ \mathcal O\!\left( \tau L^2+m\tau+q+ (m+\tau+2)(m\tau+m+\tau)^2L \right) \]
bit operations. Here the initial term covers clearing denominators and constructing integer capacities; the flow term uses the standard bound of \(\mathcal O(VE^2)\) arithmetic operations, each on \(\mathcal O(L)\)-bit integers.
Thus verification is polynomial in \(m,\tau,q,N,L\). In particular, it does not require expanding rational masses into a population of agents. The problem belongs to \(\mathrm{NP}\).
Use the discrete frustration-free existence problem under partition quotas as the source problem. Its input explicitly lists \(n\) agents, each of whom must receive one distinct project. Theorem 2 of the supplied paper establishes that this problem is \(\mathrm{NP}\)-complete. [Belahcene, Mousseau and Wilczynski, *Combining Fairness and Optimality when Selecting and Allocating Projects*](https://www.ijcai.org/proceedings/2021/0006.pdf).
Retain the projects, groups and quotas, and set \(N=n\). Merge agents having identical rankings. For each resulting distinct ranking \(t\), let \(k_t\) be its multiplicity and define
\[ \mu_t=\frac{k_t}{n}. \]
These masses are positive and sum to \(1\), and the resulting support contains exactly the distinct rankings, as required. Moreover, \(\tau\leq N\), and each mass has an encoding of length \(\mathcal O(\log(N+1))\). Grouping the explicitly listed rankings and constructing these masses takes polynomial time.
We prove equivalence in both directions.
Suppose there is a discrete frustration-free allocation with selected set \(S\). Define
\[ x_{tr}=\frac{1}{n} \left|\{i:\text{agent }i\text{ has ranking }t\text{ and receives }r\}\right|. \]
Every type has row sum \(k_t/n=\mu_t\). Each selected project has column sum \(1/n=1/N\), and each unselected project has column sum zero. The selection satisfies the original quotas.
Whenever \(x_{tr}>0\), an agent with ranking \(t\) receives \(r\); discrete frustration-freeness therefore gives \(r\succ_t p\) for every unselected project \(p\). This is a feasible mass solution.
Suppose the constructed instance has a frustration-free mass solution with selected set \(S\). Put \(z_{tr}=n x_{tr}\). Then
\[ \sum_{r\in S}z_{tr}=k_t, \qquad \sum_{t\in T}z_{tr}=1\quad(r\in S), \]
and positive entries occur only on eligible pairs.
Construct a network with source–type capacities \(k_t\), eligible type–project capacities \(1\), and selected project–sink capacities \(1\). The numbers \(z_{tr}\) define a flow of value \(n\): each \(z_{tr}\leq1\) because its project column sums to \(1\).
All capacities are integers. By the integral maximum-flow theorem, there is an integer flow of value \(n\). The total capacities leaving the source and entering the sink both equal \(n\), so all those arcs are saturated.
Consequently, each selected project is assigned to exactly one type, and type \(t\) receives exactly \(k_t\) distinct projects. Assign these projects bijectively to the \(k_t\) original agents having ranking \(t\). Every assigned pair is eligible, so the resulting allocation is frustration-free. Its selected set is \(S\), hence it satisfies every partition quota.
This completes the polynomial reduction.
The reduction proves \(\mathrm{NP}\)-hardness, and the polynomial certificate verifier proves membership in \(\mathrm{NP}\). Therefore the mass formulation is \(\mathrm{NP}\)-complete.
The reduction also preserves contiguous group blocks in rankings and strict group upper quotas. Thus the two separate hardness restrictions stated in the question transfer to the mass formulation.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The mass formulation is \(\mathrm{NP}\)-complete, including when every scaled mass \(N\mu_t\) is a positive integer. The reduction preserves the two separate restrictions mentioned in the task. No major or minor mathematical issues were found.
The definition of \(A_t(S)\) exactly matches the frustration-free condition for a selected project. With strict rankings and \(S\ne P\), a project precedes every unselected project precisely when it precedes the highest-ranked unselected project. The treatment of \(S=P\) correctly handles the vacuous condition.
The proposed network correctly characterizes feasibility:
Both directions are valid, including the boundary case \(N=m\).
A certificate consisting only of \(S\) has polynomial length. Its cardinality and partition quotas can be checked directly; the flow characterization supplies a deterministic feasibility check.
The denominator-clearing calculation is correct. For
\(D=N\prod_t b_t\), each of
\(D\mu_t=a_t(D/b_t)\), \(D\), and \(D/N\) is an integer. Their capacities are at most \(D\), because \(0<\mu_t\leq1\) and \(N\geq1\).
The bit length of \(D\) is bounded by the sum of the input bit lengths of \(N\) and the denominators, up to an additive constant. Hence it is \(\mathcal O(L)\), even though its numerical value can be large. The argument does not confuse numerical magnitude with encoding length.
The network-size bounds are valid:
\(V\leq m+\tau+2\) and \(E\leq m\tau+m+\tau\).
Eligibility scanning takes \(\mathcal O(m\tau)\) ranking-entry operations, with a full scan when \(S=P\).
The stated Edmonds–Karp bound applies to these finite networks. Its augmentation bound is independent of capacity magnitudes, while capacity and residual-flow arithmetic uses \(\mathcal O(L)\)-bit integers. The initial \(\mathcal O(\tau L^2)\) term conservatively accommodates denominator clearing and associated input processing. Thus the displayed verification bound is polynomial in the requested parameters.
The \(\mathrm{NP}\)-membership conclusion is justified without requiring real-valued assignment entries in the certificate.
The cited theorem matches the source problem. The paper defines allocations as injections assigning one project to every explicitly listed agent, uses strict rankings, and defines frustration-freeness by comparison with every unassigned project. Its partition-quota assumptions also match the task.
Theorem 2 establishes \(\mathrm{NP}\)-completeness, separately under group-oriented preferences and under the condition that every group upper quota is strictly below its size. Group-oriented preferences mean contiguous group blocks, as required here. These definitions and the theorem were checked against the [cited paper](https://www.ijcai.org/proceedings/2021/0006.pdf).
The hardness citation is therefore applicable.
Setting \(N=n\) respects \(1\leq N\leq m\) for the source instances.
Merging identical rankings produces exactly the distinct support rankings required by the target representation. Each multiplicity \(k_t\) is positive, and
\(\sum_t k_t=n\), so the constructed masses \(\mu_t=k_t/n\) are positive and sum to \(1\).
Each numerator and denominator has \(\mathcal O(\log(N+1))\) bits. Because the source explicitly lists its agents and rankings, grouping them and retaining one copy per distinct ranking is polynomial in source input length. There is no exponential expansion hidden in the construction.
Finally, \(N\mu_t=k_t\) is a positive integer, establishing the claimed restriction on scaled masses.
The definition of \(x_{tr}\) correctly aggregates discrete assignments by ranking type and divides by \(n\).
Its row sums are \(k_t/n\). Injectivity of the discrete allocation gives column sum \(1/n\) for every selected project and zero for every unselected project.
Every positive entry corresponds to an original agent receiving that project. Since all agents of a type have the same ranking, discrete frustration-freeness implies exactly the target eligibility condition. Quotas are unchanged.
This implication is fully established.
Scaling by \(n\) correctly yields type totals \(k_t\) and selected-project totals \(1\). Nonnegativity and the column totals imply \(z_{tr}\leq1\), so the eligible type–project capacities are respected. The scaled assignment therefore defines a flow of value \(n\).
The integral maximum-flow theorem applies: the constructed network is finite and all capacities are nonnegative integers. The existing flow has value \(n\), and the total source capacity is \(n\), so the maximum-flow value is exactly \(n\). An integral maximum flow consequently has that value.
Saturation of the source and sink arcs gives exactly \(k_t\) projects to each type and exactly one type to each selected project. Integral flow on capacity-\(1\) type–project arcs ensures these are distinct assignments. The stated bijections to original agents preserve eligibility because their rankings agree.
The recovered discrete allocation is frustration-free and satisfies the original quotas. This direction is fully justified.
The polynomial reduction establishes \(\mathrm{NP}\)-hardness, and the polynomial verifier establishes membership in \(\mathrm{NP}\). Preserving rankings, groups, and quotas also preserves each separate hardness restriction. The output makes no unsupported claim about imposing both restrictions simultaneously.
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.