Answer: The feasibility problem is in \(\mathrm P\): every promised instance admits an intervention with \(m\tau\) cohorts that reaches a stable profile with strict global winner \(\omega\) after one simultaneous update.
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet d be a natural number, z=max(6(m- 1),2(max∆+d+1)), and n′=n-zm3. INFLUENCE can be solved in polynomial time if: 1. There is at least a fraction p of affected voters with a degree of at most d, where 1- 2max∆ n′ < p ≤1. 2. There is at least a fraction pω of affected voters with a degree of at most d that do not dislike ω, where pω>max( 1 m, (1-p)). 3.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a known poll, target candidate \(\omega\), and a finite distribution of positive mass over voter types that specify strict rankings and bounded integer counts of initial neighbors by type, find a finite split into cohorts and an integer balanced table of added links so that the paper’s update process reaches a stable profile in which \(\omega\) wins. Consider societies where each candidate has positive mass of first-round supporters and more than \(1/m\) of the population does not rank \(\omega\) last.
Let \(C\) contain \(m\geq2\) candidates, with target \(\omega\), a fixed lexicographic tie-breaking order, and known poll scores \(q_c\in\mathbb Z_{\geq0}\). Write \(W(x)\) for the tie-broken Plurality winner of score vector \(x\).
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Each type specifies a strict ranking and integers \(k_{tu}\geq0\), its initial neighbor counts by type, with \(\sum_u k_{tu}\leq d\) and \(\mu_tk_{tu}=\mu_uk_{ut}\). Here \(\tau\) is the support size, not the number of possible types.
Assume every candidate has positive mass ranking it first, and the mass not ranking \(\omega\) last exceeds \(1/m\).
An intervention chooses finitely many cohorts \(i\), each inheriting a type \(t(i)\), with positive rational masses \(w_i\) satisfying \(\sum_{i:t(i)=t}w_i=\mu_t\), and nonnegative integer tables \(B,A\) satisfying \(\sum_{j:t(j)=u}B_{ij}=k_{t(i)u}\), \(w_iB_{ij}=w_jB_{ji}\), and \(w_iA_{ij}=w_jA_{ji}\).
The tables specify initial and added neighbors per individual; diagonal entries mean distinct neighbors within the same cohort, never self-loops. There is no bound on added links or cohort count. All additions occur before voting and remain fixed.
Initially each cohort votes for its ranking's first candidate. At round \(r\), its perceived scores are \(x_{i,c}(r)=q_c+\sum_j(B_{ij}+A_{ij})\mathbf1\{b_j(r)=c\}\).
Updates are simultaneous: among candidates \(a\neq b_i(r)\) preferred to \(W(x_i(r))\) for which \(W(x_i(r)+e_a)=a\), choose the most preferred; if none exists, retain the current vote. Here \(e_a\) is one unit vote, even though individuals have zero population mass.
A profile is stable when every cohort retains its vote. Its global winner is \(W((\sum_iw_i\mathbf1\{b_i=c\})_{c\in C})\). Feasibility means some intervention reaches a stable profile with winner \(\omega\) after finitely many rounds.
Is this feasibility problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\), displaying any additional dependence on \(d\) and poll size \(s=\sum_cq_c\); \(L\) is the total input bit length, including binary-encoded counts and poll scores.
For finite societies, known-poll influence has a polynomial-time construction under quantitative bounded-degree, supporter-reserve, and preference-fraction conditions; it stabilizes by round three ([Sina et al., 2015](https://u.cs.biu.ac.il/~sarit/data/articles/fp195-Sina.pdf)).
No result settling this exact mass-and-integer-cohort formulation was located.
The problem is in \(\mathrm P\). In fact, every instance satisfying the stated assumptions is feasible.
More strongly, an intervention with exactly \(m\tau\) cohorts and polynomial encoding length suffices. Starting from truthful votes, it reaches a stable profile with strict global winner \(\omega\) after one simultaneous update.
The construction uses arbitrarily small rational reserve cohorts and unbounded added degrees, both expressly permitted in the question.
Write the input masses over a common denominator as \(\mu_t=n_t/D\), where every \(n_t\) is a positive integer and \(\sum_t n_t=D\). Taking the product of the input denominators gives such a \(D\) with \(O(L)\) bits.
Let \(p=\sum_{t:\,\omega\text{ is not last for }t}\mu_t\). By assumption, \(p>1/m\). Define
\[ g=p-\frac{1-p}{m-1}=\frac{mp-1}{m-1}>0. \]
Choose the positive integers
\[ P=\prod_{t=1}^{\tau}n_t,\qquad K=\left\lceil\frac1g\right\rceil+1,\qquad H=(m-1)PK. \]
Then \(Hg>1\). Moreover, for every pair of types \(t,u\),
\[ \frac{H\mu_t}{(m-1)\mu_u} =PK\frac{n_t}{n_u} \]
is a positive integer, because \(n_u\) divides \(P\). This divisibility will make every added reciprocal count integral.
Set \(\varepsilon=1/(H+1)\), and enumerate the candidates other than \(\omega\) as \(c_1,\ldots,c_{m-1}\).
For each type \(t\), create \(m\) cohorts, indexed by \(r\in\{0,\ldots,m-1\}\), with masses
\[ w_{t,0}=\varepsilon\mu_t,\qquad w_{t,r}=\frac{1-\varepsilon}{m-1}\mu_t \quad(1\leq r\leq m-1). \]
All masses are positive rational numbers, and their sum for each type is \(\mu_t\).
The cohorts with \(r=0\) form the reserve. Every reserve cohort will retain its truthful vote.
Define the initial table by
\[ B_{(t,r),(u,r)}=k_{tu},\qquad B_{(t,r),(u,r')}=0\quad(r\ne r'). \]
Thus each cohort has exactly its prescribed number of initial neighbors of every type. Within each copy, all masses have the same scaling factor, so the input identity \(\mu_tk_{tu}=\mu_uk_{ut}\) gives
\[ w_{t,r}B_{(t,r),(u,r)} =w_{u,r}B_{(u,r),(t,r)}. \]
The initial table therefore satisfies every required constraint.
For each candidate \(c\), select a reserve cohort \(a(c)\) whose type ranks \(c\) first. Such a cohort exists by the positive first-choice-mass assumption. Different candidates have different selected cohorts.
For a working cohort \((t,r)\), where \(r\geq1\), prescribe its eventual vote as
\[ z(t,r)= \begin{cases} \omega,&\omega\text{ is not last for }t,\\ c_r,&\omega\text{ is last for }t. \end{cases} \]
Every prescribed vote is different from that type’s last-ranked candidate.
Call a cohort *fixed* if it is in the reserve or its prescribed vote is already its first choice.
First construct all off-diagonal additions as described in the next section. For each fixed cohort \(i\), then set
\[ A_{ii}=s+\sum_jB_{ij}+\sum_{j\ne i}A_{ij}+2. \]
These diagonal additions satisfy mass balance automatically.
Suppose \(i\) currently votes for its first choice \(f_i\). Its diagonal added neighbors contribute \(A_{ii}\) votes to \(f_i\). Every other candidate’s perceived score is at most
\[ s+\sum_jB_{ij}+\sum_{j\ne i}A_{ij}=A_{ii}-2. \]
Consequently, \(W(x_i)=f_i\). No candidate is preferred to this winner, so the update rule retains \(f_i\).
Starting from truthful voting, induction shows that every fixed cohort keeps its first-choice vote forever, regardless of the votes outside that cohort. In particular, every selected reserve cohort \(a(c)\) supplies fixed votes for \(c\).
The diagonal entries here have exactly the interpretation allowed in the question: distinct neighbors within the same cohort.
Let \(d_0=\max_t\sum_u k_{tu}\), so \(d_0\leq d\), and put
\[ T=s+2d_0+2. \]
Consider a nonfixed working cohort \(i=(t,r)\). Let \(z=z(t,r)\), and let \(\ell\) be the last-ranked candidate of type \(t\). Thus \(z\ne\ell\), and \(z\) differs from \(i\)’s initial vote.
Before additions, its truthful perceived score for candidate \(c\) is
\[ h_{t,c}=q_c+\sum_{u:\,u\text{ ranks }c\text{ first}}k_{tu}. \]
Every \(h_{t,c}\) is at most \(s+d_0\).
Define \(\alpha=1\) if the tie-breaking order favors \(z\) over \(\ell\), and \(\alpha=0\) otherwise. Add neighbors according to
\[ A_{i,a(z)}=T-h_{t,z},\qquad A_{i,a(\ell)}=T+\alpha-h_{t,\ell}. \]
Both counts are positive integers. All other off-diagonal additions incident from \(i\) are zero.
For either selected reserve endpoint \(j=a(c)\), define the reciprocal count by
\[ A_{ji}=\frac{w_i}{w_j}A_{ij}. \]
If \(j\) inherits type \(u\), then
\[ \frac{w_i}{w_j} =\frac{H\mu_t}{(m-1)\mu_u}, \]
which is an integer by Section 1. Thus the reciprocal count is a nonnegative integer and \(w_iA_{ij}=w_jA_{ji}\). All off-diagonal additions satisfy the required balance constraints.
At the truthful profile, the resulting perceived scores are \(x_{i,z}=T\) and \(x_{i,\ell}=T+\alpha\). Every other candidate has score at most \(s+d_0<T\).
There are two cases:
Hence \(W(x_i)=\ell\) and \(W(x_i+e_z)=z\). The cohort prefers \(z\) to \(\ell\).
No candidate outside \(\{z,\ell\}\) can win after receiving one additional vote, because its score is at most \(s+d_0+1<T\). Therefore \(z\) is the unique eligible alternative, and cohort \(i\) switches to \(z\).
All fixed cohorts retain their votes during this simultaneous update.
The added neighbors of \(i\) keep voting for \(z\) and \(\ell\). Changes among its initial neighbors can decrease either candidate’s score by at most \(d_0\). Therefore, after the update,
\[ x_{i,z}\geq T-d_0,\qquad x_{i,\ell}\geq T+\alpha-d_0. \]
Both lower bounds are at least \(s+d_0+2\). Any candidate outside this pair has perceived score at most \(s+d_0\), even if all initial neighbors vote for it. Such a candidate cannot win after one additional vote.
The perceived winner must consequently be \(z\) or \(\ell\):
In either case, the cohort retains \(z\). Together with Section 3, this proves that the profile after the first update is stable.
Let \(f_c\) be the original mass ranking candidate \(c\) first. The reserve contributes \(\varepsilon f_c\) votes to \(c\).
All working mass of types not ranking \(\omega\) last votes for \(\omega\). The remaining working mass is divided equally among the other \(m-1\) candidates. Consequently, the stable global scores are
\[ v_\omega=(1-\varepsilon)p+\varepsilon f_\omega, \]
and, for every \(c\ne\omega\),
\[ v_c=(1-\varepsilon)\frac{1-p}{m-1}+\varepsilon f_c. \]
Since \(f_\omega-f_c\geq-1\),
\[ v_\omega-v_c =(1-\varepsilon)g+\varepsilon(f_\omega-f_c) \geq(1-\varepsilon)g-\varepsilon =\frac{Hg-1}{H+1}>0. \]
Thus \(\omega\) strictly defeats every rival. Global tie-breaking is immaterial.
This completes the feasibility proof.
The construction uses exactly \(m\tau\) cohorts. Its arithmetic remains polynomial in the binary input length.
Indeed, \(D\) and each \(n_t\) have \(O(L)\) bits, so \(P\) has \(O(\tau L)\) bits. If \(S=\sum_{t:\,\omega\text{ is not last}}n_t\), then
\[ g=\frac{mS-D}{(m-1)D}. \]
The numerator is a positive integer, implying \(g\geq1/((m-1)D)\). Hence \(K\) has \(O(L+\log m)\) bits, and \(H\) has \(O(\tau L+\log m)\) bits.
A nonfixed working cohort receives at most \(2T+1=O(s+d+1)\) added neighbors. For a selected reserve cohort of type \(u\), its total off-diagonal added degree is at most \(H(T+1)/\mu_u\): summing the mass ratios of all working cohorts to this reserve cohort gives \(H/\mu_u\), and each incident working count is at most \(T+1\). This bound also controls the diagonal additions.
Therefore all masses and counts in the output have
\[ \beta=O\!\left(\tau L+\log(m+d+s+2)\right) \]
bits. Using schoolbook integer arithmetic, a conservative bound for constructing and writing both dense tables is
\[ O\!\left((L+m^2\tau^2) \left(\tau L+\log(m+d+s+2)\right)^2\right) \]
bit operations. The dependence on \(d\) and \(s\) is logarithmic; no iteration runs up to either numerical value.
For the decision problem on the promised domain, the algorithm simply returns yes, taking \(O(L)\) time if it reads the input. The construction above additionally supplies a polynomial-size witness.
Unlike the quantitative finite-society construction of [Sina et al. (2015)](https://u.cs.biu.ac.il/~sarit/data/articles/fp195-Sina.pdf), this proof obtains its reserve from rational subdivision and protects it using unbounded internal added degrees.
⟨structured verdict parsed — rendered above⟩
The construction is sound in substance and establishes polynomial-time feasibility on the promised domain. Every promised instance is feasible, and the proposed intervention reaches a stable profile with strict winner \(\omega\) after one simultaneous update.
There is one minor specification gap: the added diagonal entries for nonfixed cohorts are never explicitly assigned. The voting calculations require these entries to be zero. Making that initialization explicit suffices; no new mathematical argument is needed.
The common-denominator representation is valid. Taking the product of the input denominators produces an integer \(D\) with \(O(L)\) bits, and each \(n_t=D\mu_t\) is a positive integer.
The assumption \(p>1/m\) gives
\[
g=\frac{mp-1}{m-1}>0.
\]
Consequently, \(K=\lceil 1/g\rceil+1\) satisfies \(Kg>1\). Since \((m-1)P\geq1\), the claimed inequality \(Hg>1\) follows.
For every pair \(t,u\),
\[
\frac{H\mu_t}{(m-1)\mu_u}=PK\frac{n_t}{n_u}
\]
is indeed a positive integer: \(n_u\) divides the product \(P\). This establishes the divisibility needed later for reciprocal added counts.
The cohort masses are positive because \(H>0\), hence \(0<\varepsilon<1\). Their sum within each type is exactly \(\mu_t\). There are exactly \(m\tau\) cohorts.
For every cohort \((t,r)\) and type \(u\), summing its initial counts over all cohorts inheriting \(u\) gives \(k_{tu}\), as required.
Within each copy \(r\), the cohort masses are a common multiple of the original masses. Thus the input balance identity gives the claimed balance for \(B\). Across different copies, both corresponding entries vanish.
Diagonal entries \(k_{tt}\) are consistent with the explicitly permitted interpretation of distinct neighbors within a cohort. The task imposes no additional finite-population realization constraint.
Every candidate has a selected reserve cohort because its first-choice mass is positive. Selected cohorts for distinct candidates must be distinct, since each type has a unique first choice.
The prescribed working vote is never the type’s last-ranked candidate: this follows directly from the two cases defining \(z(t,r)\).
Each nonfixed working cohort connects to two distinct reserve cohorts, corresponding to \(z\) and its last-ranked candidate \(\ell\).
Its reciprocal counts are integers because the working-to-reserve mass ratio is precisely the integer established in Section 1. The definition of each reciprocal entry satisfies mass balance exactly.
No entries conflict: working cohorts and reserve cohorts are disjoint, and each nonfixed working cohort assigns only its own two outgoing entries. Diagonal mass balance holds automatically.
Minor issue — unassigned diagonal entries. The construction explicitly assigns diagonals for fixed cohorts but does not state the value of \(A_{ii}\) for nonfixed cohorts. Section 4’s perceived-score calculations require those entries to vanish. The minimum clarification is to state explicitly that every nonfixed cohort has \(A_{ii}=0\), or that the entire added table is initialized to zero before the listed assignments.
The diagonal protection argument is valid. When a fixed cohort votes for its first choice, its diagonal additions contribute \(A_{ii}\) to that candidate. Every competing candidate receives at most the stated sum of poll scores, initial neighbors, and off-diagonal added neighbors, which equals \(A_{ii}-2\).
Thus its first choice is the perceived winner regardless of outside votes. No candidate is preferred to that winner, so no update is eligible.
The induction starts at the truthful profile and applies to simultaneous updates. It therefore establishes that every fixed cohort, including every selected reserve endpoint, retains its truthful vote forever.
For each nonfixed cohort, \(z\) differs from its initial vote by the definition of “fixed.” Its last-ranked candidate \(\ell\) also differs from its initial vote.
The initial scores satisfy \(h_{t,c}\leq s+d_0\), so both assigned added counts are positive integers.
With the diagonal clarification above, the resulting scores are exactly
\[
x_{i,z}=T,\qquad x_{i,\ell}=T+\alpha.
\]
Every other candidate has score at most \(s+d_0\).
Both tie-breaking cases are correct:
An outside candidate cannot become the winner after one additional vote because
\[
s+d_0+1<T.
\]
The candidate \(\ell\) is not preferred to the current perceived winner \(\ell\). Hence \(z\) is the unique eligible alternative, and the cohort switches to it.
The fixed reserve endpoints retain their votes during this update, so the simultaneous nature of the process causes no problem.
The two added-neighbor blocks keep their candidate labels because their reserve endpoints remain fixed. Changes among initial neighbors can reduce either candidate’s score by at most \(d_0\). Therefore the claimed lower bounds hold:
\[
x_{i,z}\geq T-d_0,\qquad
x_{i,\ell}\geq T+\alpha-d_0.
\]
Both are at least \(s+d_0+2\). Every outside candidate has score at most \(s+d_0\), even after the initial neighbors change their votes. Thus no outside candidate can win by receiving one additional vote.
The perceived winner consequently lies in \(\{z,\ell\}\). If it is \(z\), the only other potentially pivotal candidate is last-ranked and therefore ineligible. If it is \(\ell\), the only other potentially pivotal candidate is \(z\), which is excluded because it is already the cohort’s current vote.
Every nonfixed cohort therefore retains its new vote. Combined with the fixed-cohort argument, this proves stability after the first update.
The final score formulas correctly account for both fixed and nonfixed working cohorts: a fixed working cohort’s truthful vote already equals its prescribed vote.
The reserve contributes \(\varepsilon f_c\) to each candidate. Working mass from types not ranking \(\omega\) last votes for \(\omega\), and the remaining working mass is split equally among its rivals.
Since \(f_\omega-f_c\geq-1\),
\[
v_\omega-v_c
\geq (1-\varepsilon)g-\varepsilon
=\frac{Hg-1}{H+1}>0.
\]
Thus the global winner is strictly \(\omega\), independently of global tie-breaking.
The bit-length analysis is valid:
The reserve-degree estimate is valid: each incident working count is at most \(T+1\), and summing the working-to-reserve mass ratios over all working cohorts gives \(H/\mu_u\). Adding the diagonal protection preserves the claimed asymptotic bit bound.
The conservative construction bound
\[
O\!\left((L+m^2\tau^2)
\left(\tau L+\log(m+d+s+2)\right)^2\right)
\]
is consistent with dense-table output and schoolbook arithmetic. Its dependence on the numerical degree and poll size is logarithmic.
On the promised domain, the decision algorithm may return yes after reading the input, giving the stated \(O(L)\) bound. This claim does not include validating whether an arbitrary input satisfies the promises.
The proof does not invoke the finite-society theorem: its final comparison with that result is contextual and is unnecessary for the classification.
⟨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.