Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(\tau\); therefore not FPT unless \(\mathrm{FPT}=\mathrm{W}[1]\). An XP algorithm runs in \((m+1)^\tau\operatorname{poly}(m,\tau,d,L)\) time.
Theorem 5.3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet Γ a CRG game where agents are of at most t types, and k ∈N an integer. Then for any fixed t it is polynomially tractable to decide whether there exists a successful coalition of size k in Γ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite support of CRG types with masses \(\mu_t\), each type’s accepted goals and per-agent resource endowments \(e(t,r)\), per-population goal demands \(q(g,r)\), and target mass \(\kappa\), does there exist a mass vector \(x\) and goal set \(S\subseteq G\) such that \(0\le x_t\le\mu_t\), \(\sum_t x_t=\kappa\), every type with \(x_t>0\) accepts at least one goal in \(S\), and \(\sum_t x_t e(t,r)\ge\sum_{g\in S}q(g,r)\) for every resource \(r\)?
A society is given by its support: a list of \(\tau\) representational types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Let \(G\) and \(R\) be finite nonempty sets of goals and resources, with \(m=|G|\) and \(d=|R|\). Type \(t\) specifies an accepted-goal set \(A_t\subseteq G\), possibly empty, and per-agent endowments \(e(t,r)\in\mathbb{Z}_{\ge0}\); identical descriptions constitute one type.
Each goal has binary rational demands \(q(g,r)\ge0\), measured per unit of total population. A selected goal is achieved in full, incurs its demand once, and satisfies all participating mass of every type accepting it. Demands add across goals; resources are pooled within the coalition.
The input also specifies a binary rational target \(0<\kappa\le1\). A successful coalition consists of \(x\in\mathbb{R}^{\tau}\) and \(\varnothing\ne S\subseteq G\) satisfying \(0\le x_t\le\mu_t\), \(\sum_t x_t=\kappa\), \(x_t>0\Rightarrow A_t\cap S\ne\varnothing\), and \(\sum_t x_t e(t,r)\ge\sum_{g\in S}q(g,r)\) for every \(r\in R\).
Let \(L\) be the total input bit length; state running times in \(m,\tau,d,L\).
Is deciding whether such a successful coalition exists in \(\mathrm{P}\), or is it NP-hard?
If it is NP-hard, is it nevertheless FPT parameterized by \(\tau\)?
For explicitly listed discrete agents, existence of a successful coalition of exact size \(k\) is polynomial-time solvable for every fixed number of types, an XP result ([source](https://u.cs.biu.ac.il/~sarit/data/articles/On_Agent_Types.pdf)).
The discrete problem is NP-hard and \(\mathrm{W}[1]\)-hard parameterized by \(k\) ([source](https://u.cs.biu.ac.il/~sarit/data/articles/shortetal-aamas09.pdf)). No result settling this exact continuous formulation was located.
The problem is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[1]\)-hard parameterized by the support size \(\tau\). Consequently, it is not FPT in \(\tau\) unless \(\mathrm{FPT}=\mathrm{W}[1]\).
Hardness holds even when \(\kappa=1\), every endowment equals \(1\), and every demand belongs to \(\{0,1\}\).
Nevertheless, there is an XP algorithm with running time
\(\displaystyle \left(\sum_{j=1}^{\min\{m,\tau\}}\binom{m}{j}\right)\operatorname{poly}(m,\tau,d,L)\le (m+1)^\tau\operatorname{poly}(m,\tau,d,L).\)
The proofs below apply directly to the stated continuous formulation.
For a nonempty goal set \(S\subseteq G\), define
\(\displaystyle B(S)=\{t:A_t\cap S\ne\varnothing\},\qquad Q_S(r)=\sum_{g\in S}q(g,r).\)
A successful coalition using \(S\) exists exactly when the following rational linear system is feasible:
\(\displaystyle 0\le x_t\le\mu_t\quad\text{for every }t,\)
\(\displaystyle x_t=0\quad\text{for every }t\notin B(S),\)
\(\displaystyle \sum_{t=1}^{\tau}x_t=\kappa,\)
\(\displaystyle \sum_{t=1}^{\tau}x_t e(t,r)\ge Q_S(r)\quad\text{for every }r\in R.\)
Indeed, forcing unsatisfied types to have zero participation is equivalent to the required implication \(x_t>0\Rightarrow A_t\cap S\ne\varnothing\). All remaining constraints are precisely those in the question.
This system has \(\tau\) variables and \(O(\tau+d)\) constraints. Its encoding length is polynomial in \(L\): summing input rationals produces rationals of polynomial bit length, since a common denominator can be chosen as the product of their denominators. Rational linear-programming feasibility is decidable in polynomial time.
Thus a verifier can take \(S\), encoded by \(m\) bits, as its certificate and check the system in time \(\operatorname{poly}(m,\tau,d,L)\). This proves membership in \(\mathrm{NP}\), despite allowing real participation masses.
Lemma. Whenever a successful coalition exists, one exists using at most \(\tau\) goals.
Proof. Let \((x,S)\) be successful and put \(T_+=\{t:x_t>0\}\). Since \(\kappa>0\), this set is nonempty. For each \(t\in T_+\), choose one goal \(g_t\in A_t\cap S\), and put
\(\displaystyle S'=\{g_t:t\in T_+\}.\)
Then \(S'\) is nonempty, satisfies every participating type, and has size at most \(|T_+|\le\tau\). Moreover, \(S'\subseteq S\) and demands are nonnegative, so
\(\displaystyle Q_{S'}(r)\le Q_S(r)\le\sum_t x_t e(t,r)\)
for every resource \(r\). Hence \((x,S')\) is successful. \(\square\)
Enumerating all nonempty goal sets of size at most \(\min\{m,\tau\}\), and checking each linear system, therefore gives the stated XP running time. In particular, the continuous problem is polynomial-time solvable for every fixed \(\tau\).
Let \(H=(V,E)\) be a simple undirected graph with \(n=|V|\), and let \(2\le k\le n\). We construct an instance that admits a successful coalition exactly when \(H\) has a clique of size \(k\).
The restriction \(2\le k\le n\) does not affect either classical or parameterized hardness: excluded cases can be decided directly. We use the standard NP-completeness of Clique and its \(\mathrm{W}[1]\)-completeness parameterized by \(k\). The latter also follows from the \(\mathrm{W}[1]\)-completeness of Independent Set by complementing the graph without changing \(k\). [Downey and Fellows](https://homepages.ecs.vuw.ac.nz/~downey/publications/2.pdf)
Create exactly \(k\) types, indexed by \(i\in\{1,\ldots,k\}\). Create goals
\(\displaystyle G=\{g_{i,v}:1\le i\le k,\ v\in V\},\)
and give type \(i\) the accepted-goal set
\(\displaystyle A_i=\{g_{i,v}:v\in V\}.\)
These sets are nonempty and pairwise disjoint. Thus the type descriptions are distinct, as required, and \(\tau=k\). The number of goals is \(m=kn\).
Choose positive dyadic masses
\(\displaystyle \mu_i=2^{-i}\quad(1\le i<k),\qquad \mu_k=2^{-(k-1)}.\)
Their sum is \(1\), since
\(\displaystyle \sum_{i=1}^{k-1}2^{-i}+2^{-(k-1)}=1.\)
Set \(\kappa=1\).
For positions \(i<j\), call a vertex pair \((u,v)\) incompatible when either \(u=v\) or \(\{u,v\}\notin E\).
For every such choice of \(i,j,u,v\), create a resource \(r_{i,j,u,v}\). Also create a dummy resource \(r_0\), ensuring that \(R\) is nonempty.
Set
\(\displaystyle e(i,r)=1\quad\text{for every type }i\text{ and resource }r.\)
For an incompatibility resource \(r_{i,j,u,v}\), set
\(\displaystyle q(g,r_{i,j,u,v})= \begin{cases} 1,&g\in\{g_{i,u},g_{j,v}\},\\ 0,&\text{otherwise}. \end{cases}\)
All goals have zero demand on \(r_0\). These demands are charged once per selected goal, exactly as stipulated in the question.
The number of resources satisfies
\(\displaystyle d=1+\binom{k}{2}\bigl(n^2-2|E|\bigr)\le 1+\binom{k}{2}n^2.\)
All demands and endowments use constant-size numerical encodings; the masses have total bit length \(O(k^2)\). With an explicit table encoding, both the output length and construction time are bounded by \(O(k^3n^3\log(kn+2))\). Since \(k\le n\), this is a polynomial-time construction.
Any feasible participation vector satisfies
\(\displaystyle \sum_{i=1}^k(\mu_i-x_i)=1-\kappa=0.\)
Each summand is nonnegative. Therefore every summand is zero, giving
\(\displaystyle x_i=\mu_i>0\quad\text{for every }i.\)
Consequently, every type must be satisfied. Also, every resource has available amount exactly
\(\displaystyle \sum_i x_i e(i,r)=\sum_i\mu_i=1.\)
Suppose \(H\) has a clique consisting of distinct vertices \(v_1,\ldots,v_k\). Select
\(\displaystyle S=\{g_{i,v_i}:1\le i\le k\},\qquad x_i=\mu_i.\)
Every type accepts its corresponding selected goal.
Consider any incompatibility resource \(r_{i,j,u,v}\). Its demand could equal \(2\) only if both \(g_{i,u}\) and \(g_{j,v}\) were selected. This would imply \(u=v_i\) and \(v=v_j\). But \(v_i,v_j\) are distinct adjacent vertices, so that pair is compatible, contradicting the existence of this resource.
Thus each incompatibility resource has demand at most \(1\), equal to its available amount. The dummy resource has demand zero. Hence \((x,S)\) is successful.
Suppose \((x,S)\) is successful. Every \(x_i\) is positive, so \(S\cap A_i\ne\varnothing\) for every \(i\). Choose one vertex \(v_i\) such that \(g_{i,v_i}\in S\).
Fix \(i<j\). If \(v_i=v_j\) or \(\{v_i,v_j\}\notin E\), the construction contains resource \(r_{i,j,v_i,v_j}\). Both of its demand-incurring goals belong to \(S\), so its total demand is \(2\). Its available amount is \(1\), a contradiction.
Therefore the vertices \(v_1,\ldots,v_k\) are pairwise distinct and pairwise adjacent. They form a clique of size \(k\).
This proves the equivalence in both directions.
The construction is a polynomial-time reduction from Clique. Together with membership in \(\mathrm{NP}\), it proves that the continuous problem is \(\mathrm{NP}\)-complete.
It is also a parameterized reduction: the output support size is exactly \(\tau=k\). Hence the problem is \(\mathrm{W}[1]\)-hard parameterized by \(\tau\). An algorithm running in time
\(\displaystyle f(\tau)(m+\tau+d+L)^c,\)
with computable \(f\) and constant \(c\) independent of \(\tau\), would give an FPT algorithm for parameterized Clique and imply \(\mathrm{FPT}=\mathrm{W}[1]\).
The XP algorithm is consistent with the cited discrete fixed-type result: polynomial time for each fixed number of types does not require a polynomial exponent independent of that number. [Shrot, Aumann, and Kraus, Theorem 5.3](https://u.cs.biu.ac.il/~sarit/data/articles/On_Agent_Types.pdf)
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem. The continuous decision problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by the support size \(\tau\), with the claimed XP algorithm. I found no major or minor mathematical issues requiring repair.
For a fixed nonempty \(S\), the definition of \(B(S)\) correctly identifies precisely those types accepting at least one selected goal. Because participation is nonnegative, requiring \(x_t=0\) for \(t\notin B(S)\) is equivalent to the satisfaction implication in the task. Types in \(B(S)\) may participate with any mass within their prescribed bounds.
The equality fixing total participation and the resource inequalities match the task exactly. In particular, goal demands are summed once per selected goal and are not multiplied by participation mass. Empty accepted-goal sets are handled correctly: those types are forced to have zero participation.
The stated linear-programming theorem applies to feasibility of a finite system with binary rational coefficients and decides it in time polynomial in its encoding length. The displayed system satisfies these hypotheses: endowments are integers, and masses, the target, and aggregated demands are rational.
The bit-length argument is valid. A product of input denominators has bit length bounded by the sum of their bit lengths; forming the corresponding summed numerators also produces polynomial-length integers. There are \(\tau\) variables and \(O(\tau+d)\) constraints, with a polynomial number of encoded coefficients.
A deterministic polynomial-time verifier may therefore receive only the \(m\)-bit description of \(S\) and decide whether suitable real participation masses exist. A separate certificate for the participation vector is unnecessary. The certificate must describe a nonempty set, as the output explicitly requires.
The condition \(\kappa>0\) ensures that \(T_+\) is nonempty. For each participating type, success supplies a goal in \(A_t\cap S\), so every stated choice \(g_t\) exists.
The resulting \(S'\) is nonempty, contains at most \(\tau\) goals, and satisfies every type with positive participation. Retaining the same vector \(x\) preserves all participation constraints. Since demands are nonnegative and \(S'\subseteq S\), every resource demand weakly decreases.
The argument also covers repeated choices of the same goal and types with zero participation.
The lemma justifies enumerating all nonempty goal sets of size at most \(\min\{m,\tau\}\). Each feasibility check takes \(\operatorname{poly}(m,\tau,d,L)\) time.
The enumeration count and bound
\[
\sum_{j=1}^{\min\{m,\tau\}}\binom{m}{j}\le (m+1)^\tau
\]
are correct for the relevant positive integer values of \(m\) and \(\tau\). Thus the algorithm is polynomial for each fixed \(\tau\), while its exponent may depend on \(\tau\), as required for an XP result.
For \(2\le k\le n\), the construction has \(kn\) goals and \(k\) types. Their accepted-goal sets are nonempty and pairwise disjoint, so the type descriptions remain distinct even though all endowments agree. Consequently, the support size really is \(\tau=k\).
Every mass is positive and dyadic. The displayed sum equals \(1\), including the boundary case \(k=2\). Equal masses for the final two types do not merge their distinct descriptions.
The target \(\kappa=1\), integer endowments equal to \(1\), and demands in \(\{0,1\}\) all satisfy the task’s restrictions. The dummy resource ensures that the resource set is nonempty.
For each position pair \(i<j\), there are \(n^2\) ordered vertex pairs. In a simple undirected graph, precisely \(2|E|\) of these represent adjacent vertices. Hence there are \(n^2-2|E|\) incompatible pairs, including every equal-vertex pair.
This verifies
\[
d=1+\binom{k}{2}(n^2-2|E|).
\]
Together with \(m=kn\), the explicit demand table has \(O(k^3n^3)\) entries. The claimed logarithmic allowance for encoding and indexing, and the \(O(k^2)\) total mass encoding, fit within the stated construction bound. Since \(k\le n\), the reduction is polynomial in the explicitly represented graph input size.
Every difference \(\mu_i-x_i\) is nonnegative. Their sum is zero because both total support mass and required participation equal \(1\). Therefore each difference vanishes, giving \(x_i=\mu_i>0\).
This forces satisfaction of every type. Because every endowment equals \(1\), the available amount of each resource is exactly \(1\). These conclusions apply to every feasible vector, so fractional participation cannot bypass the construction.
A clique of size \(k\) supplies one selected goal for each type, giving a nonempty goal set and satisfying every participating type.
Each incompatibility resource charges exactly two distinct goals, belonging to different positions. With the proposed selection, demand \(2\) would require the corresponding clique vertices to be incompatible. Their distinctness and adjacency exclude this. Thus every such demand is at most the available amount \(1\); the dummy-resource demand is zero.
Forced positive participation ensures that \(S\) contains a goal accepted by each type, so each choice \(v_i\) exists.
If any chosen pair were equal or nonadjacent, its incompatibility resource would exist and both demand-incurring goals would belong to \(S\). Its demand would be exactly \(2\), exceeding its availability \(1\). Additional selected goals cannot remove this violation.
Therefore every chosen pair consists of distinct adjacent vertices, establishing a clique of size \(k\). The argument does not assume that a successful coalition originally selects exactly one goal per type.
The output states the standard NP-completeness of Clique and supplies a polynomial-time equivalence reduction. Together with the verified membership argument, this establishes NP-completeness.
The cited parameterized source explicitly states Clique’s \(\mathrm{W}[1]\)-completeness in Corollary 3.2. Its problem definition matches the reduction’s source problem. [Downey and Fellows](https://homepages.ecs.vuw.ac.nz/~downey/publications/2.pdf)
The construction has polynomial running time with a constant exponent and output parameter exactly \(\tau=k\), meeting the requirements of a parameterized reduction. The excluded trivial Clique cases are directly decidable and do not affect hardness.
Consequently, an FPT algorithm parameterized by \(\tau\) would yield one for parameterized Clique. The conditional conclusion “unless \(\mathrm{FPT}=\mathrm{W}[1]\)” is correctly qualified; unconditional nonexistence of an FPT algorithm is not claimed.
The discrete comparison is also accurate: the cited Theorem 5.3 states polynomial solvability of exact-size successful-coalition existence for every fixed number of types. That comparison is contextual and is not used to establish the continuous result. [Shrot, Aumann, and Kraus](https://u.cs.biu.ac.il/~sarit/data/articles/On_Agent_Types.pdf)
No additional lemma, hypothesis, or clarification is needed to verify the claimed conclusions.
⟨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.