Answer: Exactly solvable in polynomial time in the explicit input length \(L\); every instance satisfying the stated hypotheses is feasible.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an integer partition G ∈G, every coalition structure in PG is generated exactly once by FCP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) complete agent types with population distribution \(\mu\), a team-size bound \(K\), an explicit coalition welfare table \(w(z)\) for \(z\in\mathcal Z_K=\{z\in\mathbb Z_{\ge0}^{\tau}:1\le\|z\|_1\le K\}\), and a size-intensity vector \(h\) satisfying \(\sum_k kh_k=1\), find \(x_z\ge0\) maximizing \(\sum_z w(z)x_z\) subject to \(\sum_z z_t x_z=\mu_t\) for every type \(t\) and \(\sum_{\|z\|_1=k}x_z=h_k\) for every \(k\).
A society is given by its support: the list of the \(\tau\ge1\) complete types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; agents of the same type are interchangeable.
Given an integer \(K\ge1\), define \(\mathcal Z_K=\{z\in\mathbb Z_{\ge0}^{\tau}:1\le\|z\|_1\le K\}\). Coalition welfare depends only on \(z\), is independent of other coalitions, and is supplied explicitly as a signed binary rational \(w(z)\) for every \(z\in\mathcal Z_K\).
The input also contains binary rationals \(h_k\ge0\) for \(1\le k\le K\), satisfying \(\sum_{k=1}^{K}kh_k=1\); \(h_k\) is the required intensity of size-\(k\) coalitions per unit population mass.
Find nonnegative real intensities \(x_z\) maximizing \(\sum_{z\in\mathcal Z_K}w(z)x_z\), subject to \(\sum_{z\in\mathcal Z_K}z_tx_z=\mu_t\) for every \(t\) and \(\sum_{z\in\mathcal Z_K:\|z\|_1=k}x_z=h_k\) for every \(k\), or report infeasibility.
Let \(L\) be the total binary input length, including the entire welfare table. State running times in \(\tau,K,L\); this model has no separate parameter \(m\).
Is this exact continuous welfare-maximization problem solvable in polynomial time in the explicit input length \(L\), or is it NP-hard?
For finite labelled agents with a prescribed multiset of coalition sizes, an enumeration procedure generates every admissible coalition structure exactly once; this is not a polynomial-time guarantee.
Unrestricted discrete coalition structure generation with an explicit table of all coalition values has a dynamic programming algorithm polynomial in that table's size. These discrete results do not classify the continuous problem above.
The problem is exactly solvable in polynomial time in the explicit input length \(L\). Moreover, every instance satisfying the stated hypotheses is feasible.
The proof uses rational linear programming, with one variable for each entry of the welfare table.
Write \(N=|\mathcal Z_K|\). Introducing a slack coordinate \(z_{\tau+1}=K-\sum_{t=1}^{\tau}z_t\), stars and bars counts all nonnegative vectors with \(\sum_{t=1}^{\tau}z_t\le K\). Removing the zero vector gives
\[ N=\binom{\tau+K}{K}-1. \]
There are \(N\) nonnegative variables and \(\tau+K\) equality constraints. Define the matrix \(A\), right-hand side \(b\), and objective vector \(c\) by
\[ A_{t,z}=z_t \quad(1\le t\le\tau),\qquad A_{\tau+k,z}=\mathbf 1_{\{\|z\|_1=k\}}\quad(1\le k\le K), \]
\[ b=(\mu_1,\ldots,\mu_\tau,h_1,\ldots,h_K),\qquad c_z=w(z). \]
The optimization problem is therefore precisely
\[ \max\{c^{\mathsf T}x:Ax=b,\ x\ge0\}. \]
Every entry of \(A\) is an integer between zero and \(K\), requiring \(O(\log(K+1))\) bits. The entries of \(b\) and \(c\) already occur in the input. Consequently, a dense encoding of this linear program, with nonnegativity specified as variable bounds, has length
\[ B=O\!\left(L+(\tau+K)N\log(K+1)\right). \]
This encoding can be constructed within the same asymptotic bit-operation bound: enumerate the count vectors and write their columns.
Crucially, the welfare table explicitly supplies \(N\) rational values, so \(N\le L\). Also, \(N\ge\tau\), because all unit vectors occur, and \(N\ge K\), because all vectors \(ke_1\), for \(1\le k\le K\), occur. Hence \(\tau+K\le2L\) and
\[ B=O\!\left(L^2\log(L+1)\right). \]
Thus the linear program has polynomial encoding length, even when its number of variables grows rapidly with \(\tau\) and \(K\).
For each type \(t\) and size \(k\), set
\[ x_{ke_t}=h_k\mu_t, \]
and set every other intensity to zero. These homogeneous coalition vectors are distinct, and all intensities are nonnegative.
For each type \(t\), its assigned population mass is
\[ \sum_{z\in\mathcal Z_K}z_tx_z =\sum_{k=1}^{K}kh_k\mu_t =\mu_t, \]
using the hypothesis \(\sum_{k=1}^{K}kh_k=1\).
For each size \(k\), the total coalition intensity is
\[ \sum_{\|z\|_1=k}x_z =\sum_{t=1}^{\tau}h_k\mu_t =h_k, \]
using \(\sum_{t=1}^{\tau}\mu_t=1\). This proves feasibility independently of the welfare values.
For any feasible intensity vector and any \(z\) of size \(k\), nonnegativity and the size constraint imply
\[ 0\le x_z\le\sum_{\|u\|_1=k}x_u=h_k. \]
Moreover, \(kh_k\le1\), since the nonnegative quantities \(jh_j\) sum to one. Therefore \(x_z\le1/k\le1\).
The feasible region is consequently a nonempty, closed subset of the compact box \([0,1]^N\). It is compact, and the linear welfare objective is continuous. Thus a finite maximum is attained. Signed welfare values cause no difficulty.
The standard polynomial-time theorem for rational linear programming states that an explicitly encoded rational linear program can be solved exactly in a number of bit operations polynomial in its encoding length: the algorithm detects infeasibility or unboundedness, or returns a rational optimal solution. Exact rational recovery is part of this guarantee. See [Trevisan’s linear-programming notes, Sections 5.2.4–5.2.5](https://theory.stanford.edu/~trevisan/books/cs261.pdf).
All hypotheses hold here: the coefficients are rational, the encoding is explicit, and Sections 2–3 establish feasibility and a finite attained optimum. Equalities can be replaced by pairs of inequalities, increasing the encoding length by only a constant factor.
Therefore an exact optimizer can be computed in
\[ \operatorname{poly}\!\left( L+(\tau+K)\left[\binom{\tau+K}{K}-1\right]\log(K+1) \right) =L^{O(1)} \]
bit operations. Output coordinates are represented exactly as binary-encoded integer numerators and denominators.
This settles the stated continuous problem. Its rational-threshold decision version belongs to \(\mathrm P\), so NP-hardness under polynomial-time many-one reductions would imply \(\mathrm P=\mathrm{NP}\). No discrete coalition-structure enumeration result is needed.
⟨structured verdict parsed — rendered above⟩
The prover’s conclusion is correct: the exact continuous problem is solvable in polynomial time in the explicit input length \(L\). The feasibility claim is also correct. No major or minor mathematical issues were found.
The slack-coordinate construction is a bijection between nonnegative vectors in \(\mathbb Z^\tau\) with coordinate sum at most \(K\) and nonnegative vectors in \(\mathbb Z^{\tau+1}\) with coordinate sum exactly \(K\). Removing the original zero vector therefore gives
\(N=\binom{\tau+K}{K}-1\).
This includes the boundary cases \(\tau=1\) and \(K=1\). The stated number of variables is correct.
Each column corresponds to exactly one admissible coalition vector. The first \(\tau\) rows enforce the population constraints, and the remaining \(K\) rows enforce the coalition-size intensities. The objective coefficients are precisely the supplied welfare values.
Thus \(\max\{c^{\mathsf T}x:Ax=b,\ x\ge0\}\) is exactly the assigned optimization problem. No integrality restriction or additional interaction between coalitions has been introduced.
There is a linear dependence among the equality rows, because population totals equal the size-weighted coalition totals. This does not invalidate the formulation or the rational LP theorem, which requires no full-rank assumption.
The entries of \(A\) lie between zero and \(K\), so their bit lengths are \(O(\log(K+1))\). The right-hand side and objective already belong to the input. With nonnegativity represented as variable bounds, the stated estimate
\(B=O(L+(\tau+K)N\log(K+1))\)
is valid.
Because the welfare table contains a separately supplied rational for every admissible vector, \(N\le L\). The distinct unit vectors show \(N\ge\tau\), and the distinct vectors \(ke_1\), for \(1\le k\le K\), show \(N\ge K\). These two lower bounds need not come from disjoint families.
Consequently, \(\tau+K\le2L\) and
\(B=O(L^2\log(L+1))\).
Enumerating the bounded count vectors and writing their columns is consistent with the stated construction bound. The argument correctly measures complexity against the entire explicit table rather than only the binary encodings of \(\tau\) and \(K\).
Every vector \(ke_t\) is admissible. Different pairs \((k,t)\) give distinct vectors, so the assignments \(x_{ke_t}=h_k\mu_t\) do not conflict.
For a fixed type \(t\), only its homogeneous coalitions contribute population mass, giving
\(\sum_z z_tx_z=\mu_t\sum_{k=1}^K kh_k=\mu_t\).
For a fixed size \(k\), the total intensity is
\(\sum_{\|z\|_1=k}x_z=h_k\sum_{t=1}^{\tau}\mu_t=h_k\).
All assigned intensities are nonnegative. The construction covers zero values of \(h_k\), as well as \(\tau=1\) and \(K=1\). It establishes feasibility for every instance satisfying the task’s hypotheses.
For a coalition vector of size \(k\), nonnegativity and its size constraint imply \(0\le x_z\le h_k\). Since all \(jh_j\) are nonnegative and sum to one, \(kh_k\le1\), hence \(x_z\le1/k\le1\).
The feasible set is closed, nonempty, and contained in the finite-dimensional compact box \([0,1]^N\). It is therefore compact. The objective is continuous, so a finite maximum is attained. This argument remains valid for arbitrary signed rational welfare values.
The prover states the applicable rational LP theorem precisely enough: polynomial bit complexity in the explicit rational encoding, with infeasibility and unboundedness detection and exact rational optimal output. The cited sections support polynomial-time optimization and exact recovery with polynomial-length rational coordinates. [Trevisan’s notes, Sections 5.2.4–5.2.5](https://theory.stanford.edu/~trevisan/books/cs261.pdf)
All hypotheses are satisfied. Replacing equalities by pairs of inequalities causes only constant-factor encoding growth. Feasibility and boundedness have already been established independently.
The resulting running time,
\(\operatorname{poly}(L+(\tau+K)[\binom{\tau+K}{K}-1]\log(K+1))=L^{O(1)}\),
answers the requested complexity question in \(\tau,K,L\), without introducing a separate parameter.
The rational-threshold decision consequence is correct, including the conditional statement about NP-hardness implying \(\mathrm P=\mathrm{NP}\). The proof does not depend on either discrete result mentioned in the task.
No repair or additional clarification 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.