Voter Priming Campaigns: Strategies, Equilibria, and Algorithms (aaai25-33544)

Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), rational \(q_{t,i}(c)\), \(s_{t,i}(0)\), common sensitivities \(\rho_i\), issues \(I\), and budgets \(W^A,W^B\), compute \(i,j\in I\) such that \(w^A=W^Ae_i\) and \(w^B=W^Be_j\) form a pure Nash equilibrium for \(r_\mu(c,w)=P_\mu(c,w)/\sum_{c'}P_\mu(c',w)\), where \(P_\mu(c,w)=\sum_{t\in T}\mu_t\sum_{i\in I}q_{t,i}(c)(s_{t,i}(0)+\rho_iw_i)/\sum_{k\in I}(s_{t,k}(0)+\rho_kw_k)\).

There are two candidates \(C=\{A,B\}\) and \(m=|I|\) issues. A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Require \(\sum_t\mu_t=1\), and let \(L\) be the total input bit length.
All input scores, saliences, sensitivities, and budgets are binary rationals satisfying \(q_{t,i}(c)\geq0\), \(q_{t,i}(A)+q_{t,i}(B)\leq1\), \(s_{t,i}(0)\geq0\), \(\sum_i s_{t,i}(0)=1\), \(\rho_i\geq0\), and \(W^A,W^B\geq0\). Sensitivities are common to all types.
Include a dummy issue \(0\in I\) with \(q_{t,0}(c)=s_{t,0}(0)=\rho_0=0\), representing unused budget. Candidate \(c\)'s strategies are all real vectors \(w^c\geq0\) with \(\sum_i w_i^c=W^c\); deviations may split the budget arbitrarily.
For \(w=w^A+w^B\), define \(P_\mu(c,w)=\sum_t\mu_t\frac{\sum_i q_{t,i}(c)(s_{t,i}(0)+\rho_iw_i)}{\sum_k(s_{t,k}(0)+\rho_kw_k)}\) and utility \(r_\mu(c,w)=\frac{P_\mu(c,w)}{P_\mu(A,w)+P_\mu(B,w)}\). Require \(\sum_t\mu_t\sum_i s_{t,i}(0)(q_{t,i}(A)+q_{t,i}(B))>0\), ensuring positive turnout at every feasible profile.

Is computing \(i,j\in I\) such that \((W^Ae_i,W^Be_j)\) is a pure Nash equilibrium solvable in polynomial time in \(m,\tau,L\), or is this search problem NP-hard?

For a finite list of \(N\) voters, a pure equilibrium with both candidates concentrating their budgets on single issues always exists, with a reported computation bound of \(O(m^2+N)\). [Source](https://arxiv.org/html/2412.13380v1)
No result addressing exactly this binary-rational mass formulation was located.

1. Result and aggregation. The search problem is polynomial-time solvable in \(m,\tau,L\). The algorithm uses \(O(\tau m+m^2)\) exact rational arithmetic operations, and all intermediate numbers have polynomial bit length. The proof includes arbitrary real-valued budget-splitting deviations.

Define
\[ \]
\(a_0=\sum_t\mu_t\sum_i s_{t,i}(0)q_{t,i}(A),\qquad b_0=\sum_t\mu_t\sum_i s_{t,i}(0)\bigl(q_{t,i}(A)+q_{t,i}(B)\bigr),\)

and, for every issue \(i\), define

\(a_i=\rho_i\sum_t\mu_tq_{t,i}(A),\qquad b_i=\rho_i\sum_t\mu_t\bigl(q_{t,i}(A)+q_{t,i}(B)\bigr).\)

The hypotheses imply \(0\leq a_0\leq b_0\), \(b_0>0\), and \(0\leq a_i\leq b_i\).

For every type \(t\), normalization and common sensitivities give

\(\sum_k\bigl(s_{t,k}(0)+\rho_kw_k\bigr)=1+\sum_k\rho_kw_k.\)

Consequently,

\(P_\mu(A,w)=\dfrac{a_0+\sum_i a_iw_i}{1+\sum_i\rho_iw_i},\qquad P_\mu(A,w)+P_\mu(B,w)=\dfrac{b_0+\sum_i b_iw_i}{1+\sum_i\rho_iw_i}.\)

Thus candidate \(A\)'s utility is

\(R(w):=r_\mu(A,w)=\dfrac{a_0+\sum_i a_iw_i}{b_0+\sum_i b_iw_i}.\)

Its denominator is at least \(b_0>0\), and \(r_\mu(B,w)=1-R(w)\). Therefore, \(A\) maximizes \(R\), while \(B\) minimizes it.

This is the weighted analogue of the aggregation in Section 2.1 of the [cited paper](https://arxiv.org/html/2412.13380v1#S2.SS1). The following existence proof and bit-complexity analysis are self-contained.

2. Split deviations reduce to single-issue deviations. Fix the opponent’s investment \(y\), and let the deviating candidate have budget \(W\).

Every feasible investment \(x\) can be written as

\(x=\sum_i\lambda_iWe_i,\qquad \lambda_i\geq0,\qquad \sum_i\lambda_i=1.\)

When \(W>0\), take \(\lambda_i=x_i/W\). When \(W=0\), the only feasible investment is zero, and any such coefficients work.

Set

\(N_i=a_0+\sum_k a_ky_k+Wa_i,\qquad D_i=b_0+\sum_k b_ky_k+Wb_i.\)

Because the coefficients sum to one,

\(R(x+y)=\dfrac{\sum_i\lambda_iN_i}{\sum_i\lambda_iD_i} =\sum_i\frac{\lambda_iD_i}{\sum_k\lambda_kD_k}\,R(We_i+y).\)

Every \(D_i\) is positive. Hence the final expression is a convex combination of the single-issue utilities. In particular,

\(\min_iR(We_i+y)\leq R(x+y)\leq\max_iR(We_i+y).\)

Thus, against a fixed opponent investment, a split deviation cannot outperform every single-issue deviation. This applies to both \(A\)'s maximization and \(B\)'s minimization.

3. A single-issue equilibrium always exists. Write \(\alpha=W^A\) and \(\beta=W^B\). For \(v\in[0,1]\), define

\(h_i(v)=a_i-vb_i\)

and

\(F(v)=a_0-vb_0+\alpha\max_i h_i(v)+\beta\min_i h_i(v).\)

The function \(F\) is continuous because it is formed from maxima and minima of finitely many continuous functions. Moreover, each \(h_i\) is nonincreasing, since \(b_i\geq0\). Therefore, for \(v_2>v_1\),

\(F(v_2)\leq F(v_1)-b_0(v_2-v_1)<F(v_1).\)

The endpoint signs are

\(F(0)=a_0+\alpha\max_i a_i+\beta\min_i a_i\geq0\)

and

\(F(1)=a_0-b_0+\alpha\max_i(a_i-b_i)+\beta\min_i(a_i-b_i)\leq0.\)

By the intermediate value theorem, there is a unique \(v^*\in[0,1]\) with \(F(v^*)=0\).

Choose

\(p\in\operatorname*{arg\,max}_i h_i(v^*),\qquad q\in\operatorname*{arg\,min}_i h_i(v^*).\)

For any investments \(x,y\), subtraction of \(v^*\) gives

\(R(x+y)-v^*= \dfrac{a_0-v^*b_0+\sum_i h_i(v^*)(x_i+y_i)} {b_0+\sum_i b_i(x_i+y_i)}.\)

At \(x=\alpha e_p,\ y=\beta e_q\), the numerator is \(F(v^*)=0\), so the utility is \(v^*\).

For every feasible deviation \(x'\) of \(A\),

\(\sum_i h_i(v^*)x'_i\leq\alpha h_p(v^*),\)

because \(x'_i\geq0\), \(\sum_i x'_i=\alpha\), and \(h_p(v^*)\) is the largest coefficient. Thus the numerator of \(R(x'+\beta e_q)-v^*\) is nonpositive. Its denominator is positive, so

\(R(x'+\beta e_q)\leq v^*.\)

Similarly, every feasible deviation \(y'\) of \(B\) satisfies

\(\sum_i h_i(v^*)y'_i\geq\beta h_q(v^*),\)

and hence

\(R(\alpha e_p+y')\geq v^*.\)

Therefore, \((\alpha e_p,\beta e_q)\) is a pure Nash equilibrium against all feasible real-valued deviations. The argument also covers zero budgets.

4. Exact algorithm without computing the root. Construct the matrix

\(M_{ij}=R(\alpha e_i+\beta e_j) =\dfrac{a_0+\alpha a_i+\beta a_j}{b_0+\alpha b_i+\beta b_j}.\)

Compute each row minimum and each column maximum:

\(\ell_i=\min_jM_{ij},\qquad u_j=\max_iM_{ij}.\)

Return independently chosen indices

\(i^*\in\operatorname*{arg\,max}_i\ell_i,\qquad j^*\in\operatorname*{arg\,min}_ju_j.\)

To prove correctness, the equilibrium \((p,q)\) established above implies

\(M_{kq}\leq v^*\leq M_{pj}\qquad\text{for every }k,j,\)

with \(M_{pq}=v^*\). Therefore:

• Every row minimum is at most \(v^*\), while row \(p\)'s minimum equals \(v^*\).
• Every column maximum is at least \(v^*\), while column \(q\)'s maximum equals \(v^*\).

It follows that

\(\max_i\ell_i=\min_ju_j=v^*.\)

For the returned indices,

\(v^*=\ell_{i^*}\leq M_{i^*j^*}\leq u_{j^*}=v^*,\)

so \(M_{i^*j^*}=v^*\). Furthermore,

\(M_{kj^*}\leq v^*\leq M_{i^*j}\qquad\text{for every }k,j.\)

Thus neither candidate has a profitable single-issue deviation. Section 2 then excludes every split deviation. The returned pair is consequently a Nash equilibrium in the original strategy spaces.

5. Polynomial bit complexity. Computing the aggregate coefficients takes \(O(\tau m)\) rational operations. Constructing the matrix and finding its row minima and column maxima takes \(O(m^2)\) rational operations and comparisons.

To bound their bit complexity, interpret each input rational as a binary-encoded numerator and positive denominator. Let \(D\) be the product of all input denominators. Since their total encoding length is at most \(L\), the binary length of \(D\) is \(O(L)\).

Each aggregate coefficient is a sum of products of at most three input rationals. It therefore has a representation with denominator \(D^3\). After multiplication by a budget, every numerator or denominator expression defining \(M_{ij}\) has a representation with denominator \(D^4\).

Every input rational has magnitude at most \(2^L\). The expressions above involve products of at most four inputs and sums of \(O(\tau m)\) terms. Their integer numerators consequently have bit length \(O(L+\log(\tau m))\). The denominators have the same polynomial bound. Exact comparisons use cross-multiplication of positive denominators and also require only polynomial-length integers.

Standard integer arithmetic therefore implements the algorithm in time polynomial in \(m,\tau,L\). No expansion of rational masses into individual voters and no numerical approximation of \(v^*\) are required.

⟨structured verdict parsed — rendered above⟩

The argument establishes polynomial-time solvability in substance. There is one minor notation issue: the baseline constants \(a_0,b_0\) collide with the coefficients of the required dummy issue \(0\). No additional mathematics is needed, but these symbols must be distinguished to make the write-up internally consistent.

• Aggregation — correct apart from the notation collision.

The normalization \(\sum_k s_{t,k}(0)=1\) and type-independent sensitivities imply that every type has the same denominator \(1+\sum_k\rho_kw_k\). Factoring this denominator out of the weighted sum is therefore valid.

The stated aggregate expressions correctly collect the baseline contributions and investment contributions. Nonnegative masses, scores, and sensitivities give the asserted coefficient inequalities. The positive-turnout hypothesis makes the baseline denominator constant strictly positive, so cancellation is valid at every feasible profile. Consequently, \(B\)'s utility is \(1-R\), and the maximization/minimization interpretation is correct.

Minor issue: the instruction “for every issue \(i\)” includes the dummy issue \(0\). Its coefficient definitions give \(a_0=b_0=0\), whereas the preceding baseline definition requires \(b_0>0\). These are evidently two different intended quantities, but the notation identifies them. The sums over issues inherit this ambiguity.

Minimum clarification: give the two baseline constants distinct names and use those names consistently outside the issue-indexed sums. Keep the dummy issue coefficients equal to zero.

• Reduction of split deviations — correct.

For a positive budget, the coefficients \(\lambda_i=x_i/W\) are nonnegative and sum to one. For a zero budget, the only feasible investment is zero, and the stated representation remains valid.

Both numerator and denominator are affine in the deviating investment. The displayed identity therefore holds. Every \(D_i\) is strictly positive, and the weights
\(\lambda_iD_i/\sum_k\lambda_kD_k\) are nonnegative and sum to one.

Thus the utility of every real-valued split deviation lies between the minimum and maximum single-issue utilities. This excludes profitable split deviations whenever all single-issue deviations are unprofitable, for either candidate.

• Existence proof — correct.

The issue set is finite and nonempty, so its maxima and minima exist. Each \(h_i\) is continuous and nonincreasing. Their maximum and minimum are consequently continuous and nonincreasing. Because the baseline denominator constant is positive and both budgets are nonnegative, the displayed strict-decrease bound for \(F\) is valid.

The endpoint signs follow from the coefficient inequalities. The intermediate value theorem applies to the continuous function on \([0,1]\), giving a root; strict decrease gives uniqueness. Roots at either endpoint are permitted.

At the selected maximizing and minimizing issues, the numerator of \(R-v^*\) equals \(F(v^*)=0\). For any feasible deviation by \(A\), that numerator is nonpositive; for any feasible deviation by \(B\), it is nonnegative. The denominators remain positive, so both Nash inequalities have the correct direction.

The argument explicitly covers arbitrary real allocations and zero budgets. Ties among maximizing or minimizing issues cause no difficulty.

• Exact matrix algorithm — correct.

The established equilibrium gives
\(M_{kq}\leq v^*\leq M_{pj}\) for every \(k,j\), with equality at \(M_{pq}\). These inequalities justify both the maximum row-minimum value and minimum column-maximum value being \(v^*\).

For independently chosen optimizing indices, the bounds
\(\ell_{i^*}\leq M_{i^*j^*}\leq u_{j^*}\) force equality to \(v^*\). Every entry in column \(j^*\) is at most that value, and every entry in row \(i^*\) is at least it. Hence neither candidate has a profitable single-issue deviation. The split-deviation calculation then establishes equilibrium in the original continuous strategy spaces.

No root approximation or expansion of rational masses into individual voters is required.

• Arithmetic count and bit complexity — correct.

Computing the aggregate coefficients requires \(O(\tau m)\) rational operations. Constructing and scanning the matrix requires \(O(m^2)\) operations and comparisons.

Every input denominator divides their product \(D\), whose bit length is \(O(L)\). Expanding the stated sums into products shows that aggregate coefficients admit denominator \(D^3\), and the numerator and denominator expressions defining a matrix entry admit denominator \(D^4\).

Each relevant term contains at most four input factors. Combining the input magnitude bound with the bit length of \(D^4\) and the number of summed terms gives the claimed \(O(L+\log(\tau m))\) bound for the integer numerators. A matrix entry is then a ratio of two polynomial-length integers. Positive denominators permit exact comparison by cross-multiplication, also using polynomial-length integers.

Thus the operation count yields polynomial bit complexity, rather than merely a unit-cost arithmetic bound.

• External reference and scope — sufficient.

The attribution to voter aggregation is consistent with [Section 2.1 of the cited paper](https://arxiv.org/html/2412.13380v1#S2.SS1). The submitted proof establishes its own aggregation, existence result, and algorithm; it does not depend on importing a theorem whose hypotheses remain unchecked.

Subject only to distinguishing the baseline constants from dummy-issue coefficients, the output resolves the exact binary-rational support formulation in USER_TASK. There are no major gaps or blocking issues.

⟨structured verdict parsed — rendered above⟩