Answer: For every fixed \(s\geq1\), the threshold problem is in \(\mathrm P\). The attained optimum is \(1/s!\), so an assignment exists exactly when \(B\geq1/s!\).
Theorem 5.5 — class: other
Given a finite type set \(T\), rational masses \(\mu_t\), and a fixed coalition size \(s\), let \(\Omega=[0,1)\) be an atomless population with a measurable type map whose type regions have masses \(\mu_t\). Let coalition tasks be unordered sets of \(s\) distinct points, with measure \(\nu_s\) induced by \(\lambda^{\otimes s}/s!\). Find a measurable assignment \(a(S)\in S\) minimizing \(\operatorname*{ess\,sup}_{x\in\Omega} d\rho/d\lambda(x)\), where \(\rho(A)=\nu_s(\{S:a(S)\in A\})\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Let \(\Omega=[0,1)\) carry Lebesgue measure \(\lambda\); realize the listed types on consecutive half-open intervals of lengths \(\mu_t\). Types impose no eligibility restrictions or differences in calculation cost.
Fix an integer \(s\geq1\). Every unordered set of \(s\) distinct population points is a coalition task of unit cost. Write \(\mathcal C_s\) for this space, with its quotient measurable structure, and let \(q(x_1,\ldots,x_s)=\{x_1,\ldots,x_s\}\) on distinct tuples.
The task measure is \(\nu_s(E)=\lambda^{\otimes s}(q^{-1}(E))/s!\); it is not normalized to a probability measure.
An assignment is a deterministic measurable map \(a:\mathcal C_s\to\Omega\) satisfying \(a(S)\in S\), assigning each task exactly once. For measurable \(A\subseteq\Omega\), set \(\rho_a(A)=\nu_s(\{S:a(S)\in A\})\) and \(M(a)=\operatorname*{ess\,sup}_{x\in\Omega}(d\rho_a/d\lambda)(x)\).
The optimization problem is to minimize \(M(a)\). Its threshold problem has an additional nonnegative binary rational \(B\); let \(L\) be the total input bit length. State running times in \(\tau,L\), with dependence on \(s\) explicit; there is no separate candidate parameter \(m\).
For each fixed \(s\geq1\), is deciding whether there exists an assignment \(a\) with \(M(a)\leq B\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
Discrete: for \(n\) cyclically numbered agents, a circular offset array of length \(s\), with nonnegative entries summing to \(n-s\) and least repetition period \(p\), generates the same coalition from starting IDs \(i,j\) exactly when \(j-i\) is an integer multiple of \(np/s\). [Source](https://doi.org/10.1609/aaai.v29i1.9433).
A later discrete treatment proves member-only assignments of all size-\(s\) coalitions with agent loads differing by at most one. [Source](https://arxiv.org/html/2604.17057v1). No result settling the exact continuous threshold problem was located.
For every fixed \(s\geq1\), the threshold problem belongs to \(\mathrm P\). More precisely, for every society in the question,
\(\displaystyle \min_a M(a)=\frac1{s!},\)
and the minimum is attained by a deterministic measurable member-only assignment. Thus the answer is yes exactly when \(B\geq1/s!\), including equality.
The types and their masses do not affect this conclusion: under the stated hypotheses, every coalition has the same cost and every member is eligible.
Let \(D_s\subseteq\Omega^s\) be the set of tuples with distinct coordinates. Its complement is a finite union of coordinate diagonals, each of product Lebesgue measure zero. Consequently,
\(\displaystyle \nu_s(\mathcal C_s)=\frac{\lambda^{\otimes s}(D_s)}{s!}=\frac1{s!}.\)
For any measurable assignment \(a\) and any Lebesgue measurable \(A\subseteq\Omega\), membership of \(a(S)\) in \(A\) implies that at least one member of \(S\) lies in \(A\). The union bound therefore gives
\(\displaystyle \rho_a(A) \leq\frac1{s!}\lambda^{\otimes s}\bigl(\{(x_1,\ldots,x_s)\in D_s:\text{some }x_i\in A\}\bigr) \leq\frac{s}{s!}\lambda(A). \)
In particular, \(\rho_a\) is absolutely continuous with respect to \(\lambda\). Its Radon–Nikodym density \(f_a=d\rho_a/d\lambda\) is nonnegative and satisfies
\(\displaystyle \int_\Omega f_a\,d\lambda=\rho_a(\Omega)=\frac1{s!}.\)
Since \(\lambda(\Omega)=1\), its essential supremum is at least its integral. Hence every assignment satisfies
\(\displaystyle M(a)\geq\frac1{s!}.\)
It remains to construct an assignment attaining this bound.
For \(s=1\), the compulsory assignment \(a(\{x\})=x\) has \(\rho_a=\lambda\), so its maximum load is \(1=1/s!\).
Assume henceforth that \(s\geq2\). Identify \([0,1)\) with the circle, with addition modulo one. Write a coalition in increasing order as
\(\displaystyle S=\{y_1,\ldots,y_s\},\qquad 0\leq y_1<\cdots<y_s<1.\)
Define its circular gaps by
\(\displaystyle g_j=y_{j+1}-y_j\quad(1\leq j<s), \qquad g_s=1+y_1-y_s. \)
If there is a unique largest gap, assign the coalition to the member immediately after that gap in the positive circular direction. Explicitly, choose \(y_{j+1}\) when the largest gap is \(g_j\) with \(j<s\), and choose \(y_1\) when it is \(g_s\).
If the largest gap is tied, choose \(y_1\).
This defines exactly one member of every coalition. It is also measurable. Indeed, sorting is Borel measurable, and the choice is determined by finitely many comparisons of affine functions of the sorted coordinates. On distinct ordered tuples, the resulting selected point is therefore a coordinate projection on each member of a finite Borel partition. Its inverse image of every Lebesgue measurable set is product measurable. The rule is symmetric in the original tuple coordinates, so it descends to a measurable map on the specified quotient space.
Consider the sorted chamber
\(\displaystyle H_s=\{(y_1,\ldots,y_s):0\leq y_1<\cdots<y_s<1\}.\)
For distinct indices \(j,k\), the equality \(g_j=g_k\) is a nonconstant affine equation in the coordinates.
To verify nonconstancy, the linear parts of the gaps are
\(\displaystyle e_{j+1}-e_j\quad(j<s),\qquad e_1-e_s\quad(j=s),\)
where \(e_i\) denotes the \(i\)-th coordinate vector. These vectors are distinct: for \(s=2\) they are negatives of one another, and for \(s\geq3\) their ordered pairs of positive and negative coordinate positions are distinct.
Thus each equality \(g_j=g_k\) lies in an affine hyperplane of Lebesgue measure zero. There are finitely many such pairs, so the set of sorted configurations with any two equal gaps has measure zero. Taking its coordinate permutations proves that the corresponding subset of \(D_s\) also has product measure zero.
In particular, the set \(N\subseteq\mathcal C_s\) of coalitions whose largest gap is tied satisfies \(\nu_s(N)=0\).
For \(\theta\in[0,1)\), let \(R_\theta(x)=x+\theta\pmod1\), and apply this rotation to every member of a coalition.
Rotations preserve the circular gaps and their successor endpoints. They therefore preserve \(N\), and the assignment constructed above satisfies
\(\displaystyle a(R_\theta S)=R_\theta a(S)\qquad(S\notin N).\)
Rotations also preserve \(\nu_s\): their coordinatewise action preserves product Lebesgue measure and commutes with the quotient map \(q\).
Let \(\rho=\rho_a\). For every Borel set \(A\subseteq\Omega\), measure preservation, the displayed equivariance, and \(\nu_s(N)=0\) give
\(\displaystyle \rho(R_\theta^{-1}A) =\nu_s\bigl(\{S:R_\theta a(S)\in A\}\bigr) =\nu_s\bigl(\{S:a(R_\theta S)\in A\}\bigr) =\rho(A). \)
We now compute \(\rho\) directly. Integrating this identity over \(\theta\) and applying Tonelli’s theorem to the nonnegative Borel integrand yields
\(\displaystyle \rho(A) =\int_0^1\rho(R_\theta^{-1}A)\,d\theta =\int_\Omega\left(\int_0^1\mathbf1_A(R_\theta x)\,d\theta\right)d\rho(x). \)
For each fixed \(x\), the map \(\theta\mapsto R_\theta x\) preserves Lebesgue measure, so the inner integral equals \(\lambda(A)\). Consequently,
\(\displaystyle \rho(A)=\lambda(A)\rho(\Omega)=\frac{\lambda(A)}{s!}.\)
This equality extends from Borel sets to all Lebesgue measurable sets because \(\rho\ll\lambda\), as proved in Section 1. Therefore
\(\displaystyle \frac{d\rho_a}{d\lambda}=\frac1{s!}\quad\text{almost everywhere},\)
and \(M(a)=1/s!\). Together with the lower bound, this proves the asserted minimum and its attainment.
The [cited discrete treatment, Theorem 9](https://arxiv.org/html/2604.17057v1), establishes per-size load imbalance at most one. The argument here establishes the continuous threshold directly, without requiring a passage to a limit of discrete assignments.
Write the threshold as \(B=b/d\), with binary integers \(b\geq0\) and \(d>0\). Decide the instance by the exact integer comparison
\(\displaystyle b\,s!\geq d.\)
No enumeration of types or coalitions is needed.
For explicit dependence on \(s\), put \(K_s=1+\lceil\log_2(s!)\rceil\). Successively multiplying the integers from \(1\) through \(s\), using schoolbook binary arithmetic, computes \(s!\) in \(O(s^2\log^2(s+1))\) bit operations. Multiplication of \(b\) by this factorial and comparison with \(d\) take \(O(LK_s+L+K_s)\) bit operations.
Including reading the support list, a valid overall bound is
\(\displaystyle O\bigl(\tau+L+LK_s+s^2\log^2(s+1)\bigr).\)
For each fixed \(s\), this is \(O(\tau+L)\), hence polynomial time. The algorithm operates on the promised valid inputs; the support masses do not enter its threshold comparison.
⟨structured verdict parsed — rendered above⟩
The output resolves the requested threshold problem. The proof establishes an attained optimum of \(1/s!\), including feasibility at equality, and gives a valid polynomial-time decision algorithm for every fixed \(s\geq1\). No major or minor mathematical issues were found.
\[
\rho_a(A)\leq \frac{s}{s!}\lambda(A).
\]
Thus absolute continuity is justified for every admissible assignment. Both measures are finite, so the Radon–Nikodym theorem applies. The density has integral \(1/s!\); since the population measure is one, the essential-supremum lower bound follows.
\[
\rho(A)=\frac{\lambda(A)}{s!}.
\]
Absolute continuity correctly extends this equality to Lebesgue measurable sets. Thus the constructed assignment has constant density almost everywhere and attains the lower bound. In particular, the argument proves feasibility at \(B=1/s!\), rather than merely an infimum.
Repair feedback: None required. The proof addresses determinism, measurability, exceptional configurations, exact attainment, and the requested complexity parameters.
⟨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.