Answer: \(\mathrm{NP\text{-}complete}\)
Theorem 12 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSOCIAL OPTIMUM is NP-hard even for sim- ple games with k = 2. On the positive side, by exploiting known results for the DENSEST t-SUBGRAPH problem, it is possible to prove the following theorem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), rational capacities \(\beta_1,\beta_2>0\) summing to \(1\), and a symmetric matrix \(A\in\{0,1\}^{|T|\times|T|}\), find \(x_{ti}\ge0\) with \(\sum_i x_{ti}=\mu_t\) and \(\sum_t x_{ti}=\beta_i\) maximizing \(\operatorname{SW}_\infty(x)=\sum_{i=1}^{2}\sum_{t,u\in T}a_{tu}x_{ti}x_{ui}\), or decide whether the optimum is at least a rational threshold \(q\).
Definitions. An instance has a finite type set \(T\), rational masses \(\mu_t\geq 0\) with \(\sum_{t\in T}\mu_t=1\), rational capacities \(\beta_1,\beta_2>0\) with \(\beta_1+\beta_2=1\), and a symmetric matrix \(A=(a_{tu})_{t,u\in T}\in\{0,1\}^{T\times T}\). A feasible allocation satisfies \(x_{ti}\geq0\), \(\sum_{i=1}^2x_{ti}=\mu_t\), and \(\sum_{t\in T}x_{ti}=\beta_i\). Its welfare is \(\operatorname{SW}_\infty(x)=\sum_{i=1}^2\sum_{t,u\in T}a_{tu}x_{ti}x_{ui}\).
Target. Is deciding whether the maximum feasible value of \(\operatorname{SW}_\infty(x)\) is at least a rational threshold \(q\) solvable in polynomial time, or is it NP-hard?
Nearest known results. The discrete prescribed-size two-coalition social-welfare problem is NP-hard even for unweighted undirected graphs. No continuous-side result is assumed here.
The welfare-threshold problem is \(\mathrm{NP\text{-}complete}\). In particular, it is \(\mathrm{NP\text{-}hard}\) even when:
Thus fractional divisibility does not make the problem polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
Write \(n=|T|\), let \(\mu\) denote the mass vector, and set \(y_t=x_{t1}\). Feasibility is equivalent to
\[ 0\leq y_t\leq\mu_t,\qquad \sum_{t\in T}y_t=\beta_1, \]
with \(x_{t2}=\mu_t-y_t\). By symmetry of \(A\),
\[ \begin{aligned} \operatorname{SW}_\infty(y) &=y^{\mathsf T}Ay+(\mu-y)^{\mathsf T}A(\mu-y)\\ &=2y^{\mathsf T}Ay-2\mu^{\mathsf T}Ay+\mu^{\mathsf T}A\mu. \end{aligned} \]
Fractional splitting cannot simply be ignored. For example, take two types of mass \(1/2\), capacities \(1/2,1/2\), and
\[ A=\begin{pmatrix}0&1\\1&0\end{pmatrix}. \]
Every unsplit allocation has welfare \(0\), whereas splitting both types equally gives welfare \(1/4\). Consequently, the quoted discrete hardness result alone does not imply the desired continuous hardness.
Let \(H\) be a simple graph with adjacency matrix \(A_H\), and let \(\omega(H)\) be its clique number.
\[ \max\left\{p^{\mathsf T}A_Hp:p\geq0,\ \sum_{v\in V(H)}p_v=1\right\} =1-\frac1{\omega(H)}. \]
Let \(C\) be a maximum clique, and put \(p_v=1/|C|\) for \(v\in C\) and \(p_v=0\) otherwise. Since \(A_H\) has zero diagonal and contains both orientations of every edge,
\[ p^{\mathsf T}A_Hp =\left(\sum_{v\in C}p_v\right)^2-\sum_{v\in C}p_v^2 =1-\frac1{\omega(H)}. \]
This proves the lower bound.
For the upper bound, choose a maximizing \(p\) having minimum support. Suppose two distinct support vertices \(u,v\) are nonadjacent. Fix every coordinate except \(p_u,p_v\), and fix their sum \(s=p_u+p_v\). Because \(a_{uu}=a_{vv}=a_{uv}=0\), the objective is affine as a function of \(p_u\in[0,s]\). It therefore attains at least its present value at one endpoint. Moving to that endpoint removes \(u\) or \(v\) from the support without decreasing the objective, contradicting the choice of \(p\).
Thus the support of \(p\) is a clique, say of size \(m\leq\omega(H)\). Hence
\[ p^{\mathsf T}A_Hp =1-\sum_vp_v^2 \leq1-\frac1m \leq1-\frac1{\omega(H)}, \]
where \(\sum_vp_v^2\geq1/m\) follows from Cauchy–Schwarz. This proves the lemma. \(\square\)
We use the standard \(\mathrm{NP\text{-}complete}\) problem CUBIC INDEPENDENT SET: given a simple \(3\)-regular graph \(G\) and an integer \(k\), decide whether \(\alpha(G)\geq k\).
Let \(G\) have \(n\) vertices, and let \(H=\overline G\). Then \(H\) is regular of degree
\[ r=n-4, \]
and
\[ \omega(H)=\alpha(G). \]
Construct the welfare instance as follows:
\[ T=V(H),\qquad \mu_v=\frac1n,\qquad \beta_1=\frac1n,\qquad \beta_2=1-\frac1n, \]
and let \(A=A_H\).
For every feasible allocation, put \(p=ny\). Then \(p\geq0\) and \(\sum_vp_v=1\). Conversely, every such \(p\) defines a feasible allocation by \(y=p/n\), because \(p_v\leq1\) implies \(y_v\leq1/n=\mu_v\). Thus the feasible allocations are in bijection with the probability simplex.
Since \(H\) is \(r\)-regular,
\[ A\mathbf1=r\mathbf1. \]
Consequently,
\[ y^{\mathsf T}Ay=\frac1{n^2}p^{\mathsf T}Ap,\qquad \mu^{\mathsf T}Ay=\frac r{n^2},\qquad \mu^{\mathsf T}A\mu=\frac rn. \]
The normal form therefore gives
\[ \operatorname{SW}_\infty(y) =\frac rn-\frac{2r}{n^2} +\frac2{n^2}p^{\mathsf T}Ap. \]
Applying the fractional clique lemma,
\[ \operatorname{OPT} =\frac rn-\frac{2r}{n^2} +\frac2{n^2}\left(1-\frac1{\omega(H)}\right). \]
Set the rational threshold
\[ q= \frac rn-\frac{2r}{n^2} +\frac2{n^2}\left(1-\frac1k\right). \]
The function \(m\mapsto1-1/m\) is strictly increasing for positive integers \(m\). Hence
\[ \operatorname{OPT}\geq q \quad\Longleftrightarrow\quad \omega(H)\geq k \quad\Longleftrightarrow\quad \alpha(G)\geq k. \]
The construction and the binary encoding of \(q\) have polynomial size. This proves \(\mathrm{NP\text{-}hardness}\).
Importantly, the reduction does not assume an integral optimum: the fractional clique lemma computes the optimum over the entire simplex.
For completeness, consider an arbitrary input. After eliminating coalition \(2\), the feasible region is the bounded rational polytope
\[ P=\left\{y:0\leq y_t\leq\mu_t,\ \sum_ty_t=\beta_1\right\}, \]
and the objective is a rational quadratic polynomial \(f(y)=y^{\mathsf T}Qy+c^{\mathsf T}y+c_0\).
Let \(y^\star\) be a global maximizer, and let \(F\) be the minimal face of \(P\) containing \(y^\star\). Then \(y^\star\) lies in the relative interior of \(F\). If \(L\) is the direction space of \(F\), first-order optimality gives
\[ \nabla f(y^\star)^{\mathsf T}d=0 \qquad\text{for every }d\in L. \]
Define
\[ S=\left\{z\in\operatorname{aff}(F): \nabla f(z)^{\mathsf T}d=0\text{ for every }d\in L\right\}. \]
Because \(\nabla f\) is affine and rational, \(S\) is a rational affine space. Moreover, \(S\cap F\) is nonempty because it contains \(y^\star\).
For any \(z,w\in S\), let \(\delta=z-w\in L\). Both gradients annihilate \(\delta\), so
\[ 2\delta^{\mathsf T}Q\delta =\bigl(\nabla f(z)-\nabla f(w)\bigr)^{\mathsf T}\delta =0. \]
It follows that
\[ f(z)-f(w) =\nabla f(w)^{\mathsf T}\delta+\delta^{\mathsf T}Q\delta =0. \]
Thus every point of \(S\cap F\) has the same objective value as \(y^\star\). The bounded rational polytope \(S\cap F\) has a rational vertex \(\widehat y\). Standard determinant bounds for vertices of rational polyhedra show that \(\widehat y\) has encoding length polynomial in the input length. Therefore every yes-instance has a polynomial-size rational optimal allocation certificate. Feasibility and the inequality \(f(\widehat y)\geq q\) can be checked exactly in polynomial time.
Hence the problem belongs to \(\mathrm{NP}\).
The continuous two-coalition welfare-threshold problem is \(\mathrm{NP\text{-}complete}\). The hardness already holds for uniform masses and highly unbalanced capacities, and it explicitly accounts for all fractional allocations.
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes NP-hardness and gives a substantively sound argument for membership in \(\mathrm{NP}\). The reduction genuinely optimizes over fractional allocations rather than assuming integrality. Two minor clarifications are needed: the reduction must restrict to \(k\geq 1\), and the polynomial encoding claim in the NP-membership argument needs its coefficient-size hypotheses stated explicitly.
Setting \(y_t=x_{t1}\) gives \(x_{t2}=\mu_t-y_t\), and the stated feasibility conditions are equivalent to the original constraints.
The expansion
\[ \operatorname{SW}_\infty(y) =2y^{\mathsf T}Ay-2\mu^{\mathsf T}Ay+\mu^{\mathsf T}A\mu \]
is correct because \(A\) is symmetric.
The two-type example is also correct. An unsplit allocation separates the two types and has welfare \(0\), while splitting each type equally gives welfare \(1/4\), accounting for both ordered orientations in each coalition.
The lemma is the Motzkin–Straus identity in the normalization appropriate for a symmetric adjacency matrix.
The lower bound is computed correctly: uniform mass on a clique of size \(\omega(H)\) gives \(1-1/\omega(H)\).
For the upper bound:
No substantive gap occurs in this lemma.
For a simple \(3\)-regular graph \(G\) on \(n\) vertices, its complement \(H\) is indeed \((n-4)\)-regular, and \(\omega(H)=\alpha(G)\).
The rescaling \(p=ny\) is a bijection between feasible first-coalition allocations and the probability simplex:
The three quadratic computations are correct:
\[ y^{\mathsf T}Ay=\frac{1}{n^2}p^{\mathsf T}Ap,\qquad \mu^{\mathsf T}Ay=\frac{r}{n^2},\qquad \mu^{\mathsf T}A\mu=\frac{r}{n}. \]
Consequently, the displayed formula for \(\operatorname{OPT}\) follows correctly from the clique lemma. Since \(m\mapsto1-1/m\) is strictly increasing on positive integers, the threshold equivalence with \(\alpha(G)\geq k\) is valid.
There is one domain omission: the threshold contains \(1/k\), but the source problem is stated only with “an integer \(k\).” The proof must explicitly use the standard restriction \(k\geq1\), or otherwise address the \(k=0\) case. This is a routine restriction and does not undermine the reduction.
Let \(F\) be the minimal face containing a global maximizer \(y^\star\). Then \(y^\star\) lies in the relative interior of \(F\). Every direction in the direction space \(L\) permits sufficiently small perturbations in both signs, so the stated first-order condition is valid.
The set \(S\) is an affine space defined by rational linear equations. For \(z,w\in S\), the difference \(\delta=z-w\) lies in \(L\). Both gradients annihilate \(\delta\), and the quadratic identities used to obtain \(\delta^{\mathsf T}Q\delta=0\) and \(f(z)=f(w)\) are correct. Thus \(f\) is constant on \(S\cap F\), and this set contains \(y^\star\).
Because \(S\cap F\) is a nonempty bounded rational polyhedron, it has a rational vertex. The intended determinant-bound argument does imply a polynomial-size rational certificate.
The write-up should, however, state explicitly why the system defining \(S\cap F\) has polynomial encoding length. In particular, it should note that \(F\) is described using the original equality together with active coordinate bounds, and that equations representing annihilation on \(L\) can be chosen with polynomial-bit rational coefficients. Without that sentence, the invocation of determinant bounds leaves one hypothesis implicit. This is an expositional gap, not a need for new mathematics.
⟨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.