Answer: —
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAn mwbm belief assignment exists for every non-forbidden graph G. Moreover, this assignment can be computed in polynomial time. We prove the theorem for graphs G = (V, E) with an even number n = |V | of vertices. We then show how to extend it to odd n. Let us first give a few more definitions and fix notation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given τ exposure classes with rational masses \(M_i>0\) summing to \(1\), a symmetric rational interaction matrix \(W\), and rational \(\alpha\le \tfrac12\), decide whether there exist belief masses \(\beta_i\in[0,M_i]\) with \(\sum_i\beta_i<\tfrac12\) and a finite sequence of weakly improving positive-mass opinion transfers that starts truthfully and ends at an equilibrium where at least half the society expresses \(1\). For class \(i\), let \(q_i\) be its fraction expressing \(1\); a type-\((i,b)\) individual choosing \(s\in\{0,1\}\) receives \(U_{ib}(s;q)=\alpha\mathbf{1}[s=b]+(1-\alpha)\sum_j M_jW_{ij}((1-q_j)\mathbf{1}[s=0]+q_j\mathbf{1}[s=1])\). Each transfer moves positive mass of one complete type from its current opinion to the other, which must give at least as much payoff at the state before the transfer; the terminal state must be an equilibrium.
The society is given by its support: a list of \(\tau\ge1\) exposure types with positive binary-rational masses \(M_i\), where \(\sum_iM_i=1\); \(\tau\) is the support size, not the number of possible types. Input also includes a symmetric nonnegative rational matrix \(W\) and rational \(0<\alpha\le\tfrac12\). Diagonal entries represent interaction within an exposure class and may be positive. There are \(m=2\) opinions; let \(L\) be the total input bit length.
Choose real belief masses \(\beta_i\in[0,M_i]\). Complete types \((i,1)\) and \((i,0)\) have fixed masses \(c_{i1}=\beta_i\) and \(c_{i0}=M_i-\beta_i\), respectively; zero-mass complete types are omitted.
A state specifies real masses \(z_{ib}\in[0,c_{ib}]\) expressing \(1\), with the remainder expressing \(0\); set \(q_i=(z_{i0}+z_{i1})/M_i\). The truthful state has \(z_{i0}=0\) and \(z_{i1}=\beta_i\).
For \(b,s\in\{0,1\}\), individual utility is \(U_{ib}(s;q)=\alpha\mathbf1[s=b]+(1-\alpha)\sum_jM_jW_{ij}\bigl((1-q_j)\mathbf1[s=0]+q_j\mathbf1[s=1]\bigr)\). Individuals are nonatomic, so an individual deviation leaves \(q\) fixed.
A move transfers any real mass \(\delta>0\), no larger than the available mass, of one complete type from opinion \(s\) to \(1-s\). It is permitted exactly when \(U_{ib}(1-s;q)\ge U_{ib}(s;q)\) at the state before the move; moves are sequential, ties are permitted, and beliefs remain fixed. An equilibrium requires every opinion occupied by positive mass of a complete type to maximize that type's utility.
Is deciding whether some \(\beta\) with \(\sum_i\beta_i<\tfrac12\) admits a finite permitted sequence from the truthful state to an equilibrium satisfying \(\sum_{i,b}z_{ib}\ge\tfrac12\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite simple unweighted graphs and \(0<\alpha\le\tfrac12\), a suitable minority belief assignment can be computed in polynomial time whenever the graph is outside the forbidden families: complete or edgeless graphs, and, for even \(n\), a clique plus one isolated vertex or graphs with minimum degree at least \(n-2\). [Source](https://cs.au.dk/~iannis/publ/C85-aamas17.pdf).
No result settling this exact nonatomic finite-transfer decision problem was located.
The unrestricted polynomial-time versus $\mathrm{NP}$-hardness question remains unresolved.
The main new result below is a complete polynomial-time characterization when all off-diagonal entries of $W$ are equal. Diagonal entries remain arbitrary and nonnegative. Consequently, this resolves every instance with $\tau\le2$, as well as every diagonal interaction matrix.
I also give self-contained proofs of the general bounded-dynamics result, $\mathrm{NP}$ membership, and the exponential-time algorithm, explicitly including the support constraints identified in the verifier’s report.
Let
$$
x_i=z_{i0}+z_{i1},\qquad
a=\frac{\alpha}{1-\alpha}>0,
\qquad
H_i(x)=\sum_jW_{ij}(2x_j-M_j).
$$
Since $M_jq_j=x_j$, subtraction of the utilities gives
$$
\frac{U_{ib}(1;q)-U_{ib}(0;q)}{1-\alpha}
=
H_i(x)+(2b-1)a.
$$
Write this normalized difference as $D_{ib}(z)$. Thus
$$
D_{i0}(z)=H_i(x)-a,
\qquad
D_{i1}(z)=H_i(x)+a.
$$
An upward transfer, from opinion $0$ to opinion $1$, is permitted exactly when $D_{ib}(z)\ge0$ before the transfer. A downward transfer is permitted exactly when $D_{ib}(z)\le0$.
For a positive-capacity complete type, equilibrium requires
$$
z_{ib}>0\Longrightarrow D_{ib}(z)\ge0,
\qquad
z_{ib}<c_{ib}\Longrightarrow D_{ib}(z)\le0.
$$
All entries of $W$ are nonnegative. Therefore componentwise comparison gives
$$
z\le z'
\Longrightarrow
D_{ib}(z)\le D_{ib}(z')
$$
for every complete type. This remains valid when diagonal entries are positive.
Fix an arbitrary real belief vector $\beta$.
Starting from truth, repeatedly transfer the entire belief-$0$ capacity of any class whose belief-$0$ type is still at opinion $0$ and satisfies $H_i(x)\ge a$. Only positive-capacity types are selected. Each class is selected at most once, so this uses at most $\tau$ transfers. Call the terminal state $U$.
Its belief-$1$ coordinates are $U_{i1}=\beta_i$, while each belief-$0$ coordinate is either zero or its full capacity. Every positive-capacity belief-$0$ type left at zero satisfies
$$
D_{i0}(U)<0.
$$
The inequality is strict because ties permit a further transfer.
Lemma 1. Every state reachable from truth by a finite permitted sequence lies componentwise below $U$.
Proof. Truth lies below $U$. Assume the bound holds before a move.
A downward move preserves the bound. An upward move of a belief-$1$ type cannot exceed $U_{i1}$, which is its capacity. The same holds for a belief-$0$ type whose coordinate in $U$ equals its capacity.
For any remaining positive-capacity belief-$0$ type, monotonicity gives
$$
D_{i0}(z)\le D_{i0}(U)<0.
$$
Its upward move is prohibited. Induction proves the assertion, including arbitrary partial transfers. $\square$
Starting from $U$, now repeatedly remove the entire opinion-$1$ mass of a type with $D_{ib}(z)<0$. These are permitted downward transfers. Every type is removed at most once, so there are at most $2\tau$ such transfers. Let $E$ be the terminal state.
Lemma 2. The state $E$ is an equilibrium and dominates every equilibrium lying below $U$.
Proof. A positive-capacity type remaining at opinion $1$ satisfies $D_{ib}(E)\ge0$ by termination.
A positive-capacity type at opinion $0$ either was already at zero in $U$, or was removed. In the first case its difference was strictly negative at $U$. In the second case its difference was strictly negative when removed. Subsequent downward transfers cannot increase that difference. Thus its difference is strictly negative at $E$. These comparisons prove equilibrium.
Now let $y\le U$ be any equilibrium, allowing partially split types. Track the downward construction with current state $v$, initially $U$. Suppose $y\le v$ and the construction removes type $(i,b)$ because $D_{ib}(v)<0$. If $y_{ib}>0$, equilibrium and monotonicity would imply
$$
0\le D_{ib}(y)\le D_{ib}(v)<0,
$$
a contradiction. Hence $y_{ib}=0$, and the removal preserves $y\le v$. Induction gives $y\le E$. $\square$
It follows that $E$ is the greatest reachable equilibrium. In particular,
$$
\text{a reachable majority equilibrium exists}
\quad\Longleftrightarrow\quad
\sum_{i,b}E_{ib}\ge\frac12.
$$
It is reached using at most $3\tau$ transfers. For rational $\beta$, its construction takes polynomial time: a transfer changing $x_k$ by $\Delta$ updates the fields by
$$
H_i\leftarrow H_i+2W_{ik}\Delta.
$$
There are only polynomially many arithmetic operations, and every state coordinate is zero or a capacity. Consequently, all rational encoding lengths remain polynomial in the input and belief-vector encoding lengths.
Call a belief vector a first-transfer witness if
$$
\sum_j\beta_j<\frac12
$$
and, for some class $i$,
$$
\beta_i<M_i,\qquad H_i(\beta)\ge a.
$$
These conditions mean that a positive mass of belief-$0$ individuals can move upward directly from truth.
Lemma 3. Every yes-instance has a first-transfer witness.
Proof. If no belief-$0$ type ever moves upward, total opinion-$1$ mass cannot exceed the total belief-$1$ capacity, which is strictly below $\tfrac12$.
Consider the first upward transfer of a belief-$0$ type in a successful sequence. Before that transfer, every belief-$0$ coordinate is zero and every belief-$1$ coordinate is at most its capacity. Hence $x\le\beta$. If class $i$ makes this transfer, monotonicity gives
$$
a\le H_i(x)\le H_i(\beta).
$$
Its belief-$0$ capacity is positive, so $\beta_i<M_i$. $\square$
Existence of a first-transfer witness is polynomial-time decidable. For each class $i$, maximize $\varepsilon$ subject to
$$
\begin{aligned}
&0\le\beta_j\le M_j &&\text{for every }j,\\
&\sum_j\beta_j\le\frac12-\varepsilon,\\
&\beta_i\le M_i-\varepsilon,\\
&H_i(\beta)\ge a,\\
&0\le\varepsilon\le1.
\end{aligned}
$$
The optimum is positive exactly when class $i$ has a first-transfer witness. Indeed, a witness supplies a positive common slack for the two strict inequalities, and positive $\varepsilon$ enforces both.
These are rational linear programs of polynomial encoding length. The standard polynomial-time theorem for rational linear programming therefore applies.
For arbitrary symmetric $W$, sufficiency of this test is not proved here. The next section establishes sufficiency for a substantial family.
Assume $\tau\ge2$ and
$$
W_{ij}=w\ge0\qquad\text{whenever }i\ne j.
$$
Define
$$
d_i=W_{ii}-w,
\qquad
h_i=\min(M_i,1-M_i).
$$
Although $d_i$ may be negative, nonnegativity of $W_{ii}$ gives $d_i\ge-w$. Writing $T=\sum_i x_i$, the fields become
$$
H_i(x)=w(2T-1)+d_i(2x_i-M_i).
$$
Theorem 4. For this family, the instance is a yes-instance exactly when at least one of the following conditions holds:
$$ |d_i|h_i>a. $$
$$ M_i>\frac12,\qquad W_{ii}=0,\qquad w(1-M_i)=a. $$
Thus this family is polynomial-time solvable.
By Lemma 3, a yes-instance has a first-transfer witness in some class $i$. Put
$$
B=\sum_j\beta_j<\frac12,\qquad
s=2B-1<0,\qquad
y_i=2\beta_i-M_i.
$$
At truth,
$$
H_i(\beta)=ws+d_i y_i\ge a,
\qquad
\beta_i<M_i.
$$
If $d_i=0$, then $H_i(\beta)=ws\le0$, which is impossible.
If $d_i>0$, the two strict bounds $\beta_i<M_i$ and $\beta_i<\tfrac12$ imply
$$
y_i<M_i,\qquad y_i<1-M_i.
$$
Consequently,
$$
a\le H_i(\beta)<d_i h_i,
$$
which gives condition 1.
Suppose instead $d_i=-k_i<0$. Here $k_i>0$ and $w\ge k_i$, so $w>0$.
If $M_i\le\tfrac12$, then $y_i\ge-M_i$ and
$$
H_i(\beta)=ws-k_i y_i
\le ws+k_iM_i
<k_iM_i=k_i h_i.
$$
Again condition 1 follows.
If $M_i>\tfrac12$, put $C_i=1-M_i$. Since the other classes have total capacity $C_i$,
$$
\beta_i\ge B-C_i,
\qquad
y_i\ge s-C_i.
$$
Therefore
$$
H_i(\beta)
\le (w-k_i)s+k_iC_i
=
W_{ii}s+k_iC_i.
$$
If $W_{ii}>0$, this is strictly below $k_iC_i$, so condition 1 follows. If $W_{ii}=0$, it gives $k_iC_i\ge a$. A strict inequality gives condition 1; equality gives condition 2 because $k_i=w$.
This proves necessity.
The sufficiency constructions use the following observation.
Lemma 5. Suppose a reachable state has all belief-$1$ types entirely at opinion $1$, and every positive-capacity type currently at opinion $1$ weakly prefers that opinion. Suppose also every belief-$0$ type is entirely at one opinion.
Repeatedly transferring the full capacity of an available belief-$0$ type upward reaches an equilibrium, and total opinion-$1$ mass never decreases.
Proof. Every transfer is permitted by its pre-transfer comparison. Fields only increase, so every previously occupied opinion $1$ remains utility maximizing. Each transferred type thereafter weakly prefers opinion $1$.
At termination, every positive-capacity belief-$0$ type left at opinion $0$ has $H_i<a$; otherwise another transfer would be available. Thus every occupied opinion maximizes utility. There are at most $\tau$ transfers. $\square$
Suppose $d_i=-k_i<0$ and condition 1 holds for class $i$. Write
$$
p=M_i,\qquad C=1-p.
$$
Here $k_i p>a$. Choose a sufficiently small rational $\varepsilon>0$ satisfying
$$
\varepsilon<\frac p2,
\qquad
k_i p-2w\varepsilon\ge a.
$$
Set
$$
\beta_i=0,\qquad
\beta_j=M_j\frac{\tfrac12-\varepsilon}{C}
\quad(j\ne i).
$$
Because $C\ge\tfrac12$, these beliefs satisfy the capacity bounds. Their total is $\tfrac12-\varepsilon$.
At truth,
$$
H_i(\beta)=k_i p-2w\varepsilon\ge a.
$$
Transfer the entire mass $p$ of class $i$ upward. Afterwards,
$$
T=\frac12-\varepsilon+p>\frac12.
$$
For every other class,
$$
2x_j-M_j=M_j\frac{p-2\varepsilon}{C}.
$$
This quantity lies between zero and $p-2\varepsilon$. Using $d_j\ge-w$ gives
$$
\begin{aligned}
H_j(x)
&=2w(p-\varepsilon)
+d_jM_j\frac{p-2\varepsilon}{C}\\
&\ge2w(p-\varepsilon)-w(p-2\varepsilon)\\
&=wp>0.
\end{aligned}
$$
Thus every belief-$1$ type weakly prefers opinion $1$. The transferred belief-$0$ type also does, because its field cannot decrease during the transfer. Lemma 5 supplies a majority equilibrium.
Now $k_iC>a$. Choose sufficiently small rational $\varepsilon>0$ and set
$$
\beta_j=M_j\quad(j\ne i),
\qquad
\beta_i=p-\frac12-\varepsilon.
$$
Require $\varepsilon<p-\tfrac12$, ensuring $\beta_i\ge0$. The total belief mass is $\tfrac12-\varepsilon$.
At truth,
$$
H_i(\beta)=k_iC-2W_{ii}\varepsilon.
$$
For sufficiently small $\varepsilon$, this is at least $a$. Transfer the belief-$0$ capacity of class $i$ upward.
The resulting state has everyone expressing opinion $1$. The belief-$0$ type of class $i$ weakly prefers opinion $1$ by monotonicity. Every other class contains only belief-$1$ individuals, whose field at the all-$1$ state is nonnegative. Thus this is an equilibrium.
Suppose condition 2 holds. Give everyone outside class $i$ belief $1$ and everyone in class $i$ belief $0$:
$$
\beta_i=0,\qquad \beta_j=M_j\quad(j\ne i).
$$
Its total belief-$1$ mass is $1-M_i<\tfrac12$. Since $W_{ii}=0$,
$$
H_i(\beta)=w(1-M_i)=a.
$$
A tied full transfer of class $i$ is permitted. Afterwards everyone expresses opinion $1$.
The class-$i$ belief-$0$ type remains indifferent because its field is still $a$. All other types have belief $1$ and nonnegative fields. The resulting state is an equilibrium.
We may assume that no negative-$d_j$ class satisfies either sufficient condition; those cases are already resolved. Consequently, every class with $d_j<0$ satisfies
$$
|d_j|\min(M_j,1-M_j)\le a.
$$
For any strict-minority belief vector, $\beta_j\le M_j$ and $\beta_j<\tfrac12$. Hence
$$
d_j(2\beta_j-M_j)\ge-a
\qquad\text{whenever }d_j<0.
$$
For positive $d_i$, define
$$
t_i=\frac{M_i+a/d_i}{2}.
$$
Condition 1 is equivalent to
$$
t_i<M_i,\qquad t_i<\frac12.
$$
Call such a positive-$d_i$ class eligible.
Suppose $M_i\ge\tfrac12$ and class $i$ is eligible. Then
$$
d_i(1-M_i)>a.
$$
Choose small rational $\varepsilon>0$ and set
$$
\beta_i=\frac12-\varepsilon,\qquad
\beta_j=0\quad(j\ne i).
$$
At truth,
$$
H_i(\beta)
=
d_i(1-M_i)-2(d_i+w)\varepsilon>a
$$
for sufficiently small $\varepsilon$.
Transfer the belief-$0$ capacity of class $i$ upward. Class $i$ now contributes mass $M_i\ge\tfrac12$. Its occupied types prefer opinion $1$, and there are no belief-$1$ types elsewhere. Lemma 5 completes the state to a majority equilibrium.
Choose an eligible class $i$ minimizing $t_i$. Put
$$
t=t_i,\qquad
r=\frac12-t,\qquad
\ell_i=M_i-t>0.
$$
For each $j\ne i$, define
$$
\ell_j=
\begin{cases}
\dfrac{M_j-a/d_j}{2},
&d_j>0\text{ and }d_jM_j>a,\\[6pt]
0,&\text{otherwise}.
\end{cases}
$$
In every case,
$$
0\le\ell_j<\frac{M_j}{2}.
$$
We first show that
$$
\ell_j<r\qquad(j\ne i).
$$
Suppose otherwise. Then $\ell_j>0$, and
$$
t_j=M_j-\ell_j\le M_j-r<M_j.
$$
If $M_j<\tfrac12$, then
$$
t_j<M_j-r<\frac12-r=t_i.
$$
Thus $j$ is eligible and contradicts the minimal choice of $t_i$.
If $M_j\ge\tfrac12$, using $M_j\le1-M_i$ gives
$$
t_j\le M_j-r
\le1-M_i-r
=\frac12-\ell_i<\frac12.
$$
Thus $j$ would be an eligible class of mass at least $\tfrac12$, contrary to the current case.
Next choose a nonempty subset $J$ of classes other than $i$ such that
$$
\sum_{j\in J}M_j\ge r,
\qquad
\sum_{j\in J}\ell_j<r.
$$
Such a subset exists. If some $M_j\ge r$, use that singleton, since $\ell_j<r$. Otherwise all those masses are below $r$. Their total is $1-M_i>\tfrac12>r$, so choose an inclusion-minimal subset with total mass $S\ge r$. Minimality gives $S<2r$, and therefore
$$
\sum_{j\in J}\ell_j<\frac S2<r.
$$
Let
$$
S=\sum_{j\in J}M_j,\qquad
R=\sum_{j\in J}\ell_j,\qquad
\lambda=\frac{r-R}{S-R}.
$$
Then $0<\lambda\le1$. Define a balanced belief vector $\gamma$ by
$$
\gamma_i=t,\qquad
\gamma_j=\ell_j+\lambda(M_j-\ell_j)\quad(j\in J),
$$
and $\gamma_j=0$ otherwise. It satisfies
$$
\sum_j\gamma_j=\frac12,
\qquad
\gamma_j>\ell_j\quad(j\in J).
$$
Choose $k\in J$, set
$$
A=1+\frac{w}{d_i},
$$
and perturb the beliefs by
$$
\beta_i=t+A\varepsilon,\qquad
\beta_k=\gamma_k-(A+1)\varepsilon,
$$
leaving all other coordinates unchanged.
For sufficiently small rational $\varepsilon>0$, these beliefs satisfy
$$
0\le\beta_j\le M_j,\qquad
\beta_i<M_i,\qquad
\beta_k>\ell_k,
\qquad
\sum_j\beta_j=\frac12-\varepsilon.
$$
At truth,
$$
\begin{aligned}
H_i(\beta)
&=-2w\varepsilon+d_i(2t+2A\varepsilon-M_i)\\
&=a+2d_i\varepsilon>a.
\end{aligned}
$$
Thus the belief-$0$ capacity of class $i$ can be transferred upward.
After that transfer, total opinion-$1$ mass is
$$
T=\frac12+\ell_i-(A+1)\varepsilon>\frac12
$$
when $\varepsilon$ is sufficiently small.
We verify that every belief-$1$ type prefers opinion $1$ at this state.
For a selected class with $d_j>0$, the inequality $\beta_j>\ell_j$ implies
$$
d_j(2\beta_j-M_j)>-a.
$$
This also holds when $\ell_j=0$: positive belief mass gives
$$
d_j(2\beta_j-M_j)>-d_jM_j\ge-a.
$$
For $d_j=0$, the diagonal contribution is zero. For $d_j<0$, the previously proved minority bound gives
$$
d_j(2\beta_j-M_j)\ge-a.
$$
Since $T>\tfrac12$, adding $w(2T-1)\ge0$ preserves all required inequalities. Classes outside $J\cup\{i\}$ have no belief-$1$ mass. Class $i$ has field at least $a$ by monotonicity.
The transferred belief-$0$ type likewise prefers opinion $1$. Lemma 5 therefore completes this state to a majority equilibrium.
This finishes the proof of Theorem 4.
The criterion involves only rational comparisons and arithmetic of polynomial encoding length. Recognizing a common off-diagonal entry also takes polynomial time.
All sufficiently small parameters used above can be chosen rationally: each construction imposes finitely many strict affine inequalities that hold for all sufficiently small positive parameters.
For a diagonal matrix, take $w=0$. The equality exception disappears, giving the particularly simple characterization
$$
\boxed{
\text{yes}
\quad\Longleftrightarrow\quad
\exists i:\;
W_{ii}\min(M_i,1-M_i)>
\frac{\alpha}{1-\alpha}.
}
$$
For a constant matrix, every $d_i=0$, so the answer is always no.
Every symmetric matrix with $\tau=2$ has a common off-diagonal entry, namely $w=W_{12}$. Thus Theorem 4 resolves all two-class instances.
For $\tau=1$, necessarily $M_1=1$. At any truthful strict-minority state,
$$
H_1(\beta)=W_{11}(2\beta_1-1)\le0<a.
$$
Lemma 3 therefore excludes a yes-instance. Hence all instances with $\tau\le2$ are polynomial-time decidable.
The following establishes the general upper bounds without assuming a common off-diagonal weight.
A pattern specifies:
$$ \beta_i=0,\qquad 0<\beta_i<M_i,\qquad \beta_i=M_i. $$
$$ y_{i0}=s_{i0}(M_i-\beta_i), \qquad y_{i1}=s_{i1}\beta_i. $$
Every declared support alternative is imposed as a constraint. In particular, an interior declaration imposes both
$$
\beta_i>0,\qquad M_i-\beta_i>0.
$$
These constraints determine exactly which complete types have positive capacity.
Before a listed class is transferred, its aggregate coordinates are $M_j$ for previously listed classes and $\beta_j$ for all others. Impose
$$
M_i-\beta_i>0,\qquad H_i(x)\ge a
$$
for each listed transfer. These are affine inequalities in $\beta$. Let $P$ be the resulting state.
Require
$$
y\le P.
$$
For every positive-capacity type, impose
$$
D_{ib}(y)\ge0\quad\text{if }s_{ib}=1,
\qquad
D_{ib}(y)\le0\quad\text{if }s_{ib}=0.
$$
Finally impose
$$
\sum_i\beta_i<\frac12,\qquad
\sum_{i,b}y_{ib}\ge\frac12.
$$
All constraints are linear because capacities and state coordinates are affine functions of $\beta$.
A feasible pattern gives permitted transfers reaching $P$. By Lemma 1,
$$
P\le U.
$$
Its candidate $y$ is an equilibrium below $P$, so Lemma 2 gives
$$
y\le E.
$$
Thus $E$ is a reachable majority equilibrium.
Conversely, for any yes-instance, take its upward closure $U$ and greatest reachable equilibrium $E$. The construction in Section 2 provides an upward list, while every complete type in $E$ is entirely at one opinion. These choices give a feasible pattern.
Therefore pattern feasibility is equivalent to the original existential problem.
For a fixed pattern, introduce $0\le\varepsilon\le1$. Replace every strict inequality $f(\beta)>0$ by
$$
f(\beta)\ge\varepsilon,
$$
and maximize $\varepsilon$.
This includes all interior-support inequalities, positive transferred capacities, and the strict minority condition.
The original system is feasible exactly when the optimum is positive. A strictly feasible point has a positive minimum slack across the finitely many strict inequalities; conversely, positive common slack enforces all of them.
The program has polynomially many rational coefficients of polynomial encoding length. Its feasible region is closed and bounded. If its optimum is positive, an optimal vertex exists. Such a vertex is determined by a full-rank rational linear system of polynomial dimension. Clearing denominators and applying determinant bounds in Cramer’s rule gives polynomial encoding length.
Consequently, every yes-instance has a polynomial-length rational belief vector. Given that vector, a verifier checks the strict minority condition and runs the fixed-belief algorithm of Section 2. Hence the unrestricted problem belongs to $\mathrm{NP}$.
There are $3^\tau$ support choices and $4^\tau$ terminal masks. The number of ordered lists of distinct classes is
$$
\sum_{k=0}^{\tau}\frac{\tau!}{(\tau-k)!}
=
\tau!\sum_{r=0}^{\tau}\frac1{r!}
\le e\,\tau!.
$$
Enumerating the patterns and solving their linear programs gives the exact running-time bound
$$
2^{O(\tau\log(\tau+1))}\operatorname{poly}(L).
$$
The new characterization settles common-off-diagonal matrices, including all instances with at most two exposure classes. It does not settle arbitrary symmetric matrices.
A concrete possible route to a polynomial-time solution is to prove that the first-transfer test in Section 3 is sufficient for every symmetric nonnegative $W$. Theorem 4 proves this implication for the common-off-diagonal family. No proof or counterexample for the general implication is established here.
The [cited paper](https://cs.au.dk/~iannis/publ/C85-aamas17.pdf) studies discrete preference games with individual players. No theorem from it is used to infer the complexity of the present real-mass model.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial partial results, but it does not settle the unrestricted polynomial-time versus $\mathrm{NP}$-hardness question. The bounded-dynamics argument, general $\mathrm{NP}$ upper bound, exponential-time algorithm, and common-off-diagonal characterization are sound in substance. I found one minor inequality error in the characterization proof; it does not affect its conclusion.
The prover explicitly says that the unrestricted problem remains unresolved. This accurately describes what the write-up establishes.
The results actually proved are:
These are genuine results about the assigned model. They do not establish either a polynomial-time algorithm or $\mathrm{NP}$-hardness for arbitrary symmetric nonnegative $W$. Consequently, the overall status is partial.
The utility subtraction is correct:
$$
\frac{U_{ib}(1;q)-U_{ib}(0;q)}{1-\alpha}
=
\sum_jW_{ij}(2x_j-M_j)+(2b-1)a.
$$
The normalization is legitimate because $0<\alpha\le\tfrac12$, so $1-\alpha>0$ and $a>0$.
The upward and downward permission inequalities correctly incorporate ties and use the state before the transfer.
The equilibrium implications are also correct, including partially split positive-capacity types. A split type must satisfy both inequalities, hence have zero utility difference.
Componentwise monotonicity follows directly from $W_{ij}\ge0$. Positive diagonal entries cause no difficulty: they contribute to the field change after a transfer, while the permission comparison remains evaluated before that transfer.
Assessment: Correct.
The upward construction leaves every complete type entirely at one opinion. Every positive-capacity belief-$0$ type remaining at zero has strictly negative difference at termination, because equality would permit its full transfer.
The induction in Lemma 1 covers every permitted move:
This argument includes arbitrary partial transfers and arbitrary finite sequences.
Assessment: Correct.
The downward construction only decreases fields. Thus a type removed with negative difference continues to prefer opinion $0$ strictly.
A positive-capacity type initially at zero in $U$ must be an untransferred belief-$0$ type; its difference is strictly negative there. Belief-$1$ types of positive capacity start fully at opinion $1$. This verifies the implicit classification used in the equilibrium proof.
The domination argument correctly allows partially split candidate equilibria. If a removed type had positive opinion-$1$ mass in such an equilibrium, equilibrium and monotonicity would give the stated contradiction.
The resulting $E$ is reachable. Every reachable equilibrium lies below $U$ by Lemma 1 and therefore below $E$ by Lemma 2. Hence “greatest reachable equilibrium” is justified.
The transfer bound and rational arithmetic argument are valid. All states in the construction have coordinates equal to zero or capacities, so repeated field updates do not introduce uncontrolled encoding growth.
Assessment: Correct.
Lemma 3 correctly identifies the first upward belief-$0$ transfer. Before that transfer, all belief-$0$ coordinates are zero, and belief-$1$ coordinates are bounded by their capacities. Therefore $x\le\beta$, giving the necessary field inequality.
The strict capacity requirement is necessary and included.
The common-slack linear program correctly represents the two strict inequalities. A witness supplies positive slack for both, and a feasible point with positive $\varepsilon$ supplies a witness. All coefficients have polynomial rational encoding length.
The application of polynomial-time rational linear programming has the required hypotheses: finitely many rational linear constraints, polynomial dimension and encoding length, and a bounded objective.
Assessment: Correct as a necessary test. General sufficiency remains unproved, as the output acknowledges.
The field decomposition is correct:
$$
H_i(x)=w(2T-1)+d_i(2x_i-M_i).
$$
All sign cases are covered:
$$
H_i(\beta)\le W_{ii}s+k_i(1-M_i).
$$
The distinction between $W_{ii}>0$ and $W_{ii}=0$ correctly produces the strict criterion or the equality exception.
Assessment: Correct.
The hypotheses ensure that every currently occupied opinion $1$ maximizes utility. Upward transfers preserve this property by monotonicity. At termination, all remaining positive-capacity belief-$0$ types at zero strictly prefer zero.
The absence of belief-$1$ mass at zero is explicitly assumed, so no equilibrium condition is omitted.
Assessment: Correct.
For $M_i\le\tfrac12$, the proportional allocation respects capacities, and the field calculation after transferring class $i$ is correct. In particular, the bound using $d_j\ge-w$ remains valid because the multiplied quantity is nonnegative.
For $M_i>\tfrac12$, the proposed beliefs are feasible for sufficiently small positive $\varepsilon$, and the computed initial field is correct. After the transfer, everyone expresses opinion $1$. The transferred type retains its preference by monotonicity; other occupied types have belief $1$ and nonnegative fields.
The equality construction correctly uses a tied transfer and the zero diagonal to keep the transferred class’s field equal to $a$.
Assessment: Correct.
The bound for negative-$d_j$ classes correctly follows from
$$
2\beta_j-M_j\le\min(M_j,1-M_j).
$$
Multiplication by negative $d_j$ reverses the inequality as required.
The eligibility conditions are equivalent to the stated strict criterion. The construction for an eligible class of mass at least $\tfrac12$ is valid.
For the remaining construction, the subset argument, balanced allocation, perturbation, triggering field calculation, and final majority calculation all check out. The preference verification covers every positive belief-$1$ type and the transferred belief-$0$ type.
There is one minor error:
Minor issue — Section 4.4, proof that $\ell_j<r$.
Under the contrary assumption $\ell_j\ge r$, the text writes
$$
t_j<M_j-r.
$$
The displayed definitions only justify
$$
t_j\le M_j-r.
$$
Equality is not excluded at that step. The subsequent comparison with $t_i$ is strict, so the contradiction and final conclusion survive this error.
Minimum clarification: Replace that first strict inequality by a weak inequality.
Assessment: Sound in substance, with this minor correction.
The decision criterion requires only polynomially many rational operations and comparisons. The rational small-parameter assertions are justified by the finite strict affine conditions and positive margins in the constructions.
The diagonal and constant-matrix specializations are correct. The separate argument for $\tau=1$ correctly handles the case outside Theorem 4’s stated domain. Every symmetric two-class matrix meets the common-off-diagonal hypothesis.
Assessment: Correct.
The pattern includes enough support information to determine exactly which equilibrium inequalities apply. All intermediate states and terminal coordinates are affine in $\beta$, so the feasibility systems are linear.
Both directions of equivalence are valid:
The common-slack transformation correctly handles every strict constraint. The transformed feasible region is closed and bounded. A positive optimum has an optimal vertex, and the stated rational linear-system argument supplies polynomial encoding length. This establishes polynomial-length belief certificates even when the original successful beliefs were real.
Verification by the fixed-belief algorithm is polynomial time. The pattern count and resulting bound
$$
2^{O(\tau\log(\tau+1))}\operatorname{poly}(L)
$$
are correct.
Assessment: Correct. These upper bounds leave the requested complexity dichotomy unresolved.
The current write-up needs only the weak-inequality correction identified above to make its proved partial results fully consistent.
Resolving the original task requires an additional general complexity result. The output supplies neither general first-transfer sufficiency nor a hardness reduction, and explicitly acknowledges both limitations. This is an outstanding research step, not an omitted routine justification.
⟨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.