Answer: \(\mathrm{NP}\)-complete for every fixed integer \(m>2\).
Proposition 2.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor m > 2, computing the optimum solution for an instance of the Social Coordination Game is NP-Hard even for a fixed value of γ.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) strategies, \(\tau\) complete payoff types with rational masses \(\mu_t\) summing to \(1\), intrinsic utilities \(a_{tk}\), and symmetric nonnegative interaction weights \(\beta_{tu}\), choose \(x_{tk}\ge 0\), with \(\sum_k x_{tk}=1\) for each type \(t\), to maximize \(\Phi(x)=\sum_{t,k}\mu_t a_{tk}x_{tk}+\frac12\sum_{t,u,k}\mu_t\mu_u\beta_{tu}x_{tk}x_{uk}\).
Let \(m>2\). A society is given by its support: the list of its \(\tau\) complete payoff types with positive binary rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
The input specifies nonnegative rational intrinsic utilities \(a_{tk}\), symmetric nonnegative rational interaction weights \(\beta_{tu}\), and a rational threshold \(B\), all encoded in binary. Every type has access to every strategy; interactions are independent of the strategy chosen, and \(\beta_{tt}\) describes interactions between distinct individuals of type \(t\).
An allocation consists of real fractions \(x_{tk}\geq0\) with \(\sum_{k=1}^{m}x_{tk}=1\) for each type; the mass choosing strategy \(k\) is \(\mu_tx_{tk}\).
Define \(\Phi(x)=\sum_{t=1}^{\tau}\sum_{k=1}^{m}\mu_ta_{tk}x_{tk}+\frac12\sum_{t,u=1}^{\tau}\sum_{k=1}^{m}\mu_t\mu_u\beta_{tu}x_{tk}x_{uk}\), including terms with \(t=u\).
The decision problem asks whether a feasible allocation satisfies \(\Phi(x)\geq B\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite agents, maximizing intrinsic utility plus total pairwise coordination benefit is \(\mathrm{NP}\)-hard for \(m>2\), even with fixed relationship imbalance; a polynomial-time \(0.8535\)-approximation is also known. [Sources](https://arxiv.org/abs/1404.4718), [published version](https://ojs.aaai.org/index.php/AAAI/article/download/8789/8648).
No result settling exactly the continuous decision problem above was identified in the literature search.
The continuous decision problem is \(\mathrm{NP}\)-complete for every fixed integer \(m>2\). Hardness holds even when all masses are equal dyadic rationals, all intrinsic utilities and interaction weights are integers, and every diagonal interaction weight is zero.
The key fact is that every feasible allocation can be replaced by an allocation assigning each type entirely to one strategy, without decreasing \(\Phi\).
Call an allocation pure if, for every type \(t\), there is a strategy \(s_t\) such that \(x_{t,s_t}=1\).
Lemma. For every feasible allocation \(x\), there is a pure allocation \(y\) satisfying \(\Phi(y)\geq\Phi(x)\).
Proof. Fix a type \(t\), holding all other types’ allocations constant. Write \(z_k=x_{tk}\). By symmetry of the interaction weights, the objective as a function of this row is
\[ f(z)=C+\sum_{k=1}^{m}c_kz_k+d\sum_{k=1}^{m}z_k^2, \]
where
\[ c_k=\mu_ta_{tk}+\sum_{u\neq t}\mu_t\mu_u\beta_{tu}x_{uk}, \qquad d=\frac12\mu_t^2\beta_{tt}\geq0. \]
Here \(C\) contains all terms independent of this row. Let \(e_k\) denote the \(k\)-th unit vector. Since \(\sum_k z_k=1\),
\[ \sum_k z_kf(e_k)-f(z) =d\left(1-\sum_kz_k^2\right)\geq0. \]
The last inequality follows from \(0\leq z_k\leq1\), which implies \(z_k^2\leq z_k\). Consequently,
\[ f(z)\leq\sum_kz_kf(e_k)\leq\max_k f(e_k). \]
Replacing this row by a maximizing unit vector therefore does not decrease the objective. Performing this replacement for each of the \(\tau\) types produces a pure allocation with the required property. \(\square\)
Thus the continuous threshold question is equivalent to a finite threshold question over the \(m^\tau\) strategy vectors. For a pure allocation,
\[ \Phi(s)= \sum_t\mu_ta_{t,s_t} +\sum_{t<u}\mu_t\mu_u\beta_{tu}\mathbf{1}_{s_t=s_u} +\frac12\sum_t\mu_t^2\beta_{tt}. \]
In particular, the diagonal contribution is constant on pure allocations.
A certificate consists of one strategy \(s_t\in\{1,\ldots,m\}\) for each type. Its length is \(O(\tau\log m)\).
The displayed pure-allocation formula can be evaluated and compared with \(B\) using exact rational arithmetic in polynomial time. By the lemma, every continuous yes-instance has such a certificate. Hence the decision problem belongs to \(\mathrm{NP}\).
We use three-terminal edge multiway cut: given an undirected graph \(G=(V,E)\), three distinct terminals \(s_1,s_2,s_3\), and an integer \(K\), decide whether deleting at most \(K\) edges separates every pair of terminals.
This problem is \(\mathrm{NP}\)-complete even with unit edge weights, by Theorem 3 of Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis, *The Complexity of Multiterminal Cuts*. [Published paper](https://epubs.siam.org/doi/10.1137/S0097539792225297), [author-uploaded text containing Theorem 3](https://www.researchgate.net/publication/220617696_The_Complexity_of_Multiterminal_Cuts).
Equivalently, the source problem asks for a labeling \(\ell:V\to\{1,2,3\}\), with \(\ell(s_i)=i\), such that at most \(K\) edges have differently labeled endpoints:
Fix any integer \(m>2\). Let \(n=|V|\), and let \(N\) be the smallest power of two with \(N\geq n\). Add isolated vertices until there are \(N\) vertices. This does not change the source answer.
Index the padded vertices by \(v\in\{1,\ldots,N\}\), and create one type per vertex. Set
\[ \tau=N,\qquad \mu_v=\frac1N,\qquad q=|E|,\qquad H=q+1. \]
The masses are positive dyadic rationals and sum to one.
Define sets of preferred strategies by
\[ A_{s_i}=\{i\}\quad(i=1,2,3), \qquad A_v=\{1,2,3\}\quad\text{for every nonterminal }v. \]
These sets specify intrinsic rewards; every type still has access to every strategy. Set
\[ c_v=(H+1)v, \qquad a_{vk}=N\left(c_v+H\mathbf{1}_{k\in A_v}\right). \]
Set the symmetric interaction weights to
\[ \beta_{vu}= \begin{cases} N^2,&\{v,u\}\in E,\\ 0,&\text{otherwise}. \end{cases} \]
In particular, \(\beta_{vv}=0\). Finally, define
\[ C_0=\sum_{v=1}^{N}c_v, \qquad B=C_0+NH+q-K. \]
All intrinsic utilities and interaction weights are nonnegative integers.
The constructed types are distinct, as required for a support representation. Indeed, if \(u>v\), then for every strategy \(k\),
\[ a_{uk}-a_{vk} \geq N(c_u-c_v-H) \geq N>0. \]
Thus even their intrinsic utility vectors differ.
For a pure strategy vector \(s\), substitution into the objective gives
\[ \Phi(s)= C_0 +H\sum_{v=1}^{N}\mathbf{1}_{s_v\in A_v} +\sum_{\{v,u\}\in E}\mathbf{1}_{s_v=s_u}. \]
The edge coefficient is exactly one because \(\mu_v\mu_u\beta_{vu}=1\); the factor \(1/2\) cancels the two symmetric ordered terms.
Suppose a vertex \(v\) chooses a strategy outside \(A_v\). Changing its choice to any strategy in \(A_v\) increases the intrinsic contribution by \(H\). Only edges incident to \(v\) can lose coordination reward, and their total number is at most \(q\). Therefore the objective increases by at least
\[ H-q=1. \]
Repeatedly applying this change produces a pure allocation satisfying \(s_v\in A_v\) for every vertex, with no decrease in objective.
Such an allocation uses only strategies \(1,2,3\), and its terminals satisfy \(s_{s_i}=i\). Let
\[ \operatorname{cut}(s) =\left|\{\{v,u\}\in E:s_v\neq s_u\}\right|. \]
For these allocations,
\[ \Phi(s)=C_0+NH+q-\operatorname{cut}(s). \]
If the source instance has a separating cut of size at most \(K\), its equivalent labeling gives a pure allocation with
\[ \Phi(s)=C_0+NH+q-\operatorname{cut}(s)\geq B. \]
Conversely, suppose a feasible continuous allocation satisfies \(\Phi(x)\geq B\). First apply the lemma to obtain a pure allocation with no smaller value. Then correct every choice outside its preferred set, again without decreasing the value. The resulting labeling satisfies
\[ C_0+NH+q-\operatorname{cut}(s)\geq C_0+NH+q-K, \]
so \(\operatorname{cut}(s)\leq K\). Its crossing edges therefore form a valid three-terminal separating cut.
This proves both directions of the reduction.
We have \(n\leq N<2n\). Since the source graph has unit edge weights, every constructed number except the threshold has bit length \(O(\log N)\); the threshold additionally uses the bit length of \(K\). The complete output has length
\[ L=O\left((\tau^2+\tau m)\log\tau+\operatorname{bit}(K)\right). \]
The construction takes polynomial time. Because it works for each fixed \(m>2\), it establishes hardness already for \(m=3\) and for every larger fixed number of strategies.
Exact verification of a pure certificate can be performed in
\[ O\left((\tau^2+\tau m)L^2\right) \]
bit operations using elementary integer arithmetic. To justify the bit bound, let \(D\) be the product of all input denominators. Its bit length is \(O(L)\), and \(2D^3\) is a common denominator for every objective term and for \(B\). All scaled quantities have \(O(L)\) bits.
Precomputing these scaled coefficients and enumerating all pure allocations gives a deterministic exact algorithm with running time
\[ O\left((\tau^2+\tau m+m^\tau\tau^2)L^2\right). \]
Thus fixed support size \(\tau\) permits polynomial time, but arbitrary support size yields an \(\mathrm{NP}\)-complete decision problem, even for fixed \(m=3\). A polynomial-time algorithm for all such inputs would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The output establishes that the stated continuous decision problem is \(\mathrm{NP}\)-complete for every fixed integer \(m>2\). No major or minor mathematical issues were found.
The row objective is expanded correctly. Symmetry of \(\beta_{tu}\) combines the two ordered cross terms into the stated coefficient
\(c_k=\mu_ta_{tk}+\sum_{u\ne t}\mu_t\mu_u\beta_{tu}x_{uk}\).
The diagonal terms contribute exactly \(d\sum_k z_k^2\), with \(d=\frac12\mu_t^2\beta_{tt}\geq0\).
The identity
\(\sum_k z_k f(e_k)-f(z)=d(1-\sum_k z_k^2)\)
is correct: both the constant and linear contributions cancel. Feasibility gives \(z_k\in[0,1]\) and \(\sum_kz_k=1\), so the right-hand side is nonnegative. The weighted average of the vertex values cannot exceed their maximum.
Sequential replacement is valid. Each replacement evaluates the row objective using the current allocations of the other types and preserves or increases the current total objective. Previously replaced rows remain pure. After all \(\tau\) replacements, the allocation is pure. This also covers \(\beta_{tt}=0\), zero intrinsic utilities, and arbitrary real input allocations.
For a pure allocation, \(\sum_kx_{tk}x_{uk}\) equals the indicator that the two types choose the same strategy. For \(t=u\), it equals one. Consequently, the displayed pure-allocation formula, including its constant diagonal contribution, is correct.
The certificate has length \(O(\tau\log m)\), and its entries suffice to evaluate that formula exactly. The rounding lemma supplies a pure certificate for every continuous yes-instance; conversely, every accepted pure certificate is a feasible continuous allocation. Thus the membership argument establishes the required equivalence, without assuming that the original real allocation has a finite encoding.
The cited theorem is applicable. The author-uploaded paper explicitly restates Theorem 3 as \(\mathrm{NP}\)-completeness of three-terminal cut on arbitrary graphs with all edge weights equal to one. Its decision formulation asks whether deleting edges of total weight at most the threshold disconnects every pair of terminals. This matches the source problem used in the reduction. [Author-uploaded paper](https://www.researchgate.net/publication/220617696_The_Complexity_of_Multiterminal_Cuts)
Both directions of the labeling equivalence are correct. Deleting crossing edges prevents any path between differently labeled terminals. Conversely, components after a separating cut contain at most one terminal, and componentwise labeling ensures that every crossing edge lies in the deleted cut.
Three distinct terminals ensure \(n\geq3\). Padding to the next power of two gives \(n\leq N<2n\); isolated vertices do not alter terminal separation.
All \(N\) masses are positive dyadic rationals and sum to one. The intrinsic utilities and interaction weights are nonnegative integers; the interaction matrix is symmetric with zero diagonal. Preferred sets are implemented through rewards, so every strategy remains available to every type.
The distinctness calculation is correct. For \(u>v\), the baseline difference is at least \(H+1\), whereas the preferred-strategy bonus difference is at least \(-H\). Therefore \(a_{uk}-a_{vk}\geq N>0\) for every strategy. The construction genuinely has \(N\) distinct support types.
Multiplying each intrinsic utility by its mass produces \(c_v+H\mathbf{1}_{s_v\in A_v}\). Each unordered graph edge contributes exactly one when coordinated: the coefficient is \(\mu_v\mu_u\beta_{vu}=1\), and the factor \(\frac12\) cancels the two ordered terms.
Correcting an unpreferred choice gains exactly \(H\) intrinsically and loses at most \(q\) edge rewards. Since \(H=q+1\), the total gain is at least one. Corrections do not change whether other vertices choose within their own preferred sets, so the process terminates after at most \(N\) corrections. This argument also excludes extra strategies when \(m>3\).
Once all choices are preferred, all \(N\) intrinsic bonuses are present, the terminals have their prescribed distinct labels, and the coordination count is \(q-\operatorname{cut}(s)\). The displayed objective formula follows exactly.
Both reduction directions are valid. A source labeling with at most \(K\) crossing edges reaches the threshold. A continuous allocation reaching the threshold can first be rounded and then corrected without decreasing its value, yielding a terminal-respecting labeling with at most \(K\) crossing edges. There is no strict-versus-nonstrict inequality error.
For the unit-weight graph, \(q=O(N^2)\); hence \(H\), the baselines, utilities, interaction weights, and the threshold’s constructed offset all have \(O(\log N)\) bits. The threshold additionally depends on the encoding length of \(K\). The stated output-length bound and polynomial construction time are valid.
The exact-arithmetic justification is also sound. Every objective coefficient contains at most three input rational factors. Thus \(2D^3\), where \(D\) is the product of all input denominators, clears all relevant denominators, including that of \(B\). Its bit length and the scaled quantities’ bit lengths are \(O(L)\). Elementary arithmetic therefore supports both stated running-time bounds. Enumeration over \(m^\tau\) pure allocations is polynomial when \(\tau\) is fixed.
No additional lemma, hypothesis, or clarification is needed to make the mathematical argument verifiable.
⟨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.