Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
Given a finite type set \(T\), rational masses \(\mu_t\ge 0\) summing to \(1\), nonnegative-weight issue formulas built from \(\land\), \(\lor\), and quota tests \(z_t\ge q\) for rational \(q\), nonnegative payment rates \(p_t\) with \(\sum_t\mu_t p_t=V(\mu)\), and a rational goal \(\gamma\), decide whether some proper nonempty coalition mass vector \(z\) with \(0\le z_t\le\mu_t\) satisfies \(V(z)-\sum_t p_tz_t>\gamma\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\) explicitly represented Boolean issue formulas \(F_j\), built using \(\land\), \(\lor\), parentheses, and atoms \(z_t\ge q\) with \(q\in\mathbb Q\); issue weights satisfy \(w_j\in\mathbb Q_{\ge0}\). Define \(V(z)=\sum_{j:F_j(z)=\mathrm{true}}w_j\); a quota test is true at equality.
The input also gives payment rates \(p_t\in\mathbb Q_{\ge0}\) satisfying \(\sum_t\mu_t p_t=V(\mu)\), and a goal \(\gamma\in\mathbb Q\). A coalition is a real vector \(z\) with \(0\le z_t\le\mu_t\); it is proper and nonempty exactly when \(0<\sum_t z_t<1\).
Decide whether such a coalition satisfies \(V(z)-\sum_t p_tz_t>\gamma\). Let \(L\) be the total binary input length, including formula encodings; state running times in \(m,\tau,L\).
Is this continuous MOST-VIOLATED-COALITION decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite agents, MOST-VIOLATED-COALITION is \(\mathrm{NP}\)-complete for MC-nets with nonnegative pattern weights and both \(\land\) and \(\lor\) allowed ([Li–Conitzer](https://users.cs.duke.edu/~conitzer/complexityAAMAS14.pdf)). No result settling the exact continuous quota-formula problem above was identified in the literature search.
The problem is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions. Hardness holds even when all masses are equal dyadic rationals, all issue weights are \(1\), and every issue formula is a disjunction of two atoms. Thus a polynomial-time algorithm for the general problem would imply \(\mathrm P=\mathrm{NP}\).
The proof below handles the budget condition, fractional coalitions, properness, and the strict objective inequality explicitly.
Write \(\Phi(z)=V(z)-\sum_{t\in T}p_tz_t\). For each type \(t\), define
\[
D_t=\{0\}\cup\{q:0<q\leq\mu_t\text{ and the atom }z_t\geq q\text{ occurs in the input}\}.
\]
In the required inline notation, this is \(D_t=\{0\}\cup\{q:0<q\leq\mu_t\text{ and }z_t\geq q\text{ occurs in the input}\}\).
Rounding lemma. For every feasible coalition \(z\), there exists \(y\in\prod_{t\in T}D_t\) such that \(y_t\leq z_t\) for every \(t\), every input atom has the same truth value at \(y\) and \(z\), and \(\Phi(y)\geq\Phi(z)\).
Proof. Set \(y_t=\max\{d\in D_t:d\leq z_t\}\), which exists because \(0\in D_t\).
Consider an input atom \(z_t\geq q\).
Thus all atoms, and consequently all formulas, have identical truth values. Hence \(V(y)=V(z)\). Since each \(p_t\geq0\) and \(y_t\leq z_t\), we obtain \(\Phi(y)\geq\Phi(z)\). This proves the lemma.
The only difficulty is that rounding a nonempty coalition might produce the zero vector. The following observation handles that case.
Zero-vector observation. If \(V(0)>\gamma\), a proper nonempty coalition satisfying the strict inequality exists.
Proof. Put \(\delta=V(0)-\gamma>0\), choose any type \(r\), and set
\( \varepsilon=\min\{\mu_r/2,\delta/[2(p_r+1)]\} \).
Let \(z_r=\varepsilon\) and let every other coordinate be zero. Then
\(0<\sum_tz_t=\varepsilon\leq1/2<1\).
Every formula is monotone in the coordinates: atoms are monotone, and both allowed connectives preserve monotonicity. Nonnegative issue weights therefore imply \(V(z)\geq V(0)\). Moreover, \(p_r\varepsilon\leq\delta/2\), so
\(\Phi(z)\geq V(0)-\delta/2=\gamma+\delta/2>\gamma\).
Now suppose \(V(0)\leq\gamma\) and a proper nonempty witness \(z\) exists. Apply the rounding lemma. The resulting \(y\) remains proper because \(\sum_ty_t\leq\sum_tz_t<1\). It is nonempty: otherwise, equality of formula truth values would give \(V(z)=V(0)\), and consequently
\(\Phi(z)\leq V(0)\leq\gamma\), contradicting the witness inequality.
We have therefore proved the exact characterization:
The answer is yes if and only if either \(V(0)>\gamma\), or there exists a proper nonempty vector \(y\in\prod_tD_t\) with \(\Phi(y)>\gamma\).
Each coordinate of such a grid witness is either zero or an input quota. A certificate can specify its input occurrence, using \(O(\tau\log(L+1))\) bits altogether. Formula evaluation and exact rational comparisons take polynomial time. This proves membership in \(\mathrm{NP}\).
We use the known \(\mathrm{NP}\)-completeness of unweighted MAX-CUT: given a simple undirected graph \(G=(U,E)\) and a positive integer \(K\), decide whether some vertex subset has at least \(K\) crossing edges. This is the Simple Max Cut problem established by [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Let \(n=|U|\geq2\), and choose \(N=2^{\lceil\log_2n\rceil}\). Add isolated vertices to obtain a graph \(\widehat G\) on \(N\) vertices. This preserves every attainable cut size, and \(n\leq N<2n\).
Construct the society as follows.
\(F_e(z)=(z_u\geq1/N)\lor(z_v\geq1/N)\), with weight \(w_e=1\).
All masses are positive dyadic rationals, and all payments and weights are nonnegative rationals. There are \(m=|E|\) issues.
At the grand coalition, every issue is true, so \(V(\mu)=|E|\). By the degree-sum identity,
\(\displaystyle \sum_t\mu_tp_t=\sum_t\frac1N\frac{N\deg_{\widehat G}(t)}2=\frac12\sum_t\deg_{\widehat G}(t)=|E|=V(\mu).\)
Thus the constructed instance satisfies the required payment condition exactly.
For a vertex subset \(S\), let \(z^S_t=\mu_t\) when \(t\in S\), and \(z^S_t=0\) otherwise.
Write \(a(S)\) for the number of edges with both endpoints in \(S\), and \(c(S)\) for the number with exactly one endpoint in \(S\). An issue is true precisely when its edge has an endpoint in \(S\). Consequently,
\(V(z^S)=a(S)+c(S)\).
The degree sum over \(S\) equals \(2a(S)+c(S)\), so
\(\displaystyle \sum_tp_tz^S_t=\frac12\sum_{t\in S}\deg_{\widehat G}(t)=a(S)+\frac{c(S)}2.\)
Subtracting gives the central identity
\(\Phi(z^S)=c(S)/2\).
If \(c(S)\geq K\), then \(K\geq1\) implies that \(S\) is nonempty and proper. Hence \(z^S\) is a proper nonempty coalition, and
\(\displaystyle \Phi(z^S)=\frac{c(S)}2\geq\frac K2>\frac{2K-1}4=\gamma.\)
Thus every yes-instance of MAX-CUT yields a yes-instance of the continuous problem.
Conversely, suppose a proper nonempty real coalition \(z\) satisfies \(\Phi(z)>\gamma\). Define its set of fully included types by
\(S=\{t:z_t=\mu_t\}\).
Because \(0\leq z_t\leq\mu_t=1/N\), the atom \(z_t\geq1/N\) is true exactly when \(t\in S\). Therefore,
\(V(z)=a(S)+c(S)\).
Nonnegative payments give
\(\displaystyle \sum_tp_tz_t\geq\sum_{t\in S}p_t\mu_t=a(S)+\frac{c(S)}2.\)
It follows that \(\Phi(z)\leq c(S)/2\). Combining this with the strict witness inequality yields
\(\displaystyle \frac{c(S)}2>\frac{2K-1}4,\qquad c(S)>K-\frac12.\)
Since \(c(S)\) is an integer, \(c(S)\geq K\). Isolated padding vertices affect no crossing edges, so the original graph also has a cut of size at least \(K\).
This proves both directions of the reduction. The quarter-unit offset in \(\gamma\) explicitly converts the integer MAX-CUT threshold into the required strict inequality.
The reduction has \(\tau=N<2n\), \(m=|E|\), and output length
\(L=O((m+\tau)\log(\tau+1)+\log(K+1))\).
Degrees, payments, and formulas can all be constructed in polynomial time.
For general instances, the certificate verification above takes
\((m+\tau+L)^{O(1)}\) bit operations.
There is also an exact deterministic algorithm: first check \(V(0)>\gamma\), then enumerate the quota grid and test every proper nonempty point. If \(a_t=|D_t|-1\), the grid contains \(\prod_t(a_t+1)\) points. Since the total number of atom occurrences is at most \(L\), this gives running time
\(\displaystyle O\!\left((L+1)^\tau(m+\tau+L)L^3\right)\)
as a conservative bound using elementary exact integer arithmetic. In particular, the problem is polynomial-time solvable for every fixed support size \(\tau\), while it is \(\mathrm{NP}\)-complete when \(\tau\) is part of the input.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned problem. It establishes \(\mathrm{NP}\)-completeness for the stated continuous decision problem, including the budget constraint, real-valued coalitions, properness, and strict inequality. I found no major or minor mathematical issues.
Quota grid. Each \(D_t\) is finite and contains zero. The definition correctly excludes positive quotas exceeding \(\mu_t\), whose atoms are always false on feasible coalitions, and nonpositive quotas, whose atoms are always true.
Rounding lemma. The maximum defining \(y_t\) exists, and \(0\leq y_t\leq z_t\leq\mu_t\). The three cases for an input quota exhaust all possibilities. For a quota in \(D_t\), a true atom remains true because its quota is an eligible value in the maximum; a false atom remains false because \(y_t\leq z_t\). This includes equality at a quota.
Identical atom values imply identical formula values. Thus \(V(y)=V(z)\), and nonnegative payment rates give \(\Phi(y)\geq\Phi(z)\). Every claimed part of the lemma follows.
Zero-vector observation. A type \(r\) exists because positive masses sum to one. Both quantities defining \(\varepsilon\) are positive, and
\[
0<\varepsilon\leq\mu_r/2\leq1/2.
\]
The constructed coalition is therefore feasible, nonempty, and proper. Monotonicity follows from the permitted atoms and connectives; nonnegative weights then give \(V(z)\geq V(0)\). The payment estimate \(p_r\varepsilon\leq\delta/2\) is valid, including when \(p_r=0\). The strict objective inequality follows.
Nonempty grid witnesses. When \(V(0)\leq\gamma\), rounding a successful witness cannot produce zero: that would imply \(V(z)=V(0)\), and nonnegative payments would contradict \(\Phi(z)>\gamma\). Properness is preserved by coordinatewise decrease.
Consequently, the stated characterization is exact. Its reverse implication also holds: the zero-vector branch has the constructed witness, and every qualifying grid point is itself a valid coalition.
Certificate size and verification. An occurrence index or zero marker identifies each coordinate using \(O(\log(L+1))\) bits. The total certificate length is polynomial. Formula evaluation, feasibility, properness, and the strict rational comparison are all polynomial-time checks. The zero-vector branch can be accepted deterministically without a grid certificate.
Membership in \(\mathrm{NP}\) is established.
Source theorem. The cited theorem supplies precisely the required unweighted MAX-CUT decision problem: an undirected graph and a positive integer threshold, asking for a cut with at least that many edges. The cited paper confirms \(\mathrm{NP}\)-completeness of Simple Max Cut. Restricting attention to graphs with at least two vertices excludes only trivial cases and does not undermine hardness. [Garey–Johnson–Stockmeyer](https://www.acs.uwinnipeg.ca/ychen2/journalpapers/Garey-Johnson-2maxsat.pdf)
Padding and representation. The chosen power of two satisfies \(n\leq N<2n\). Adding isolated vertices preserves attainable cut sizes. The masses are positive dyadic rationals summing to one. Every issue has exactly the claimed form, and all weights and payments have the required signs.
Budget condition. The calculation is correct:
\[
\sum_t\mu_tp_t
=\frac12\sum_t\deg_{\widehat G}(t)
=|E|
=V(\mu).
\]
The degree-sum identity applies to the constructed undirected graph, and every edge issue is true at the grand coalition.
Whole-type coalitions. For a subset \(S\), the issue count is \(a(S)+c(S)\), while its payment is
\[
\frac12\sum_{t\in S}\deg_{\widehat G}(t)
=a(S)+\frac{c(S)}2.
\]
Hence the claimed identity \(\Phi(z^S)=c(S)/2\) is correct.
If \(c(S)\geq K\geq1\), there is a crossing edge, so both \(S\) and its complement are nonempty. The associated coalition is proper and nonempty. The threshold calculation is also correct: \(K/2\) exceeds \((2K-1)/4\) by \(1/4\).
Arbitrary fractional coalitions. Because each coordinate is bounded above by \(1/N\), an issue atom is true exactly when its type is fully included. Thus the set \(S\) defined in the proof determines all issue values.
Payments from partially included types are nonnegative, so dropping them gives the stated lower bound on total payment. Consequently,
\[
\Phi(z)\leq\frac{c(S)}2.
\]
Combining this with the witness inequality yields \(c(S)>K-1/2\). Integrality then gives \(c(S)\geq K\). Removing isolated padding vertices preserves that cut size in the original graph.
Both directions of the reduction are valid. Fractional coordinates cannot create a false positive.
The output-length bound is consistent with the construction. Type identifiers, quotas, masses, degrees, and payments require \(O(\log(\tau+1))\) bits per relevant entry; the goal requires \(O(\log(K+1))\) bits. The construction is polynomial-time.
The general certificate-verification bound \((m+\tau+L)^{O(1)}\) is valid.
The grid contains exactly \(\prod_t(a_t+1)\) points. Since there are at most \(L\) atom occurrences, the bound \((L+1)^\tau\) follows. Exact rational checks have polynomial bit complexity: selected quotas come from the input, and the sums and products used in verification have polynomially bounded representations. The displayed \(O((L+1)^\tau(m+\tau+L)L^3)\) bound is sufficiently conservative for elementary exact arithmetic and grid preparation.
Thus the fixed-support polynomial-time conclusion and the general \(\mathrm{NP}\)-completeness conclusion are both justified.
None required. No unjustified substantive step, false assertion, missing hypothesis, or unresolved edge case was identified.
⟨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.