d4-conf-atal-2020-0214 (d4-conf-atal-2020-0214)

Given \(k>3\) locations, rational masses \(\mu_t\), and a symmetric nonpositive influence kernel \(W\) with \(W_{tt}=0\), let \(x_{tj}\ge 0\) satisfy \(\sum_j x_{tj}=\mu_t\). Define \(u_t(j;x)=\sum_s W_{st}x_{sj}\); call \(x\) a population PSNE when \(x_{tj}>0\) only if \(j\) maximizes \(u_t(j;x)\). Is there a population PSNE with normalized welfare \(\sum_{t,j}x_{tj}u_t(j;x)\ge 0\)?

A society is given by its support: a list of \(\tau\ge1\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=k>3\) locations, all available to every type, each with capacity \(1\). The input includes a binary rational matrix \(W\in\mathbb{Q}^{\tau\times\tau}\) satisfying \(W_{st}=W_{ts}\le0\) and \(W_{tt}=0\). There are no location bonuses or effects from neighboring locations.
An allocation is a real matrix \(x\in\mathbb{R}_{\ge0}^{\tau\times m}\) with \(\sum_{j=1}^{m}x_{tj}=\mu_t\). Types may split their mass among locations. Define \(u_t(j;x)=\sum_{s=1}^{\tau}W_{st}x_{sj}\).
A population PSNE satisfies \(x_{tj}>0\Longrightarrow u_t(j;x)\ge u_t(\ell;x)\) for every \(\ell\in\{1,\ldots,m\}\). Individuals are nonatomic, so deviations leave \(x\) unchanged; ties permit occupation of any maximizing location. Define normalized welfare \(\operatorname{SW}(x)=\sum_{t=1}^{\tau}\sum_{j=1}^{m}x_{tj}u_t(j;x)\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).

Is deciding whether there exists a population PSNE \(x\) with \(\operatorname{SW}(x)\ge0\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For finite agents, maximizing welfare over PSNE is NP-hard with symmetric negative influence edges, zero location bonuses, no location effect, nonbinding capacities, and more than three locations; the zero-welfare threshold decision problem is also NP-hard ([Chan, Irfan, and Than, 2020](https://www.ifaamas.org/Proceedings/aamas2020/pdfs/p240.pdf)).
No complexity classification for exactly the population problem defined above was located in the literature search.

Classification

The decision problem is \(\mathrm{NP}\)-complete, even for every fixed number of locations \(m>3\), equal type masses, and influence entries restricted to \(\{0,-1\}\).

The proof applies directly to the population model: allowing a type to split its mass does not change feasibility at the zero-welfare threshold.

1. Zero welfare is equivalent to separation of negatively interacting types

Define the finite simple graph \(G_W=(V,E)\) by
\(V=\{1,\ldots,\tau\}\) and
\(E=\{\{s,t\}:s<t,\ W_{st}<0\}\).

For any feasible allocation, symmetry and the zero diagonal give
\[ \operatorname{SW}(x) =\sum_{j=1}^{m}\sum_{s,t=1}^{\tau}W_{st}x_{sj}x_{tj} =2\sum_{\{s,t\}\in E}W_{st}\sum_{j=1}^{m}x_{sj}x_{tj}. \]

Every summand is nonpositive. Consequently, \(\operatorname{SW}(x)\le0\), and
\[ \operatorname{SW}(x)\ge0 \quad\Longleftrightarrow\quad \operatorname{SW}(x)=0 \quad\Longleftrightarrow\quad x_{sj}x_{tj}=0 \text{ for every }\{s,t\}\in E\text{ and every }j. \]

Indeed, a finite sum of nonpositive terms is zero exactly when every term is zero. For an edge, \(W_{st}<0\), so its term vanishes exactly when the sum of the nonnegative products \(x_{sj}x_{tj}\) vanishes.

For each type, define its occupied-location set
\(S_t=\{j:x_{tj}>0\}\).
Since \(\mu_t>0\) and \(\sum_jx_{tj}=\mu_t\), every \(S_t\) is nonempty. Thus zero welfare is equivalent to
\[ S_s\cap S_t=\varnothing \qquad\text{for every }\{s,t\}\in E. \]

Capacities impose no additional restriction: at every location,
\(\sum_t x_{tj}\le\sum_{t,j}x_{tj}=1\).

2. Every zero-welfare allocation is a population PSNE

Suppose \(x\) has zero welfare, and fix a type \(t\) occupying location \(j\).

For every type \(s\), either \(W_{st}=0\), or \(W_{st}<0\). In the latter case, the separation property and \(x_{tj}>0\) imply \(x_{sj}=0\). Therefore
\[ u_t(j;x)=\sum_sW_{st}x_{sj}=0. \]

At every location \(\ell\), nonpositive influences and nonnegative masses imply
\(u_t(\ell;x)\le0\). Hence
\(u_t(j;x)\ge u_t(\ell;x)\) for every \(\ell\), exactly as required by the population PSNE definition.

Thus, at this threshold, the equilibrium condition follows automatically from welfare feasibility.

3. Exact equivalence with graph coloring

Proposition. There exists a population PSNE with \(\operatorname{SW}(x)\ge0\) if and only if \(G_W\) admits a proper coloring with at most \(m\) colors.

Proof, forward direction. Such an equilibrium has zero welfare by Section 1. Choose any \(c(t)\in S_t\) for each type. Every edge has disjoint occupied-location sets, so its endpoints receive different colors. Therefore \(c:V\to\{1,\ldots,m\}\) is a proper coloring.

Proof, reverse direction. Given a proper coloring \(c\), place all mass of each type at its color:
\[ x_{tj}= \begin{cases} \mu_t,&j=c(t),\\ 0,&j\ne c(t). \end{cases} \]

This allocation satisfies the mass constraints and capacities. Adjacent types occupy different locations, so Section 1 gives zero welfare. Section 2 then proves that it is a population PSNE. \(\square\)

In particular, every yes-instance has a rational equilibrium in which each type occupies just one location.

4. NP-hardness for every fixed \(m>3\)

We use the standard theorem that deciding whether a finite simple graph is properly colorable with at most three colors is \(\mathrm{NP}\)-complete. See [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975(76)90059-1).

Fix any integer \(m>3\). Given a three-colorability instance \(H\) on \(n\ge1\) vertices, construct \(G\) by:

• Adding a clique on \(m-3\) new vertices.
• Joining every new vertex to every vertex of \(H\).

Then \(G\) is \(m\)-colorable if and only if \(H\) is three-colorable. To verify both directions:

• A three-coloring of \(H\) extends by assigning distinct additional colors to the new clique.
• In any \(m\)-coloring of \(G\), the clique uses \(m-3\) distinct colors. None of these colors can occur on \(H\), because every vertex of \(H\) is adjacent to every clique vertex. Thus \(H\) uses at most three colors.

Construct the population instance with one type per vertex of \(G\), so \(\tau=n+m-3\), and set
\[ \mu_t=\frac1{\tau}, \qquad W_{st}= \begin{cases} -1,&\{s,t\}\in E(G),\\ 0,&\text{otherwise}. \end{cases} \]

These masses are positive binary rationals and sum to one. The matrix is symmetric, nonpositive, and has zero diagonal. All locations have capacity one and are available to every type.

By Section 3, this population instance is a yes-instance exactly when \(G\) is \(m\)-colorable, hence exactly when \(H\) is three-colorable.

The output length is \(L=O(\tau^2+\tau\log(\tau+1))\) for fixed \(m\). An explicit construction takes \(O((n+m)^2\log(n+m+1))\) bit operations, which is polynomial in the source input length when \(m\) is fixed. This proves \(\mathrm{NP}\)-hardness for every fixed \(m>3\).

5. NP membership and running times

A certificate consists of one color \(c(t)\in\{1,\ldots,m\}\) per type, requiring \(O(\tau\log(m+1))\) bits.

The verifier checks the color ranges and verifies \(c(s)\ne c(t)\) whenever \(W_{st}<0\). Reading the input and checking all pairs takes
\(O(L+\tau^2\log(m+1))\) bit operations under the usual bit-cost random-access model. Section 3 proves that this certificate is equivalent to existence of the requested equilibrium; no certificate involving arbitrary real numbers is needed.

For completeness, a direct deterministic algorithm enumerates all color assignments in time
\(O(L+m^\tau\tau^2\log(m+1))\).
If \(m\ge\tau\), assigning a distinct location to every type immediately yields a yes-answer.

Therefore the target decision problem is \(\mathrm{NP}\)-complete, both when \(m>3\) is part of the input and when any such \(m\) is fixed. A polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s output resolves the task correctly. The decision problem is \(\mathrm{NP}\)-complete, including for every fixed \(m>3\). I found no major or minor mathematical gaps.

• Welfare expansion and its sign. Substituting the utility definition gives

\[ \operatorname{SW}(x)=\sum_{j=1}^{m}\sum_{s,t=1}^{\tau}W_{st}x_{sj}x_{tj}. \]
Symmetry combines the two ordered terms for each distinct pair, and the zero diagonal removes self-interaction terms. The displayed factor of \(2\) is correct. Every remaining term is nonpositive because \(W_{st}<0\) on edges and allocation entries are nonnegative.

• Zero welfare and separation. The inference from zero total welfare to zero contribution from every edge is valid: the sum is finite and all contributions are nonpositive. For an edge, its strictly negative weight makes its contribution zero precisely when every nonnegative product \(x_{sj}x_{tj}\) is zero. Thus the equivalence with disjoint occupied-location sets is exact. Positive type masses ensure that each occupied-location set is nonempty; this is essential to the subsequent color selection.

• Capacity feasibility. The capacity calculation is correct. Every location’s total mass is at most the total society mass, which is \(1\). Consequently, all allocations satisfying nonnegativity and the type mass constraints also satisfy the stated capacities, including allocations that exactly fill a location.

• The equilibrium implication. For every occupied location of a type, separation eliminates every strictly negative interaction with that type. All other interaction coefficients are zero, so its utility there equals zero. Its utility at every alternative location is nonpositive. This proves precisely the required weak maximizing inequality for every occupied location. The argument accommodates split types, ties, and isolated vertices, and uses the stipulated nonatomic deviation rule correctly.

• Equivalence with graph coloring. Both directions are rigorous.

• From a qualifying equilibrium, nonpositive welfare forces zero welfare. Selecting one occupied location per type produces a proper coloring because adjacent types have disjoint occupied-location sets.
• From a proper coloring, assigning each type’s entire mass to its color satisfies the mass and capacity constraints. Separation gives zero welfare, and the preceding equilibrium argument applies.

No integrality assumption about arbitrary population allocations is introduced. The assertion that every yes-instance has an unsplit rational equilibrium follows from this construction.

• NP-hardness reduction. The invoked theorem is correctly stated: deciding proper three-colorability of finite simple graphs is \(\mathrm{NP}\)-complete. The cited [Garey–Johnson–Stockmeyer paper](https://www.sciencedirect.com/science/article/pii/0304397576900591) supports this source problem.

For fixed \(m>3\), the added clique requires \(m-3\) distinct colors, and its adjacency to every original vertex excludes those colors from the original graph. Conversely, a three-coloring extends using distinct additional colors for the clique. Both implications hold even when the original graph uses fewer than three colors.

The resulting population instance satisfies every required hypothesis: positive normalized rational masses, symmetric nonpositive influences, zero diagonal, unrestricted location availability, and capacity \(1\). The equal masses \(1/\tau\) have binary numerator-and-denominator encodings of length \(O(\log(\tau+1))\). The stated output-length and construction-time bounds are valid upper bounds. For fixed \(m\), the reduction is polynomial in the explicit source graph’s input length. The restriction to nonempty source graphs does not affect hardness.

• NP membership and algorithmic bounds. A coloring is a sufficient certificate by the established equivalence, so no representation of arbitrary real allocations is required. Its length \(O(\tau\log(m+1))\) is polynomial in the input length, including when \(m\) is binary encoded. Checking color ranges and every negative matrix entry verifies exactly the necessary condition. The stated verification bound is valid under the specified random-access bit-cost model.

The exhaustive-search bound is also valid: there are \(m^\tau\) assignments, each requiring at most the stated pairwise checking cost after input processing. When \(m\ge\tau\), distinct locations for all types indeed yield a yes-instance.

• Final classification. Fixed-\(m\) hardness implies hardness when \(m\) is part of the input, and the certificate argument establishes membership in \(\mathrm{NP}\) in both settings. The final implication concerning \(\mathrm{P}=\mathrm{NP}\) is correct.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩