Answer: Polynomial-time solvable; the problem belongs to \(\mathsf{P}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an input and a strategy profile, deciding whether there is a coalition of size~$t$ that has an improvement step is $\wtwo$-hard wrt.~$t$ even if all teams are of size one. It remains $\np$-complete if there is no restriction on the coalition size.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given discrete time slots and a finite support \(Q\) of types \(q=(A_q,B_q)\), each with rational mass \(\mu_q\), where \(B_q\le A_q\in\{0,1\}^m\) is its current report and true availability, decide whether a positive mass can coordinate on new reports. Choose masses \(x_{q,D}\ge 0\) for reports \(D\le A_q\), with \(\sum_D x_{q,D}\le\mu_q\); all remaining mass keeps report \(B_q\). Let \(S_j\) be the resulting average reported attendance at slot \(j\), let \(W=\arg\max_j S_j\), and let \(u_q\) be type \(q\)'s current payoff, computed from \(B_q\) and the current co-winners by the paper's maximin rule. Does there exist such an allocation with positive total deviating mass for which every report \(D\) used by positive mass of type \(q\) yields \(\min_{j\in W}D_j/S_j>u_q\), with winning-slot denominators positive?
There are \(m\ge1\) time slots. A society is given by its support: the list of \(\tau\) types \(q=(A_q,B_q)\) with positive masses \(\mu_q\) encoded as binary rationals, where \(A_q,B_q\in\{0,1\}^m\) and \(B_q\le A_q\) coordinatewise. Require \(\sum_q\mu_q=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Set \(S_j^0=\sum_q\mu_q B_{qj}\), require \(\max_j S_j^0>0\), and define \(W^0=\arg\max_j S_j^0\) and \(u_q=\min_{j\in W^0}B_{qj}/S_j^0\). Ties are evaluated adversarially through this minimum; attendance equals the report, rather than true availability.
For each type, let \(\mathcal D_q=\{D\in\{0,1\}^m:D\le A_q\}\). A coalition allocation consists of real masses \(x_{q,D}\ge0\) satisfying \(\sum_{D\in\mathcal D_q}x_{q,D}\le\mu_q\); remaining mass keeps \(B_q\). Reports may increase coordinates relative to \(B_q\), and coalition members may retain \(D=B_q\).
The resulting attendance is \(S_j=\sum_q[(\mu_q-\sum_{D\in\mathcal D_q}x_{q,D})B_{qj}+\sum_{D\in\mathcal D_q}x_{q,D}D_j]\), with \(W=\arg\max_j S_j\).
Call the allocation improving if \(\sum_{q,D}x_{q,D}>0\), \(\max_j S_j>0\), and every pair with \(x_{q,D}>0\) satisfies \(\min_{j\in W}D_j/S_j>u_q\). Coalition mass has no additional bound.
Is deciding whether an improving allocation exists solvable in time polynomial in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard?
For finite societies of teams of size one, existence of an improving coalition of unrestricted size is \(\mathsf{NP}\)-complete; bounding coalition size by \(t\) gives \(\mathsf{W}[2]\)-hardness parameterized by \(t\). [Bredereck et al.](https://arxiv.org/pdf/1611.08892)
No result settling this exact mass-allocation problem was located in the literature search.
Theorem. The decision problem is solvable in time polynomial in \(m,\tau,L\). It suffices to solve two rational linear programs per time slot.
1. Initial utilities. Write \(c=\max_j S_j^0>0\). Every initial winning slot has attendance \(c\), and reports are binary. Therefore
\[ u_q= \begin{cases} 1/c,& B_{qj}=1\text{ for every }j\in W^0,\\ 0,& B_{qj}=0\text{ for some }j\in W^0. \end{cases} \]
Thus there are only two initial utility levels. Define \(Z=\{q:u_q=0\}\).
2. Reduction to a unique winning slot. We prove that every improving allocation can be replaced by one in which every coalition member reports the same unit vector \(e_k\), and \(k\) is the unique winner.
Take an improving allocation \(x\), and put \(s=\max_j S_j>0\) and \(C=\sum_{q,D}x_{q,D}>0\). For every pair with \(x_{q,D}>0\), improvement and \(u_q\ge0\) imply \(D_j=1\) at every \(j\in W\): otherwise that pair’s new utility would be zero.
Choose any \(k\in W\), and define \(y_q=\sum_Dx_{q,D}\). Replace every participating report by \(e_k\), keeping the same participating masses \(y_q\). This is feasible: whenever \(y_q>0\), some participating report has \(D_k=1\), so \(A_{qk}=1\) and hence \(e_k\le A_q\). Also \(0\le y_q\le\mu_q\).
Let \(S'_j\) denote attendance after this replacement. Attendance at \(k\) is unchanged, since all participating reports already had coordinate \(k\) equal to one. Thus \(S'_k=s\). For \(j\ne k\),
\[ S'_j=S_j-\sum_{q,D}x_{q,D}D_j. \]
If \(j\in W\setminus\{k\}\), the subtracted mass is exactly \(C\), so \(S'_j=s-C<s\). If \(j\notin W\), then \(S'_j\le S_j<s\). Consequently \(k\) is the unique winner.
Each participating pair previously had utility \(1/s\), because its report was one at every original winning slot. After replacement it still has utility \(1/s\). Thus the replacement remains improving.
This argument permits a participant’s replacement report to equal its initial report, as allowed in the question.
3. The linear programs. Fix a candidate slot \(k\). For masses \(y_q\) participating with report \(e_k\), attendance is
\[ T_k(y)=S_k^0+\sum_q(1-B_{qk})y_q, \]
and, for \(j\ne k\),
\[ T_j(y)=S_j^0-\sum_qB_{qj}y_q. \]
Both expressions are affine functions of the participating masses.
For each \(k\), construct two programs. Both maximize a variable \(\varepsilon\), subject to the common constraints
\[ 0\le y_q\le\mu_q\quad\text{for every }q,\qquad 0\le\varepsilon\le1, \]
\[ \sum_qy_q\ge\varepsilon,\qquad T_k(y)\ge\varepsilon, \]
\[ T_k(y)-T_j(y)\ge\varepsilon \quad\text{for every }j\ne k. \]
The additional constraints distinguish the two programs:
Accept if any of these programs has a strictly positive optimum; reject otherwise. An infeasible program does not cause acceptance.
The variable \(\varepsilon\) handles strict inequalities exactly. A positive feasible value guarantees positive coalition mass, positive winning attendance, and a unique winner. In the second program it additionally guarantees winning attendance strictly below \(c\).
4. Correctness. First suppose a program has a feasible solution with \(\varepsilon>0\). Set \(x_{q,e_k}=y_q\) for the permitted types and set all other allocation variables to zero. The bounds and availability restrictions make this allocation feasible. The common constraints give positive coalition mass, \(T_k(y)>0\), and \(W=\{k\}\).
In the zero-utility program, every participant has initial utility zero and receives \(1/T_k(y)>0\), so every participant strictly improves.
In the lower-attendance program, \(0<T_k(y)<c\). Every participant therefore receives
\[ \frac1{T_k(y)}>\frac1c\ge u_q, \]
so this allocation also improves. This proves soundness.
Conversely, suppose an improving allocation exists. Apply the reduction in part 2, obtaining participating masses \(y_q\), unique winner \(k\), and winning attendance \(s>0\).
If every participating type belongs to \(Z\), these masses satisfy the restrictions of the zero-utility program. If some participating type has positive initial utility, its improvement requires \(1/s>1/c\); since \(s,c>0\), this implies \(s<c\). The masses then satisfy the restrictions of the lower-attendance program.
In either case, all quantities that must be strictly positive are indeed positive: coalition mass, winning attendance, and every gap between the winning attendance and a rival’s attendance. In the second case, \(c-s\) is positive as well. Choose \(\varepsilon>0\) no larger than one and no larger than any of these finitely many positive quantities. The corresponding program has a positive feasible objective value, and hence a positive optimum. This proves completeness.
5. Bit complexity. Computing \(S_j^0\), \(c\), \(W^0\), and \(Z\) requires polynomially many rational arithmetic operations. Their bit lengths are polynomially bounded by \(L\): for example, a common denominator for the input masses can be taken as the product of their denominators, whose bit length is at most the sum of their encoded bit lengths.
Each program has \(\tau+1\) variables and \(O(m+\tau)\) constraints, all with rational coefficients of polynomial bit length. Its feasible region is bounded by the explicit bounds on \(y_q\) and \(\varepsilon\).
We use the standard polynomial-time theorem for rational linear programming: feasibility and the exact optimum of a bounded rational linear program can be computed in time polynomial in its encoded size. All hypotheses hold here. In particular, comparing the exact optimum with zero requires no numerical tolerance or assumed minimum improvement.
There are \(2m\) programs, so the complete decision procedure runs in time polynomial in \(m,\tau,L\). A positive optimum also supplies an improving allocation using at most one coalition report per type.
The finite-society hardness result concerns indivisible participants. Here the participating masses are real variables, and the preceding proof reduces their selection to linear programming. [Bredereck et al., Theorem 3](https://arxiv.org/pdf/1611.08892)
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated mass-allocation problem correctly: its decision procedure runs in polynomial time. No major or minor mathematical issues were found.
The assumption \(c=\max_j S_j^0>0\) ensures every initial winning denominator is positive. Since all slots in \(W^0\) have attendance \(c\), each binary report gives initial utility either \(0\) or \(1/c\). The definition of \(Z\) therefore captures exactly the types with zero initial utility, including under adversarial ties.
For every participating pair, strict improvement over a nonnegative initial utility requires its report to equal one at every winning slot. Otherwise its minimum utility would be zero.
Consequently, for any chosen \(k\in W\), every participating type can feasibly report \(e_k\). Aggregating its participating mass into \(y_q\) preserves the bounds \(0\le y_q\le\mu_q\).
Attendance at \(k\) remains \(s\). For every other slot, the stated identity
\[
S'_j=S_j-\sum_{q,D}x_{q,D}D_j
\]
follows directly by keeping the nonparticipating mass unchanged and replacing participating reports by \(e_k\). At another original winner, the subtracted quantity is exactly \(C>0\); at an original nonwinner, attendance cannot increase. Thus \(k\) becomes the unique winner.
Every participant’s utility remains \(1/s\), so strict improvement is preserved. Aggregating different reports of the same type introduces no utility issue because the initial utility depends only on the type. Replacement reports equal to initial reports are expressly permitted by the task.
With participating reports \(e_k\), the candidate slot gains precisely the participating mass whose initial coordinate was zero. Every other slot loses precisely the participating mass whose initial coordinate was one. This verifies both affine attendance formulas.
The availability restrictions ensure that every positive participating mass has \(e_k\in\mathcal D_q\). The zero-utility program additionally restricts participation to \(Z\). The lower-attendance program permits either initial utility level while requiring attendance strictly below \(c\) whenever \(\varepsilon>0\).
The common constraints with \(\varepsilon>0\) guarantee positive coalition mass, positive attendance at \(k\), and strict dominance over every rival slot. Thus the resulting winner set is exactly \(\{k\}\).
In the zero-utility program, every participant obtains positive utility over initial utility zero. In the lower-attendance program, \(0<T_k(y)<c\) gives
\[
\frac{1}{T_k(y)}>\frac{1}{c}\ge u_q.
\]
Both programs therefore satisfy every condition in the task’s definition of improvement.
The reduction produces a unique winner with positive attendance and positive coalition mass. If every participating type has zero initial utility, its masses satisfy the zero-utility program’s restrictions.
Otherwise, a positive participating mass belongs to a type with initial utility \(1/c\). Its strict improvement forces \(1/s>1/c\), hence \(s<c\). The masses then satisfy the lower-attendance program’s restrictions.
The quantities used to choose \(\varepsilon\) are finitely many strictly positive numbers. Their positive minimum, capped at one, gives a positive feasible objective value. This argument does not assume rationality of the original improving allocation or a uniform minimum improvement.
When \(m=1\), the rival-slot constraints are absent, and the completeness argument still has positive coalition mass and winning attendance available for choosing \(\varepsilon\). No minimum over an empty family is required.
Types with no availability at the candidate slot are excluded. Zero participating masses impose no improvement requirement. Initial ties and reports retained by coalition members are handled explicitly. The argument introduces no additional coalition-mass restriction.
The denominator-product bound correctly gives polynomial bit length for the initial attendance values and their comparisons. Each LP has \(\tau+1\) variables and \(O(m+\tau)\) constraints with rational coefficients of polynomial bit length.
The cited rational linear-programming theorem is stated sufficiently precisely for the application: feasibility and exact optimization of bounded rational LPs are computable in polynomial time. The explicit variable bounds make every feasible region bounded; the inequalities make it closed. Thus a feasible program has an attained finite optimum, and infeasible programs are handled separately.
Exact comparison of the optimum with zero is legitimate. Solving \(2m\) such programs establishes the claimed polynomial running time without enumerating the exponentially many possible reports.
The cited [Bredereck et al., Theorem 3](https://arxiv.org/pdf/1611.08892) states unrestricted-coalition NP-completeness even for teams of size one. Its finite participants are indivisible, whereas the submitted LPs select real participating masses. The prover establishes its continuous result independently of that citation.
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.